0
$\begingroup$

I'm developing a Rubik's Cube Solver and require a pruning table for Kociemba's G1 to G2. I already have a table but the search is still very slow...

I have 4 edge permutation values and I need to calculate all 4! indices for these possible edge permutations. How do I do this as this logic can carry over to other slices of the cube and corners too?

TLDR; I need to return the lexicographical index of 4 numbers out of 12. 12C4. Except I only want the 24 perms where the 4 numbers are 1, 2, 3, 4.

Any recommendations or suggestions are much appreciated. Thank you

$\endgroup$

1 Answer 1

0
$\begingroup$

$3!$ of the permutations start with each number, so the index is $6$ times the first element minus $1$ (because you start counting from $1$) plus the index of the permutation of the last three elements. This suggests a recursive approach-add the impact of the first number to the index of the rest. For example, if the permutation is $3142$ you get $3! \cdot (3-1)=12$ from the $3$. You get $2! \cdot (1-1)=0$ from the $1$ because it is the first of what is left. You get $1$ from the $42$ if your indices start at $0$, for a total of $13$

$\endgroup$
2
  • $\begingroup$ Hi there, thanks for the response. I hate to say this but I'm not quite following. From what I understand... if I wanted to find the permutation for 2431... I'd do 3! * (2-1) = 6. .. $\endgroup$ Commented Apr 25, 2021 at 15:04
  • $\begingroup$ That is right, then you want the index of $431$ among the $3!$ permutations of the last three numbers. You can see it is $5$, the last, or you would do $2!(3-1)=4$ because $4$ is the third number that is left and add $1$ because $31$ is the second one of the two element permutations, getting $11$. Between this and $3142$ is $3124$, so it checks. $\endgroup$ Commented Apr 25, 2021 at 15:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .