Kociemba - 2 phase alg

[deadalnix]

Hi, I wantto start a thread about kociemba 2 phase alg.

The base of the method is largely explained on tthis website : http://kociemba.org/cube.htm

But theyre is a point that I don't get at all. It's about UDSlice coord : http://kociemba.org/math/UDSliceCoord.htm

I have understood how to calculate the coord, it works and fine but, what the hell does it means ? Why C(n,k) is used here ? How can we make a reverse function (that give the edges position from the UD slic coord) ?

 

[Johannes91]

So we want to convert a list of N bits with K ones (and N-K zeros) to a number (I call it an index) in the range [0, C(n,k)). Here's a list of all combinations with (N = 5, K = 2):

0 0 0 1 1 (index = 0)
0 0 1 0 1 (index = 1)
0 0 1 1 0 (index = 2)
0 1 0 0 1 (index = 3)
0 1 0 1 0 (index = 4)
0 1 1 0 0 (index = 5)
1 0 0 0 1 (index = 6)
1 0 0 1 0 (index = 7)
1 0 1 0 0 (index = 8)
1 1 0 0 0 (index = 9)

It's easy if you think about it recursively. The lists where the first bit is zero come before the lists where it's one.

Here's a function that converts those lists to indices in math-like notation.

comb2index(N,K,()) = 0
comb2index(N,K,(0,bs)) = comb2index(N-1,K,bs)
comb2index(N,K,(1,bs)) = C(N-1,K) + comb2index(N-1,K-1,bs)

The base case is the empty list, its index is zero. If the first bit is zero, we just ignore it; if it's one, we add C(N-1,K). That's the number of lists where the first bit is zero.

Then the other direction.

index2comb(0,K,i) = ()
index2comb(N,K,i) = let c = C(N-1,K-1)
                    if i < c
                    then (0, index2comb(N-1,K,i))
                    else (1, index2comb(N-1,K-1,i-c))

Here the base case is N=0 and its value is the empty list.

Or, in Haskell:

fact :: Integer -> Integer
fact n = product [1 .. n]

choose :: Integer -> Integer -> Integer
choose n k
   | k > n     = 0
   | otherwise = fact n `div` (fact k * fact (n - k))

comb2index :: Integer -> Integer -> [Integer] -> Integer
comb2index n k _
   | min n k <= 0     = 0
comb2index n k (0:bs) = comb2index (n - 1) k bs
comb2index n k (1:bs) = comb2index (n - 1) (k - 1) bs + choose (n - 1) k

index2comb :: Integer -> Integer -> Integer -> [Integer]
index2comb 0 _ _ = []
index2comb n k index
   | index >= c  = 1 : index2comb (n - 1) (k - 1) (index - c)
   | otherwise   = 0 : index2comb (n - 1) k index
   where
   c = choose (n - 1) k

Testing:

*Main> comb2index 12 4 [1,1,1,1,0,0,0,0,0,0,0,0]
494
*Main> index2comb 12 4 494
[1,1,1,1,0,0,0,0,0,0,0,0]
*Main> index2comb 12 4 0
[0,0,0,0,0,0,0,0,1,1,1,1]
*Main> map (comb2index 5 2 . index2comb 5 2) [0 .. choose 5 2 - 1]
[0,1,2,3,4,5,6,7,8,9]

Not sure if that helps at all. Jaap's site has weird pseudo-code but no explanation: http://www.jaapsch.net/puzzles/compindx.htm#comb.

It's not hard to generalize to lists with more than 2 different elements. It can be done very similarly using recursion, one element at a time.

 

[deadalnix]

Your explaination is very clear.

And, even if it's not the same system than Kociemba's, it make me understand Kociemba's as well.

The system is very similar.

Kociemba is incrementing on 0 values. The value added is the number of cases where theyre is an 1 in this position instead of a 0.

In both system, you just add recursively the number of case you have « before », but the « before » definition isn't the same.

Ok, let's start another question : What about kociemba on 4x4x4 ? I haven't found anything about this except people trying to make reduction then kociemba solve on 3x3x3.

I'm a little confused with information to use to qualify the cube in several phases.

The goal of phase 1 :
-Centers are on opposites faces. So center can have 3 values in phase 1, corresponding to centers goal directions (x y or z). 2 in phase 2 : correct center or opposite.
-Wing have to be splitted in two subgroups. Phase 1 have to put every wing in his subgroup. In phase 2, this is 2 standard permutations.
-For corners, nothing changes.

I gess that phase 2 centers is very similar to phase 1 wings (in term of metric).

Let's think about the wing metric for phase 1. The first 12 subgroup have 2^12 possibilities (4096). But the 12 remaining wings have to have the same number of wing in the wrong subgroup.

So we need a c(n,k) solution. The maximal value is 924 if I'm not wrong. That make the number of option 924*4096 which is very close to 2x2x2 numbers of case (and the god alg for 2x2x2 is really fast to produce).

The problem with this metric is that many id are not used. 924 only occurs when 6 wing are in the wrong subgroup. In all the cases, the value is smaller (494 for 4 wings in the wrong subgroup).

Another solution I think about is using 2 c(n,k) solutions and one numbers of wing wrong index. I think we could get a smaller ammount of cases theyre, but I doesn't succed in formalizing it.

I have some other interrogatiin about kociemba, I think I will use this thread for all. For exemple, how to reduce pruning tables with symetries ? With a transition tabes like for moves ?

Or how to handle pieces where orientation doesn't matter ? I think I have to study ACube to have some informations about that.

 

[Johannes91]

Ok, let's start another question : What about kociemba on 4x4x4 ? I haven't found anything about this except people trying to make reduction then kociemba solve on 3x3x3.

Searching for 4x4x4 here finds something on Thistlethwaite/Kociemba style algorithms. Usually they use around 5 phases.

Let's think about the wing metric for phase 1. The first 12 subgroup have 2^12 possibilities (4096). But the 12 remaining wings have to have the same number of wing in the wrong subgroup.
[..]
Another solution I think about is using 2 c(n,k) solutions and one numbers of wing wrong index. I think we could get a smaller ammount of cases theyre, but I doesn't succed in formalizing it.

Why not just one? C(24,12) = 2,704,156 or C(24,8) = 735,471 (not sure what 2 subgroups you meant). The number of combinations is small, I don't see a reason to do anything so complicated.

 

[deadalnix]

Good website. I knew it but they are many results theyre but not so many explainations :/

With theses moves, you can move wings only in a 12 wings subset. In phase 1, we have to put each wings in the good subset.

We can have any number of wing in the wrong subset from 0 to 12. But then, if theyre is N incorrect wings in the subset 1, you have also N incorrect edges in the subset 2.

The possibilities in one subset are 2^12 (12 wing that can be in the good or the incorrect subset).

But then, the number of cases in the other subset depends on the case in subset 1. The C(24,12) idea works for wing, but not for centers (C(24,8)) because we have 3 groups of centers.

A generalisation of the c(n,k) concept for numbering the situation in needed, but with 0,1 and 2. Maybe calculating it in 2 steps can do the trick => C(24,8)*C(16,8) for centers. This is explosive ! The 12! for wings in phase 2 is explosive also.

So 3 steps at least is needed. I gess if they do 5 it's not for nothing, but I like to understand

I think I come up with some idea about 4x4x4 but I need to clarify my mind about it.

Lets go on reducing memory usage with symetries. I have no clue how to do that also . . .