• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Number of cases for 3 Cycles of Wing Edges in Last Layer (K4 Method)

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
Good point, and you are right, but we also have to be careful, and not get away from the relevance to LLK4.
K4LL.

Lucas: Do you have any ideas for a suitable naming system that could be used to specify (by its name alone) any big-cube edge perm case? Right now, without diagrams, or whole cube representations, it is (and is going to be - once the algs start rolling in) rather hard to communicate what cases are being referred to.
What's wrong with writing down the permutation or cycle decomposition?
You can number the edges if you want.

Also, do you mean edges or wings?
 
Joined
Dec 11, 2009
Messages
294
Lucas: Do you have any ideas for a suitable naming system that could be used to specify (by its name alone) any big-cube edge perm case? Right now, without diagrams, or whole cube representations, it is (and is going to be - once the algs start rolling in) rather hard to communicate what cases are being referred to.

What's wrong with writing down the permutation or cycle decomposition?
You can number the edges if you want.

Also, do you mean edges or wings?

Just go ahead and name/label some of the cases in this K4LL diagram you posted earlier. The nomenclature should be able to handle the additional FR edge pieces as well. I will use whatever convention you come up with.
K4LL_3cycles.png


EDIT: Starting idea for a universal edge perm case naming system. Number the edges 0-9 with UFr = 0, UFl = 1, and going clockwise ending with FRd = 9. Possible syntax - use bracket prefix [cycle1,cycle2,cycle3] to describe the cycles for the case (can be multiple (compound) cycles, clockwise/counterclockwise), and append the permutations for each, seperated by commas.
Examples for some cases above would be:
1st case - [3]170
2nd case - [3']710
5th case - [3]671
6th case - [3']761
PLL parity case - [2,2]40,15

Option to append "C4" to stand for Cube type = 4x4x4. 1st case would then = C4[3]170.

Lucas: feedback please?
 
Last edited:

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
I used the Polya-Burnside lemma to calculate the total number of cases for the last 10 edges (U-layer edges and FR edges), using conjugation by U-layer turns and reflections to reduce the cases. This gave 454096 cases. Without reflections, the number of cases increases to 907424. I also wrote a C++ program to do a brute force verification of these numbers. With my C++ program, I also computed 230612 cases when using inverses as well.

I note that if the idea is to generate optimal algs for each case, then conjugation by U-layer turns should not be used to reduce the cases. As I noted in an earlier post, it is possible to use conjugation by cube rotations (and not just y-axis rotations) to reduce the number of cases. I calculated the resulting number of cases for each set of n-cycles using a C++ program.

I am not completely sure of these results, but the values I got for using cube rotations only is (for n=2,3,...,10):

{ 14, 108, 818, 4800, 22500, 82080, 223036, 403200, 362880 }

For considering reflections as equivalent, the numbers I get reduce to:

{ 9, 54, 415, 2400, 11266, 41040, 111542, 201600, 181440 }

For considering reflections and inverses as equivalent, I get:

{ 9, 31, 220, 1224, 5681, 20616, 55879, 100992, 90816 }

Doing the same for only the edge pair preserving n-cycles, I get (for n=2,4,6,8,10):

considering cube rotations only:

{ 1, 5, 44, 204, 384 }

considering cube rotations and reflections:

{ 1, 3, 22, 102, 192 }

considering cube rotations, reflections, and inverses:

{ 1, 3, 15, 54, 104 }

EDIT: I implemented my case counting with a different algorithm as a check. As a result, I found a bug in my original code which resulted in a few wrong numbers. I've corrected these numbers in boldface. Both algorithms are now in agreement, making me now fairly confident of the results.
 
Last edited:
Joined
Dec 11, 2009
Messages
294
I used the Polya-Burnside lemma to calculate the total number of cases for the last 10 edges (U-layer edges and FR edges), using conjugation by U-layer turns and reflections to reduce the cases. This gave 454096 cases. Without reflections, the number of cases increases to 907424. I also wrote a C++ program to do a brute force verification of these numbers. With my C++ program, I also computed 230612 cases when using inverses as well.

I note that if the idea is to generate optimal algs for each case, then conjugation by U-layer turns should not be used to reduce the cases. As I noted in an earlier post, it is possible to use conjugation by cube rotations (and not just y-axis rotations) to reduce the number of cases. I calculated the resulting number of cases for each set of n-cycles using a C++ program.

I am not completely sure of these results, but the values I got for using cube rotations only is (for n=2,3,...,10):

{ 14, 108, 818, 4800, 22500, 82080, 223036, 403200, 362880 }

For considering reflections as equivalent, the numbers I get reduce to:

{ 9, 56, 416, 2400, 11266, 41040, 111542, 201600, 181440 }

For considering reflections and inverses as equivalent, I get:

{ 9, 32, 220, 1224, 5681, 20616, 55879, 100992, 90816 }

Doing the same for only the edge pair preserving n-cycles, I get (for n=2,4,6,8,10):

considering cube rotations only:

{ 1, 5, 44, 204, 384 }

considering cube rotations and reflections:

{ 1, 4, 22, 102, 192 }

considering cube rotations, reflections, and inverses:

{ 1, 3, 15, 54, 104 }

Very astute you are, Bruce. Yeah, it is tempting to simply reduce by conjugating the cases, but we should know FIRST which one (of the U-turn conj cases) yields the best alg for the primary case. Of course many of the earlier results - n-cycles preserving edge pairing (whether or not FR edges move):{ 2, 0, 3, 0, 8, 0, 20, 0, 30 } can also be further reduced by 1-2 move conjugations, but that also needs to wait for the same reason. I think the numbers you have above are correct for reducing single even-cycle cases without conjugation. So the next step would be to add in the other odd perm cases (multi-cycles) that also keep the composite edges paired. The 8-cycle and 10-cycle cases are exempt from this possibility, but the other even-cycle cases are not. Would it be possible for you to also include with those?
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
Very astute you are, Bruce. Yeah, it is tempting to simply reduce by conjugating the cases, but we should know FIRST which one (of the U-turn conj cases) yields the best alg for the primary case. Of course many of the earlier results - n-cycles preserving edge pairing (whether or not FR edges move):{ 2, 0, 3, 0, 8, 0, 20, 0, 30 } can also be further reduced by 1-2 move conjugations, but that also needs to wait for the same reason. I think the numbers you have above are correct for reducing single even-cycle cases without conjugation. So the next step would be to add in the other odd perm cases (multi-cycles) that also keep the composite edges paired. The 8-cycle and 10-cycle cases are exempt from this possibility, but the other even-cycle cases are not. Would it be possible for you to also include with those?

I've now analyzed the following cycles structures for odd permutations that preserve edge pairs.

The data for each case is:
{ total permutations, count reduced by cube rotations, count reduced by cube rotations & reflections, count reduced by cube rotations & reflections & inverses }

2-2-2-2-2:
{ 81, 81, 47, 47 }

2-2-2
{ 70, 41, 25, 25 }

2-2-4
{ 180, 153, 78, 42 }

2-2-6
{ 240, 240, 120, 66 }

2-4-4
{ 300, 300, 156, 84 }

EDIT:
In case anyone is interested in the number of cases when reducing by conjugation by U-layer turns instead of by cube rotations, I've generated these, too.

2-2-2-2-2
{ 81, 25, 18, 18 }

2-2-2
{ 70, 19, 14, 14 }

2-2-4
{ 180, 45, 24, 17 }

2-2-6
{ 240, 60, 30, 22 }

2-4-4
{ 300, 80, 43, 28 }
 
Last edited:
Joined
Dec 11, 2009
Messages
294
Very astute you are, Bruce. Yeah, it is tempting to simply reduce by conjugating the cases, but we should know FIRST which one (of the U-turn conj cases) yields the best alg for the primary case. Of course many of the earlier results - n-cycles preserving edge pairing (whether or not FR edges move):{ 2, 0, 3, 0, 8, 0, 20, 0, 30 } can also be further reduced by 1-2 move conjugations, but that also needs to wait for the same reason. I think the numbers you have above are correct for reducing single even-cycle cases without conjugation. So the next step would be to add in the other odd perm cases (multi-cycles) that also keep the composite edges paired. The 8-cycle and 10-cycle cases are exempt from this possibility, but the other even-cycle cases are not. Would it be possible for you to also include with those?

I've now analyzed the following cycles structures for odd permutations that preserve edge pairs.

The data for each case is:
{ total permutations, count reduced by cube rotations, count reduced by cube rotations & reflections, count reduced by cube rotations & reflections & inverses }

2-2-2-2-2:
{ 81, 81, 47, 47 }

2-2-2
{ 70, 41, 25, 25 }

2-2-4
{ 180, 153, 78, 42 }

2-2-6
{ 240, 240, 120, 66 }

2-4-4
{ 300, 300, 156, 84 }

EDIT:
In case anyone is interested in the number of cases when reducing by conjugation by U-layer turns instead of by cube rotations, I've generated these, too.

2-2-2-2-2
{ 81, 25, 18, 18 }

2-2-2
{ 70, 19, 14, 14 }

2-2-4
{ 180, 45, 24, 17 }

2-2-6
{ 240, 60, 30, 22 }

2-4-4
{ 300, 80, 43, 28 }

Bruce: Looking good here, but a couple odd ones got left out - [2-3-3], [4-3-3].

Any suggestions now, on how to generate all of the edge perm diagrams that would represent these cases, would be much appreciated.

Lucas: your esteemed feedback is urgently requested - for an earlier case naming post in this thread.
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
Bruce: Looking good here, but a couple odd ones got left out - [2-3-3], [4-3-3].


Using cube rotations
{ total permutations, count reduced by cube rotations, count reduced by cube rotations & reflections, count reduced by cube rotations & reflections & inverses }

2-3-3:
{ 160, 136, 68, 35 }

3-3-4:
{ 160, 160, 80, 44 }

Using conjugation by U-layer turns:
{ total permutations, count reduced by conjugation by U-layer turns, count reduced by conjugation by U-layer turns & reflections, count reduced by conjugation by U-layer turns & reflections & inverses }

2-3-3:
{ 160, 40, 20, 13 }

3-3-4:
{ 160, 40, 20, 15 }

EDIT:
Any suggestions now, on how to generate all of the edge perm diagrams that would represent these cases, would be much appreciated.

I modified my program to generate a list of all the various odd permutation cases preserving edge pairs (distinct with respect to cube rotations) using cycle notation.

See the attachmentment.
 

Attachments

  • L10E_Cases.txt
    39.3 KB · Views: 12
Last edited:
Joined
Dec 11, 2009
Messages
294
Any suggestions now, on how to generate all of the edge perm diagrams that would represent these cases, would be much appreciated.

I modified my program to generate a list of all the various odd permutation cases preserving edge pairs (distinct with respect to cube rotations) using cycle notation.

See the attachmentment.

Attachment output is great. I am liking that notation a lot more now.

I am most curious about the case [2 2 2] (06) (17) (89), which corresponds by cube rotation z'y' to [2 2 2] (01) (68) (79) on your list. It would be nice to get some algs for that case.
 

Christopher Mowla

Premium Member
Joined
Sep 17, 2009
Messages
1,184
Location
Earth
YouTube
Visit Channel
Hey Bruce, can you calculate {total permutations, count reduced by cube rotations} for the nxnxn cube for the set of all products of disjoint 2-cycles in 8 objects, 12 objects, and 24 objects?

For example,

The total unabridged amount of disjoint 2-cycle permutations in 8 objects is:
1 2–cycle: 28
2 2-cycles: 210
3 2-cycles: 420
4 2-cycles: 105
I know that you and Lucas have already calculated 58 for the total count reduced by cube rotations for 2 2-cycles and 8 for 2-cycles.

The total unabridged amount of disjoint 2-cycle permutations in 12 objects is:
1 2–cycle: 66
2 2-cycles: 1485
3 2-cycles: 13860
4 2-cycles: 51975
5 2-cycles: 62370
6 2-cycles: 10395

The total unabridged amount of disjoint 2-cycle permutations in 24 objects is:
1 2–cycle: 276
2 2-cycles: 31878
3 2-cycles: 2018940
4 2-cycles: 77224455
5 2-cycles: 1853386920
6 2-cycles: 28109701620
7 2-cycles: 265034329560
8 2-cycles: 1490818103775
9 2-cycles: 4638100767300
10 2-cycles: 6957151150950
11 2-cycles: 3794809718700
12 2-cycles: 316234143225
 
Last edited:

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
Hey Bruce, can you calculate {total permutations, count reduced by cube rotations} for the nxnxn cube for the set of all products of disjoint 2-cycles in 8 objects, 12 objects, and 24 objects?

The numbers for the 24 objects case are quite large. The way I normally compute these types of things in GAP would require too much memory, to say nothing about what the runtime might be. It might be possible to use the so-called Burnside lemma to compute them. But the cases for 8 and 12 objects should be no problem. I guess I am to assume you want this for 8 LL edges, 12 dedges or middle edges on odd size cube, and all 24 edges.
 
Last edited:

Christopher Mowla

Premium Member
Joined
Sep 17, 2009
Messages
1,184
Location
Earth
YouTube
Visit Channel
Thanks for the quick response. I actually want this for 8 corners, 12 middle edges on odd size cubes, and all big cube parts (wings, and all orbits of centers). I didn't think about it before, but maybe it matters which piece types these are for (maybe there would have to be a calculation for the orbit of X-centers, + centers, oblique centers, and wing edges?). I'm glad you mentioned that. Whatever you can do without too much trouble will be fine (anything is better than nothing...and if for some reason you don't have time to do this, then that's okay as well).
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
For now, I've got numbers for 8 LL wing edges (any 1 orbit):

1 2-cycle: 8 (6)
2 2-cycles: 58 (38)
3 2-cycles: 112 (70)
4 2-cycles: 35 (30)

Numbers in parentheses include reducing by mirroring.

EDIT #1:
For the corners, ignoring orientation, I come up with these numbers.

1 2-cycle: 3 (3)
2 2-cycles: 16 (12)
3 2-cycles: 29 (20)
4 2-cycles: 16 (12)

EDIT #2:
For 12 middle-edge pieces, ignoring orientation, I get these numbers.

1 2-cycle: 5 (4)
2 2-cycles: 77 (47)
3 2-cycles: 626 (338)
4 2-cycles: 2265 (1182)
5 2-cycles: 2711 (1406)
6 2-cycles: 507 (278)
 
Last edited:

Christopher Mowla

Premium Member
Joined
Sep 17, 2009
Messages
1,184
Location
Earth
YouTube
Visit Channel
Thanks, Bruce. These numbers are a lot less than the "unabridged" numbers for permutations in general. That's excellent news. If you ever decide to compute the numbers for 24 objects (which might be 4 times as hard as what I initially thought, if you would need to do calculations for 4 different piece types), I will never lose my curiosity to see those numbers. Thanks again.
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
Thanks, Bruce. These numbers are a lot less than the "unabridged" numbers for permutations in general. That's excellent news. If you ever decide to compute the numbers for 24 objects (which might be 4 times as hard as what I initially thought, if you would need to do calculations for 4 different piece types), I will never lose my curiosity to see those numbers. Thanks again.

Generally speaking, when you reduce cases by symmetries like this, the number of reduced cases will be roughly the number of unabridged cases (as you call them) divided by the number of symmetries. More specifically, this quotient will be a lower bound. As the number of cases gets larger, the percentage accuracy of this calculation seems to get better and better.

So for the 24-piece orbits, divide the unabridged numbers by 24 (the number of rotational symmetries of a cube) and you should get a number that's pretty close to the true answer.

I note that for corners and middle edges, I have ignored orientation. So UF<=>UB is considered equivalent to UF<=>BU, for example. If you want to treat these as distinct, the number of unabridged cases as well as the number of reduced cases will of course be higher.

I also note that you seem to be considering the centers (in an orbit) as 24 distinct objects, or at least that you are able track precisely how pieces are moved around, even though the standard puzzles may have indistinguishable pieces. (Said another way, we're talking about permutations and cycles, not about the visibly distinct states of the puzzle.)
 
Top