• 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 30,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)

Joined
Sep 17, 2009
Messages
849
Likes
19
Location
New Orleans, LA
YouTube
4EverTrying
Thread starter #1
Hello everyone,
I have made a document which shows why there are exactly 28 distinct cases for 3-cycles of winged edges restricted in the last layer of a 4X4X4 or 5X5X5 cube.

I know that many have known that there are 28 cases for a long time now (just as I have known, even before looking at Thom Barlow's webpage), but I wanted to introduce another (interesting) way to verify why there are 28 cases.

In the document, I also include an organized table of all 28 cases which may be useful for those just beginning to learn the K4 method. There are two of these tables: one is with Thom Barlow's algorithms, and the other is a table without any algorithms (for custom algorithms).
 

Attachments

Last edited:
Joined
Oct 8, 2006
Messages
914
Likes
15
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
cuBerBruce
#3
I look at it this way. There are 8 edges. A 3-cycle involves 3 of them. C(8,3)=8!/(3!*5!)=56.

For each 3 edges, there is a clockwise and a counterclockwise 3-cycle. 2*56= 112.

Since we're considering 3-cycles that are equivalent under a y-axis rotation, we have counted each case 4 times. 112/4=28.
 

Lucas Garron

Super-Duper Moderator
Staff member
Joined
Jul 6, 2007
Messages
3,551
Likes
81
Location
Where the rolling foothills rise
WCA
2006GARR01
YouTube
LucasGarron
#4
Nice. I've always been too scared of all the cases, but it doesn't look that bad after all.

Code:
Sort[Table[RotateRight[#,x],{x,0,6,2}]][[1]]&/@Permutations[{1,1,1,0,0,0,0,0}]//DeleteDuplicates//Length
Returns 14. :p

I love canonicalization. What the code above does:
  • Generate all the possibilities: Permutations[{1,1,1,0,0,0,0,0}]
  • Canonicalize each one by generating all the symmetries, sorting, and picking the canonically (think "alphabetically") first: Sort[Table[RotateRight[#,x],{x,0,6,2}]][[1]]&
  • Count the number of unique cases: //DeleteDuplicates//Length
 
Joined
Sep 17, 2009
Messages
849
Likes
19
Location
New Orleans, LA
YouTube
4EverTrying
Thread starter #5
I look at it this way. There are 8 edges. A 3-cycle involves 3 of them. C(8,3)=8!/(3!*5!)=56.

For each 3 edges, there is a clockwise and a counterclockwise 3-cycle. 2*56= 112.

Since we're considering 3-cycles that are equivalent under a y-axis rotation, we have counted each case 4 times. 112/4=28.
Well, that strategy works out for 3-cycles, but not for 4-cycles and 2 2-cycles (and by some thought, probably not for 2 3-cycles, 6-cycles, etc).



A Document for 4-cycles and 2 2-Cycles
 

Attachments

Last edited:
Joined
Feb 27, 2009
Messages
3,051
Likes
14
#7
Disregarding the permutation of the dedges, is it faster to solve 2 adjacent dedges, or 2 opposite dedges (after the other 2 have been solved)?
 
Joined
Oct 8, 2006
Messages
914
Likes
15
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
cuBerBruce
#8
Not so sure about the 120, but I think the 58 is right. Are you sure you counted correctly?
I used GAP to confirm that there are 58 cases for two 2-cycles. I also got 110 cases for 4-cycles. I think this agrees with Lucas. It seems he miscounted his rows.

cmowla, the proper way to write "n-cycle" is with a hyphen. You should say "4-cycles and 2 2-cycles" (or "4-cycles and two 2-cycles") rather than "4 cycles and 2-2 cycles." "4 cycles" (no hyphen) would imply you're talking about 4 separate cycles without any information about the lengths of those cycles. If you're creating a nice document as a resource for the cubing community, it would be nice to have things "spelled" properly.
 
Joined
Feb 27, 2009
Messages
3,051
Likes
14
#9
@ cmowla: What I was meaning is, consider the following;

-This is for 4x4 only (as of yet)
-All centers solved
-All dedges in D and E paired and oriented
-All dedges in U not paired

Now, which would be the most practical approach to finish the edge pairing, while making sure all edges are oriented, but disregarding the position of the dedges or corners?
 

Lucas Garron

Super-Duper Moderator
Staff member
Joined
Jul 6, 2007
Messages
3,551
Likes
81
Location
Where the rolling foothills rise
WCA
2006GARR01
YouTube
LucasGarron
#10
Yeah, 120 was a mistake when I typed it into my post. Will edit.

Number of n-cycles for 2 through 8:

{8, 28, 110, 336, 848, 1440, 1276}​

Not bad compared to Binomial[8, n]*(n - 1)!/4. The exceptions are not too insane, and it's nice to see that odd cycles have no rotational symmetry.
Estimates: {7, 28, 105, 336, 840, 1440, 1260}

Modding out by reflections:
{6, 14, 61, 168, 440, 720, 662}​

Modding out by reflections and inverses (the number of distinct algs that need to be found to have a solution for every case):
{6, 7, 38, 84, 250, 360, 391}​

Bruce, can you also verify these?

I would totally write some code to solve the general problem for cycle structures, but I've been procrastinating on homework enough by doing this.
 
Last edited:
Joined
Sep 17, 2009
Messages
849
Likes
19
Location
New Orleans, LA
YouTube
4EverTrying
Thread starter #12
Well, it depends on the scramble of the last 4 dedges. Since we are ignoring odd permutations, PLL parity, and are not picky where the winged edges pieces go (just pairing the dedges, not directly solving the dedges like in K4),

1) If there are 2 dedges incomplete,
Execute a 3-cycle that is between those two dedges only.

2) If there are 3 dedges incomplete,
Perform a 3-cycle that is between those 3 dedges.

3) If there are 4 dedges incomplete,
a) Perform a 3 cycle to complete one of the dedges.
b) Go to step 2.

For this scenario, it would be ideal if you knew all 44 two 2-cycle and 4 cycle algorithms which involve all 4 dedges (see the last main chart in my two 2-cycle/4-cycle document. That way, you only need to execute 1 algorithm to pair up all 4 dedges, but you said "practical", so I would go with the first option.
 
Last edited:
Joined
Feb 27, 2009
Messages
3,051
Likes
14
#13
So basically, it can be done with at most two 3-cycles? The first to pair at least one dedge, and the second to pair the remaining 2/3?
 
Joined
Oct 8, 2006
Messages
914
Likes
15
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
cuBerBruce
#14
Number of n-cycles for 2 through 8:

{8, 28, 110, 336, 848, 1440, 1276}​

Not bad compared to Binomial[8, n]*(n - 1)!/4. The exceptions are not too insane, and it's nice to see that odd cycles have no rotational symmetry.
Estimates: {7, 28, 105, 336, 840, 1440, 1260}

Modding out by reflections:
{6, 14, 61, 168, 440, 720, 662}​

Modding out by reflections and inverses (the number of distinct algs that need to be found to have a solution for every case):
{6, 7, 38, 84, 250, 360, 391}​

Bruce, can you also verify these?
Yes, I got the same results. I also did inverses without reflections, for completeness.

mod rotations only: [ 8, 28, 110, 336, 848, 1440, 1276 ]
modding out by reflections: [ 6, 14, 61, 168, 440, 720, 662 ]
modding out by inverses: [ 8, 14, 58, 168, 436, 720, 662 ]
modding out by reflections and inverses: [ 6, 7, 38, 84, 250, 360, 391 ]
 
Joined
Feb 27, 2009
Messages
3,051
Likes
14
#15
I guess so. Other people can tell you how they view it. That's basically what it comes down to, when viewing it from my perspective. You can also perform a 2-cycle alg if only two remain incomplete...I guess it's a matter of preference (and it only is because we are not even considering odd permutations).
Ok, thanks. Now I have to find a way to produce optimal speed algs for each case...or just use the ones from K4/KBCM.
 
Joined
Dec 11, 2009
Messages
294
Likes
0
#16
Nice. I've always been too scared of all the cases, but it doesn't look that bad after all.

Code:
Sort[Table[RotateRight[#,x],{x,0,6,2}]][[1]]&/@Permutations[{1,1,1,0,0,0,0,0}]//DeleteDuplicates//Length
Returns 14. :p

I love canonicalization. What the code above does:
  • Generate all the possibilities: Permutations[{1,1,1,0,0,0,0,0}]
  • Canonicalize each one by generating all the symmetries, sorting, and picking the canonically (think "alphabetically") first: Sort[Table[RotateRight[#,x],{x,0,6,2}]][[1]]&
  • Count the number of unique cases: //DeleteDuplicates//Length
The more canonicalizing the better!
Code:
 "CODE" tag must be parse failing on the imbedded "["'s ?
Nice work to all here, VERY useful diagrams are resulting. Wiki pages would be appropriate for much of this.
 
Last edited:
Joined
Dec 11, 2009
Messages
294
Likes
0
#17
Number of n-cycles for 2 through 8:

{8, 28, 110, 336, 848, 1440, 1276}​

Not bad compared to Binomial[8, n]*(n - 1)!/4. The exceptions are not too insane, and it's nice to see that odd cycles have no rotational symmetry.
Estimates: {7, 28, 105, 336, 840, 1440, 1260}

Modding out by reflections:
{6, 14, 61, 168, 440, 720, 662}​

Modding out by reflections and inverses (the number of distinct algs that need to be found to have a solution for every case):
{6, 7, 38, 84, 250, 360, 391}​

Bruce, can you also verify these?
Yes, I got the same results. I also did inverses without reflections, for completeness.

mod rotations only: [ 8, 28, 110, 336, 848, 1440, 1276 ]
modding out by reflections: [ 6, 14, 61, 168, 440, 720, 662 ]
modding out by inverses: [ 8, 14, 58, 168, 436, 720, 662 ]
modding out by reflections and inverses: [ 6, 7, 38, 84, 250, 360, 391 ]
Could you guys do this with added FR composite position (not just the 8 - U layer edges), and going out to 10-cycles? How about identifying those V.I.P. even#-cycle algs (2,4,6,8,10-cycle) that also keep all of the composite edges together?
 
Last edited:
Joined
Apr 6, 2007
Messages
560
Likes
2
WCA
2008SECH01
#18
((rR)2' F (rR)2 U2)2

and

((rR)2' F (rR)2 D2)2

(if i'm right, I have no 4x4x4 to check it and My fingers know it but my brain isn't so sure).
 
Joined
Oct 8, 2006
Messages
914
Likes
15
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
cuBerBruce
#19
Could you guys do this with added FR composite position (not just the 8 - U layer edges), and going out to 10-cycles? How about identifying those V.I.P. even#-cycle algs (2,4,6,8,10-cycle) that also keep all of the composite edges together?
Sorry if it's seemed like a lot of time to do these calculations. With the addition of a couple more edges, the number of permutations increases greatly. So while the calculations for 8 edges took only very few minutes, for 10 edges the calculation time increased to several hours.

I note that with the FR edges added, conjugations by U layer turns is used instead of conjugations by y-axis rotations.

So far, I've finished only the calculations for reducing cases by rotational symmetry. I'll plan to append additional results to the end of this post as I complete them.

For 10 edges, the number of cases for n-cycles for n={2,3,4,...,10} that involve at least 1 of the FR edges are:
{ 5, 32, 210, 1176, 5460, 20160, 55440, 100800, 90720 }

Adding in the previous results for 8 edges, the total numbers are:
{ 13, 60, 320, 1512, 6308, 21600, 56716, 100800, 90720 }

The above numbers include the cases of n-cycles that don't split up any pairs. The number of such cases that include permuting of the FR edges are:
{ 1, 0, 2, 0, 12, 0, 48, 0, 96 }

The total number of these n-cycle cases (whether or not FR edges are permuted) are:
{ 2, 0, 5, 0, 20, 0, 60, 0, 96 }

EDIT 1:
I note that I counted the number of 2-cycle cases that don't split up any edge pairs as 2. Those cases are (1) swapping the element in a U-layer edge pair, and (2) swapping the elements of the FR edge pair. Of course, these two cases could be viewed as the same thing. Generally, I could use cube rotations xy and y'x' to reduce cases that only involve the FR edge pair and 2 adjacent edge pairs in the U layer (assuming we're also allowing conjugation by U-layer moves; otherwise specifically the UF and UR edge pairs ). These symmetries have not been considered in my calculations. So the swapping of the two edges of a pair is counted as 2 cases instead of 1.

Results for counting reflections as the same case.

n-cycles involving at least one of the FR edges (for n=2,3,4,...,10):
{ 3, 16, 105, 588, 2730, 10080, 27720, 50400, 45360 }

total cases (for n=2,3,4,...,10):
{ 9, 30, 166, 756, 3170, 10800, 28382, 50400, 45360 }

n-cycles preserving edge pairing involving at least the FR edge pair:
{ 1, 0, 1, 0, 6, 0, 24, 0, 48 }

n-cycles preserving edge pairing (whether or not FR edges move):
{ 2, 0, 3, 0, 10, 0, 30, 0, 48 }

EDIT 2:

Results counting reflections and inverses as the same case.

n-cycles involving at least one of the FR edges (for n=2,3,4,...,10):
{ 3, 13, 55, 324, 1380, 5160, 13920, 25440, 22800 }

total cases (for n=2,3,4,...,10):
{ 9, 20, 93, 408, 1630, 5520, 14311, 25440, 22800 }

n-cycles preserving edge pairing involving at least the FR edge pair:
{ 1, 0, 1, 0, 5, 0, 14, 0, 30 }

n-cycles preserving edge pairing (whether or not FR edges move):
{ 2, 0, 3, 0, 8, 0, 20, 0, 30 }
 
Last edited:
Joined
Dec 11, 2009
Messages
294
Likes
0
#20
Could you guys do this with added FR composite position (not just the 8 - U layer edges), and going out to 10-cycles? How about identifying those V.I.P. even#-cycle algs (2,4,6,8,10-cycle) that also keep all of the composite edges together?
Sorry if it's seemed like a lot of time to do these calculations. With the addition of a couple more edges, the number of permutations increases greatly. So while the calculations for 8 edges took only very few minutes, for 10 edges the calculation time increased to several hours.

I note that with the FR edges added, conjugations by U layer turns is used instead of conjugations by y-axis rotations.

So far, I've finished only the calculations for reducing cases by rotational symmetry. I'll plan to append additional results to the end of this post as I complete them.

For 10 edges, the number of cases for n-cycles for n={2,3,4,...,10} that involve at least 1 of the FR edges are:
{ 5, 32, 210, 1176, 5460, 20160, 55440, 100800, 90720 }

Adding in the previous results for 8 edges, the total numbers are:
{ 13, 60, 320, 1512, 6308, 21600, 56716, 100800, 90720 }

The above numbers include the cases of n-cycles that don't split up any pairs. The number of such cases that include permuting of the FR edges are:
{ 1, 0, 2, 0, 12, 0, 48, 0, 96 }

The total number of these n-cycle cases (whether or not FR edges are permuted) are:
{ 2, 0, 5, 0, 20, 0, 60, 0, 96 }

EDIT 1:
I note that I counted the number of 2-cycle cases that don't split up any edge pairs as 2. Those cases are (1) swapping the element in a U-layer edge pair, and (2) swapping the elements of the FR edge pair. Of course, these two cases could be viewed as the same thing. Generally, I could use cube rotations xy and y'x' to reduce cases that only involve the FR edge pair and 2 adjacent edge pairs in the U layer (assuming we're also allowing conjugation by U-layer moves; otherwise specifically the UF and UR edge pairs ). These symmetries have not been considered in my calculations. So the swapping of the two edges of a pair is counted as 2 cases instead of 1.

Results for counting reflections as the same case.

n-cycles involving at least one of the FR edges (for n=2,3,4,...,10):
{ 3, 16, 105, 588, 2730, 10080, 27720, 50400, 45360 }

total cases (for n=2,3,4,...,10):
{ 9, 30, 166, 756, 3170, 10800, 28382, 50400, 45360 }

n-cycles preserving edge pairing involving at least the FR edge pair:
{ 1, 0, 1, 0, 6, 0, 24, 0, 48 }

n-cycles preserving edge pairing (whether or not FR edges move):
{ 2, 0, 3, 0, 10, 0, 30, 0, 48 }

EDIT 2:

Results counting reflections and inverses as the same case.

n-cycles involving at least one of the FR edges (for n=2,3,4,...,10):
{ 3, 13, 55, 324, 1380, 5160, 13920, 25440, 22800 }

total cases (for n=2,3,4,...,10):
{ 9, 20, 93, 408, 1630, 5520, 14311, 25440, 22800 }

n-cycles preserving edge pairing involving at least the FR edge pair:
{ 1, 0, 1, 0, 5, 0, 14, 0, 30 }

n-cycles preserving edge pairing (whether or not FR edges move):
{ 2, 0, 3, 0, 8, 0, 20, 0, 30 }

Thanks Bruce, this is a VERY fine piece of work!

I see great potential in reThinking the Cube's quest for even n-cycle possibilities, assuming that the ultimate goal is to find a scenario which can make room for a OLL parity algorithm which only messes up the last layer and a F2L slot......(snip)

I suspect that a two 4-cycle/one 2-cycle algorithm can be achieved using the conventional method, not just by the one which I used to find mine. Hence, in order to really see all of the possibilities, we can't just look for all distinct even cycle cases, but also look to odd multiples of 2-cycles, odd multiples of 2-cycles with an even number of double parity 4-cycles, and vice versa.
Good point, and you are right, but we also have to be careful, and not get away from the relevance to LLK4. Bruce's 100% correct answer for n-cycles preserving edge pairing (whether or not FR edges move): { 2, 0, 3, 0, 8, 0, 20, 0, 30 }. 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.

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.
 
Last edited:
Top