ch.randelshofer.rubik.solver
Class Combinatorials

java.lang.Object
  ch.randelshofer.rubik.solver.Combinatorials

public class Combinatorials
extends java.lang.Object

Combinatorial algorithms. This class has been derived from Combinat.cpp and Combinat.h from the 'Kociemba Cube Solver 1.0' (KCube) (c) Greg Schmidt.

Version:

0.0 2000-07-01

Author:

Werner Randelshofer, Hausmatt 10, CH-6045 Immensee, Switzerland

Constructor Summary

Combinatorials()

Method Summary

static int	NChooseM(int N, int M) N Choose M - Compute the number of ways a subset of N items can be selected from a set of M items.
static void	ordinalToPermutation(int ordinal, int[] vector, int off, int len, int offset) OrdinalToPermutation - Given an ordinal in the range (0,...n!-1) compute a unique permutation of n items.
static int	permutationToOrdinal(int[] vector, int off, int len) The following pair of permutation algorithms are based on a description in Knuth's "Fundamental Algorithms Volume 2: Seminumerical Algorithms" p64.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Combinatorials

public Combinatorials()

Method Detail

NChooseM

public static int NChooseM(int N,
                           int M)

N Choose M - Compute the number of ways a subset of N items can be selected from a set of M items. N must be greater than M. The formula for N choose M is: N! / (M! * (N-M)!) The N! / (N-M)! portion can be computed iteratively as: N * (N-1) * (N-2) * (N-3) * ... * (N-M+1) The M! portion can be divided out iteratively as: 1, 2, 3 ... M (i.e. first divide partial result by 1, then by 2, then by 3,...) Note that both require M iterations allowing the entire calculation to be performed within a single loop. Note also that we want to keep the numerator as large as possible during this calculation to avoid truncation error during the division. This is accomplished by performing the multiplication in descending order and the division in ascending order. Since N choose M is equivalent to N choose (N-M) we can take advantage of this property to optimize the calculation in cases where M > N/2 since using the equivalent form results in a smaller M recalling that M is the number of loop iterations. Note, the performance of this function could be improved by using a table of precomputed results (i.e. NChooseM[N][M]).

permutationToOrdinal

public static int permutationToOrdinal(int[] vector,
                                       int off,
                                       int len)

The following pair of permutation algorithms are based on a description in Knuth's "Fundamental Algorithms Volume 2: Seminumerical Algorithms" p64. PermutationToOrdinal - Given a permutation contained in a vector of length n, compute a unique ordinal in the range (0,...n!-1). This algorithm is based on the notion of a "factorial number system". An ordinal can be thought of as a number with a variable base, the sum of factorial terms, where each term is the product of a factorial and an associated coefficent. It generates the coefficients by finding the position of the largest, second largest, third largest, etc. elements in the permutation vector. Each time it finds the ith largest element, it exchanges that with the element at location i. Thus there are i possibilities for the position of the ith largest element. This process yields the i coefficients.

ordinalToPermutation

public static void ordinalToPermutation(int ordinal,
                                        int[] vector,
                                        int off,
                                        int len,
                                        int offset)

OrdinalToPermutation - Given an ordinal in the range (0,...n!-1) compute a unique permutation of n items. This algorithm is essentially the above algorithm run backwards. It uses modulo arithmetic and division to produce the coefficients that drive the exchanges.