- File:
-
- 1 edited
-
sage/groups/perm_gps/cubegroup.py (modified) (15 diffs)
Legend:
- Unmodified
- Added
- Removed
-
sage/groups/perm_gps/cubegroup.py
r6036 r6218 11 11 Products of moves are read {\it right to left}, so for example, 12 12 R*U means move U first and then R. 13 14 See \code{CubeGroup.parse()} for all possible input notations. 13 15 14 16 The "Singmaster notation": … … 40 42 - " (2007-08): colors corrected, "solve" rewritten (again),typos fixed. 41 43 - Robert Miller (2007-08): editing, cleaned up display2d 42 - Robert Bradshaw (2006-08): RubiksCube object, 3d plotting. 43 44 - Robert Bradshaw (2007-08): RubiksCube object, 3d plotting. 45 - DJ (2007-09): rewrote docstring for CubeGroup's "solve". 46 - Robert Bradshaw (2007-09): Versatile parse function for all input types. 47 44 48 REFERENCES: 45 49 Cameron, P., Permutation Groups. New York: Cambridge University Press, 1999. … … 613 617 #PermutationGroup_subgroup(H,self.__gens) #### very slow.. 614 618 self._group 619 620 def gen_names(self): 621 return ['B','D','F','L','R','U'] 615 622 616 623 def __str__(self): … … 620 627 return "The PermutationGroup of all legal moves of the Rubik's cube." 621 628 622 def __call__(self, other):629 def __call__(self, mv): 623 630 """ 624 631 EXAMPLES: … … 627 634 () 628 635 """ 629 return self. _group(other)636 return self.parse(mv) 630 637 631 638 def group(self): … … 664 671 g = G(self.gens()[5]) 665 672 return g 666 667 673 674 675 def parse(self, mv): 676 """ 677 This function allows one to create the permutation group element from a variety of formats. 678 679 INPUT: one of the following 680 list -- list of facets (as returned by self.facets()) 681 dict -- list of faces (as returned by self.faces()) 682 str -- either cycle notation (passed to GAP) or a product of generators or Singmaster notation 683 perm_group element -- returned as an element of self.group() 684 685 EXAMPLES: 686 sage: C = CubeGroup() 687 sage: C.parse(range(1,49)) 688 () 689 sage: g = C.parse("L"); g 690 (1,17,41,40)(4,20,44,37)(6,22,46,35)(9,11,16,14)(10,13,15,12) 691 sage: C.parse(str(g)) == g 692 True 693 sage: facets = C.facets(g); facets 694 [17, 2, 3, 20, 5, 22, 7, 8, 11, 13, 16, 10, 15, 9, 12, 14, 41, 18, 19, 44, 21, 46, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 6, 36, 4, 38, 39, 1, 40, 42, 43, 37, 45, 35, 47, 48] 695 sage: C.parse(facets) 696 (1,17,41,40)(4,20,44,37)(6,22,46,35)(9,11,16,14)(10,13,15,12) 697 sage: C.parse(facets) == g 698 True 699 sage: faces = C.faces("L"); faces 700 {'right': [[25, 26, 27], [28, 0, 29], [30, 31, 32]], 'up': [[17, 2, 3], [20, 0, 5], [22, 7, 8]], 'back': [[33, 34, 6], [36, 0, 4], [38, 39, 1]], 'down': [[40, 42, 43], [37, 0, 45], [35, 47, 48]], 'front': [[41, 18, 19], [44, 0, 21], [46, 23, 24]], 'left': [[11, 13, 16], [10, 0, 15], [9, 12, 14]]} 701 sage: C.parse(faces) == C.parse("L") 702 True 703 sage: C.parse("L' R2") == C.parse("L^(-1)*R^2") 704 True 705 sage: C.parse("L' R2") 706 (1,40,41,17)(3,43)(4,37,44,20)(5,45)(6,35,46,22)(8,48)(9,14,16,11)(10,12,15,13)(19,38)(21,36)(24,33)(25,32)(26,31)(27,30)(28,29) 707 sage: C.parse("L^4") 708 () 709 sage: C.parse("L^(-1)*R") 710 (1,40,41,17)(3,38,43,19)(4,37,44,20)(5,36,45,21)(6,35,46,22)(8,33,48,24)(9,14,16,11)(10,12,15,13)(25,27,32,30)(26,29,31,28) 711 """ 712 G = self.group() 713 if isinstance(mv, PermutationGroupElement): 714 # mv is a perm_group element, return mv 715 return mv if mv.parent() is G else G(mv) 716 elif isinstance(mv, str): 717 # It is a string: may be in cycle notation or rubik's notation 718 if '(' in mv and not '^' in mv: 719 return G(mv) 720 else: 721 gens = G.gens() 722 names = self.gen_names() 723 map = {} 724 for i in range(6): 725 map[names[i]] = gens[i] 726 g = G(1) 727 mv = mv.strip().replace(" ","*").replace("**", "*").replace("'", "-1").replace('^','').replace('(','').replace(')','') 728 M = mv.split("*") 729 for m in M: 730 if len(m) == 0: 731 pass 732 elif len(m) == 1: 733 g *= map[m[0]] 734 else: 735 g *= map[m[0]]**int(m[1:]) 736 return g 737 elif isinstance(mv, dict): 738 state = mv 739 state_facets = [] 740 keyss = state.keys() 741 keyss.sort() 742 for k in keyss: 743 r = state[k][0]+state[k][1]+state[k][2] 744 r.remove(0) 745 state_facets = state_facets + r 746 state0 = self.faces("") 747 state0_facets = [] 748 keyss = state0.keys() 749 keyss.sort() 750 for k in keyss: 751 r = state0[k][0]+state0[k][1]+state0[k][2] 752 r.remove(0) 753 state0_facets = state0_facets + r 754 p1 = [state0_facets.index(x) for x in range(1,49)] 755 p2 = [state_facets[j] for j in p1] 756 return G(p2) 757 elif isinstance(mv, list): 758 return G(mv) 759 else: 760 return G(mv) 761 668 762 def facets(self, g=None): 669 763 r""" … … 699 793 700 794 """ 701 if isinstance(mv, str): 702 fcts = self.move(mv)[1] 703 else: 704 fcts = self.facets(mv) 795 fcts = self.facets(self.parse(mv)) 705 796 faceR = [[fcts[24],fcts[25],fcts[26]],[fcts[27],0,fcts[28]],[fcts[29],fcts[30],fcts[31]]] 706 797 faceL = [[fcts[8],fcts[9],fcts[10]],[fcts[11],0,fcts[12]],[fcts[13],fcts[14],fcts[15]]] … … 710 801 faceB = [[fcts[32],fcts[33],fcts[34]],[fcts[35],0,fcts[36]],[fcts[37],fcts[38],fcts[39]]] 711 802 return {'right':faceR,'left':faceL,'up':faceU,'down':faceD,'front':faceF,'back':faceB} 803 712 804 713 805 def move(self,mv): … … 730 822 731 823 """ 824 g = self.parse(mv) 825 return g, self.facets(g) 826 732 827 mv = mv.strip().replace(" ","*").replace("**", "*").replace("'", "^(-1)") 733 828 m = mv.split("*") … … 803 898 You can see the right face has been rotated but not the left face. 804 899 """ 805 if isinstance(mv, str): 806 lst = self.move(mv)[1] 807 else: 808 lst = self.facets(mv) 900 g = self.parse(mv) 901 lst = self.facets(g) 809 902 line1 = " +--------------+\n" 810 903 line2 = " |%3d %3d %3d |\n"%(lst[0],lst[1],lst[2]) … … 838 931 sage: # "superflip+4 spot" (in 26q* moves) 839 932 """ 840 rubik = CubeGroup() 841 if isinstance(mv, str): 842 state = rubik.move(mv)[1] 843 else: 844 state = rubik.facets(mv) 933 g = self.parse(mv) 934 state = self.facets(g) 845 935 #print state 846 936 str_colors = [index2singmaster(state[x])+"("+str(color_of_square(x+1))+")" for x in range(48)] … … 869 959 sage: P = rubik.plot3d_cube("R*L*D^2*B^3*L^2*F^2*R^2*U^3*D*R^3*D^2*F^3*B^3*D^3*F^2*D^3*R^2*U^3*F^2*D^3") 870 960 """ 871 rubik = CubeGroup()872 state = rubik.move(mv)[1]961 g = self.parse(mv) 962 state = self.facets(g) 873 963 clr_any = white 874 964 shown_labels = range(1,9)+range(17,33) … … 914 1004 915 1005 """ 916 state_facets = []917 keyss = state.keys()918 keyss.sort()919 for k in keyss:920 r = state[k][0]+state[k][1]+state[k][2]921 r.remove(0)922 state_facets = state_facets + r923 state0 = self.faces("")924 state0_facets = []925 keyss = state0.keys()926 keyss.sort()927 for k in keyss:928 r = state0[k][0]+state0[k][1]+state0[k][2]929 r.remove(0)930 state0_facets = state0_facets + r931 p1 = [state0_facets.index(x) for x in range(1,49)]932 p2 = [state_facets[j] for j in p1]933 #if mode != "quiet":934 # print "list (BDFLRU, L2R, T2B ordering):",p2935 G = self.group()936 1006 try: 937 g = G(p2) 1007 g = self.parse(state) 1008 res = 1 938 1009 except TypeError: 939 if mode != "quiet": 940 return 0,G([()]) 941 else: 942 return 0 1010 res = 0 1011 g = self.group()([()]) 1012 1013 if mode != 'quiet': 1014 return res, g 943 1015 else: 944 if mode != "quiet": 945 #print "cube group element:" 946 return 1,g 947 else: 948 return 1 949 1016 return res 1017 950 1018 def solve(self,state): 951 1019 r""" … … 976 1044 EXAMPLES: 977 1045 sage: rubik = CubeGroup() 1046 sage: state = rubik.faces("R") 1047 sage: rubik.solve(state) 1048 'R' 978 1049 sage: state = rubik.faces("R*U") 979 sage: rubik.solve(state) # long time; *computationally intensive* even for simple moves1050 sage: rubik.solve(state) # long time 980 1051 'R*U' 981 1052 982 You can also check this using \code{word_problem} method (eg, G = rubik.group(); 1053 You can also check this another (but similar) way using the 1054 \code{word_problem} method (eg, G = rubik.group(); 983 1055 g = G("(3,38,43,19)(5,36,45,21)(8,33,48,24)(25,27,32,30)(26,29,31,28)"); 984 1056 g.word_problem([b,d,f,l,r,u]), though the output will be less intuitive). … … 987 1059 from sage.groups.perm_gps.permgroup import PermutationGroup 988 1060 from sage.interfaces.all import gap 989 rubik = self 990 G = rubik.group() 991 if isinstance(state, str): 992 leg = rubik.legal(state,"verbose") 993 if not(leg[0]): 994 return "Illegal or syntactically incorrect state. No solution." 995 g = leg[1] 996 else: 997 g = state 1061 G = self.group() 1062 try: 1063 g = self.parse(state) 1064 except TypeError: 1065 return "Illegal or syntactically incorrect state. No solution." 998 1066 hom = G._gap_().EpimorphismFromFreeGroup() 999 1067 soln = hom.PreImagesRepresentative(gap(str(g))) 1000 1068 # print soln 1001 sol1 = str(soln).replace("x1","B") 1002 sol2 = sol1.replace("x2","D") 1003 sol3 = sol2.replace("x3","F") 1004 sol4 = sol3.replace("x4","L") 1005 sol5 = sol4.replace("x5","R") 1006 sol6 = sol5.replace("x6","U") 1007 return sol6 1008 1069 sol = str(soln) 1070 names = self.gen_names() 1071 for i in range(6): 1072 sol = sol.replace("x%s" % (i+1), names[i]) 1073 return sol 1009 1074 1010 1075
Note: See TracChangeset
for help on using the changeset viewer.
