Dear all,

I am looking for an expert opinion on what the fastest combination generator is. I am currently facing a problem of generating a huge combinations (k elements out of n) and as it stands now, the running time of my program will take more than three years. My current implementation uses the Algorithm R (see Knuth's book pre-fascicle 3a), a revolving-door algorithm.

If anyone knows a better/faster way of enumerating combinations, please let me know. Many thanks.

Well unless you have access to a quantum computer I doubt you will be able to cut down on run time. Knuth's work is generally accepted as being the best for algorithms and reducing time complexity.

However, you may be looking at your problem in the wrong way. Take for example the classic travelling salesman problem.

Applying a brute force algorithm to calculate the shortest route for a journey with 100+ pit-stops will take an unfathomable amount of time.

However, if you adopt a heuristic approach you can find a high probabilistic solution,within a much smaller time scale.

Perhaps you need to think about approaching your problem from a different angle.

See this:

http://en.wikipedia.org/wiki/Dynamic_programming

Incase anyone wanted to know here is Knuth's algorithm for producing combinations in C.

Help with Code Tags

(Toggle Plain Text)

 
/* Algorithm by Donald Knuth. */
 
#include <stdio.h>
#include <stdlib.h> 
void main( void)
{
	int i, j=1, k, n, *c, x;
	printf( "Enter n,k: ");
	scanf( "%d,%d", &n, &k);
	c = malloc( (k+3) * sizeof(int));
 
	for (i=1; i <= k; i++) c[i] = i;
	c[k+1] = n+1;
	c[k+2] = 0;
	j = k;
visit:
	for (i=k; i >= 1; i--) printf( "%3d", c[i]);
	printf( "\n");
	if (j > 0) {x = j+1; goto incr;}
	if (c[1] + 1 < c[2])
	 {
	 c[1] += 1;
	 goto visit;
	 }
	j = 2;
do_more:
	c[j-1] = j-1;
	x = c[j] + 1;
	if (x == c[j+1]) {j++; goto do_more;}
	if (j > k) exit(0);
incr:
	c[j] = x;
	j--;
	goto visit;
}

/* Algorithm by Donald Knuth. */ #include <stdio.h> #include <stdlib.h> void main( void) { int i, j=1, k, n, *c, x; printf( "Enter n,k: "); scanf( "%d,%d", &n, &k); c = malloc( (k+3) * sizeof(int)); for (i=1; i <= k; i++) c[i] = i; c[k+1] = n+1; c[k+2] = 0; j = k; visit: for (i=k; i >= 1; i--) printf( "%3d", c[i]); printf( "\n"); if (j > 0) {x = j+1; goto incr;} if (c[1] + 1 < c[2]) { c[1] += 1; goto visit; } j = 2; do_more: c[j-1] = j-1; x = c[j] + 1; if (x == c[j+1]) {j++; goto do_more;} if (j > k) exit(0); incr: c[j] = x; j--; goto visit; }

And java

Help with Code Tags

(Toggle Plain Text)

 
//CombinationGenerator.java
//--------------------------------------
// Systematically generate combinations.
//--------------------------------------
import java.math.BigInteger;
public class CombinationGenerator {
private int[] a;
private int n;
private int r;
private BigInteger numLeft;
private BigInteger total;
//------------
// Constructor
//------------
public CombinationGenerator (int n, int r) {
	if (r > n) {
	 throw new IllegalArgumentException ();
	}
	if (n < 1) {
	 throw new IllegalArgumentException ();
	}
	this.n = n;
	this.r = r;
	a = new int[r];
	BigInteger nFact = getFactorial (n);
	BigInteger rFact = getFactorial (r);
	BigInteger nminusrFact = getFactorial (n - r);
	total = nFact.divide (rFact.multiply (nminusrFact));
	reset ();
}
//------
// Reset
//------
public void reset () {
	for (int i = 0; i < a.length; i++) {
	 a[i] = i;
	}
	numLeft = new BigInteger (total.toString ());
}
//------------------------------------------------
// Return number of combinations not yet generated
//------------------------------------------------
public BigInteger getNumLeft () {
	return numLeft;
}
//-----------------------------
// Are there more combinations?
//-----------------------------
public boolean hasMore () {
	return numLeft.compareTo (BigInteger.ZERO) == 1;
}
//------------------------------------
// Return total number of combinations
//------------------------------------
public BigInteger getTotal () {
	return total;
}
//------------------
// Compute factorial
//------------------
private static BigInteger getFactorial (int n) {
	BigInteger fact = BigInteger.ONE;
	for (int i = n; i > 1; i--) {
	 fact = fact.multiply (new BigInteger (Integer.toString (i)));
	}
	return fact;
}
//--------------------------------------------------------
// Generate next combination (algorithm from Rosen p. 286)
//--------------------------------------------------------
public int[] getNext () {
	if (numLeft.equals (total)) {
	 numLeft = numLeft.subtract (BigInteger.ONE);
	 return a;
	}
	int i = r - 1;
	while (a[i] == n - r + i) {
	 i--;
	}
	a[i] = a[i] + 1;
	for (int j = i + 1; j < r; j++) {
	 a[j] = a[i] + j - i;
	}
	numLeft = numLeft.subtract (BigInteger.ONE);
	return a;
}
}

//CombinationGenerator.java //-------------------------------------- // Systematically generate combinations. //-------------------------------------- import java.math.BigInteger; public class CombinationGenerator { private int[] a; private int n; private int r; private BigInteger numLeft; private BigInteger total; //------------ // Constructor //------------ public CombinationGenerator (int n, int r) { if (r > n) { throw new IllegalArgumentException (); } if (n < 1) { throw new IllegalArgumentException (); } this.n = n; this.r = r; a = new int[r]; BigInteger nFact = getFactorial (n); BigInteger rFact = getFactorial (r); BigInteger nminusrFact = getFactorial (n - r); total = nFact.divide (rFact.multiply (nminusrFact)); reset (); } //------ // Reset //------ public void reset () { for (int i = 0; i < a.length; i++) { a[i] = i; } numLeft = new BigInteger (total.toString ()); } //------------------------------------------------ // Return number of combinations not yet generated //------------------------------------------------ public BigInteger getNumLeft () { return numLeft; } //----------------------------- // Are there more combinations? //----------------------------- public boolean hasMore () { return numLeft.compareTo (BigInteger.ZERO) == 1; } //------------------------------------ // Return total number of combinations //------------------------------------ public BigInteger getTotal () { return total; } //------------------ // Compute factorial //------------------ private static BigInteger getFactorial (int n) { BigInteger fact = BigInteger.ONE; for (int i = n; i > 1; i--) { fact = fact.multiply (new BigInteger (Integer.toString (i))); } return fact; } //-------------------------------------------------------- // Generate next combination (algorithm from Rosen p. 286) //-------------------------------------------------------- public int[] getNext () { if (numLeft.equals (total)) { numLeft = numLeft.subtract (BigInteger.ONE); return a; } int i = r - 1; while (a[i] == n - r + i) { i--; } a[i] = a[i] + 1; for (int j = i + 1; j < r; j++) { a[j] = a[i] + j - i; } numLeft = numLeft.subtract (BigInteger.ONE); return a; } }

Help with Code Tags

(Toggle Plain Text)

 
/*
* test.java
*
* Created on 14 January 2006, 16:29
*/
/**
*
* @author iamthwee
*/
public class test {
 
	/** Creates a new instance of test */
	public test() {
	}
 
	/**
	 * @param args the command line arguments
	 */
	public static void main(String[] args) {
		String[] elements = {"a", "b","c","d"};
int[] indices;
CombinationGenerator x = new CombinationGenerator (elements.length, 2);
StringBuffer combination;
while (x.hasMore ()) {
combination = new StringBuffer ();
indices = x.getNext ();
for (int i = 0; i < indices.length; i++) {
	combination.append (elements[indices[i]]);
}
System.out.println (combination.toString ());
}
 
	}
 
}

/* * test.java * * Created on 14 January 2006, 16:29 */ /** * * @author iamthwee */ public class test { /** Creates a new instance of test */ public test() { } /** * @param args the command line arguments */ public static void main(String[] args) { String[] elements = {"a", "b","c","d"}; int[] indices; CombinationGenerator x = new CombinationGenerator (elements.length, 2); StringBuffer combination; while (x.hasMore ()) { combination = new StringBuffer (); indices = x.getNext (); for (int i = 0; i < indices.length; i++) { combination.append (elements[indices[i]]); } System.out.println (combination.toString ()); } } }

Hi,

Do you need a solution which is in a smaller time complexity class than Knuth's or have a bound for n,k and just need a faster code to get it done in less than 3 years ? +what is the maximum acceptable time span for you ? because I have some ideas for optimization which can reduce your 3 year but not for n limit to infinity.

Loren Soth