Algorithm help

[fenris]

I have been wrestling with this problem for a while and i can't seem to find any information on the internet about it.

The problem is this:
I have ten numbers (not necessarily sequential) and I want to print out all the 6 group combinations, ie 10 choose 6. I know the formula n_c_p = n!/(p!(n-p)!) which tells me how many combinations there are. I am stumped. It should also be able to handle arbritary n and p values ie, I should be able to input 25 numbers and have it generate all the 5 number combinations.

Any help would be appreciated. Pointers to websites would be appreciated as well

Thanks...

Troy Williams B.Eng.
fenris@hotmail.com

 

[Tom7]

Here's an algorithm I wrote. It's not very readable, but it works as follows:
Let's say, we have an array of five numbers: {1,2,3,4,5},
and we want to find all possible groups of three numbers. My algorithm goes through the combinations like we humans would probably do it:

helper array i[] = {1,2,3}

123 // increment i[2] as 3 < 5
124 // increment i[2] as 4 < 5
125 // increment i[1] and set i[2] = i[1]+1
134 // increment i[2]
135 // increment i[1] and set i[2] = i[1]+1
145 // increment i[0] and set i[1] = i[0]+1 and i[2]= i[0]+2
234 // etc...

Here's the code:

public class Combinations {
public static void main(String args[]) {
printCombinations(new int[] {1,2,3,4,5}, 3); // test
}
private boolean exit = false;

public static void printCombinations(int[] array, int p) {
int l = array.length;
if (p > l || l<1 || p<1) return; // illegal
int[] indices = new int[p];
for (int i=0; i<p; i++)
indices = i; // initializing indices
long counter = 1;

while(true) {
printArray(array, indices);
boolean exit = true;
for (int x = p-1; x >= 0; --x) {
int index = indices[x];
if (x == p-1) {
if (index == l-1) continue;
} else if (index == indices[x+1]-1) continue; // shift not possible
indices[x]++;
for (int y=x+1; y <= p-1; ++y)
indices[y] = indices[x]+(y-x);
exit = false;
counter++;
break;
}
if (exit) break;
}
System.out.println(&quot;\nThere were &quot;+counter+&quot; combinations&quot;

}

public static void printArray(int[] array, int[] indices) {
for (int i=0; i<indices.length; i++)
if (indices < array.length)
System.out.print(array[indices] + &quot; &quot;
System.out.println();
}
}


P.S. It should read

indices(i) = i; // initializing indices

with square brackets

 

[fenris]

Thank you for the reply, I appreciate it


Troy Williams B.Eng.
fenris@hotmail.com

 

[koundinya]

Tom7,
Your idea is really to be appreciated
Cheers