Originally Posted by ithelp

It is an NP complete problem , so you can only get some approximation algorithm to get it faster.

Originally Posted by iamthwee

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 ()); } } }