Unsolved Views: 45169
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.
/* 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;
}
//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;
}
}
/*
* 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 ());
}
}
}
Offline 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.
/* 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
//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; } }
/* * 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 ()); } } }
Offline 
Offline 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
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// just to check the numbers are right
long totalcombs(int n, int r){
long c=1;
if (r > n) return 0;
for (long d=1; d <= r; d++) {
c *= n--;
c /= d;
}
return c;
}
// example code to get all combination
int main(){
vector<int> indx;
string alpha("ABCDEFGHIJKLMNOPQRSTUVWXYZ");
int n=26;
int j=1;
int k=26;
for(int twk=j;twk<=k;twk++){
int r=twk;
int total=totalcombs(n,r);
int ccount=1;
bool done=true;
for(int iwk=0;iwk<r;iwk++)indx.push_back(iwk);
while(done){
done=false;
cout << ccount++ << " of " << total << " ";
for(int owk=0;owk<r;owk++){
cout << alpha[indx[owk]] << " ";
}
cout << endl;
for(int iwk=r-1;iwk>=0;iwk--){
if(indx[iwk]<=(n-1)-(r-iwk)){
indx[iwk]++;
for(int swk=iwk+1;swk<r;swk++){
indx[swk]=indx[swk-1]+1;
}
iwk=-1;
done=true;
}
}
}
cout << " --------------------------- " << endl;
indx.clear();
}
return 0;
}| DaniWeb Message | |
| Cancel Changes | |
