Combinatorial Algorithm
Hi,
I have a problem which i would like to see solved. I'm breaking heads over this problem for over 5 hours already, and because i'm not a mathematician i cannot find the solution.
I have a function like this:
publicint faculty (int number)
{
return (number == 1) ? 1 : number * faculty(number - 1);
}
publicint combinations (int n,int p)
{
return faculty(n) / (faculty(p) * faculty(n - p));
}
This calculates the number of possible combinations out of a set of elements.
Take this for example:
I have 5 (= n) ingredients, and i want to make a dish. For a dish i want to use 3 (= p) ingredients.
With these 5 ingredients there are 10 possible dishes that contain 3 of the 5 ingredients.
That is solved already.
Now i want a function which prints out these possible combinations in the form:
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE
(or sorted otherwise).
I can't get the correct for loops to deal with it.
The trick is, i had a discussion with my dad about the belgian lottery, and this also have to work for that.
I have to give an N parameter which is is the number of total elements, and P which is the number of elements in one combination.
In our lotery we have 42 number out of which we have to choose 6. That makes 5,245,786 possible combintions, and i would like to print these combinations on screen too, or any other kind of question i have concerning combinations.
Can anyone help me with this ? I'm baffeled...
[2053 byte] By [
Don_Stevo] at [2007-9-30 8:57:21]
Blatently stolen and modified from [url http://forum.java.sun.com/thread.jsp?forum=426&thread=397462]rkippen[/url]public class Test2 {
public static void main(String[] args) {
String[] elements = {"One","Two","Three","Four","Five"};
clique(elements, 0, 0, new Object[3]);
}
public static void clique(Object[] things, int i, int j, Object[] chosen) {
if (i == chosen.length) {
for (int k = 0; k < chosen.length; k++) {
System.out.print(chosen[k] + " ");
}
System.out.println();
} else {
for (int k = j; k <= (things.length - chosen.length) + i; k++) {
chosen[i] = things[k];
clique(things, i + 1, k + 1, chosen);
}
}
}
}
Your function for calculating combinations needs some re-thinking. If we calculate 13!, this value is larger than the largest value that can be represented with an int, 2^31. Thus, we can't use the implementation to calculate anything like combinations(42, 6). Fortunately, there are other ways to attack the problem. One way is with Pascal's triangle (Google for more information), e.g.,
public int combinations(n, p){
int[] pascals=new int[n+1];
pascals[0]=1;
for(int i=0; i < n; ++i){
pascals[i+1]=1;
for(int j=i; j > 0; --j){
pascals[j] += pascals[j-1];
}
}
return pascals[p];
}
> Your function for calculating combinations needs some re-thinking.
Here's some new code to just count the combinations in (42.6).public class Test2 {
static int cnt=0;
public static void main(String[] args) {
String[] elements = {"one","two","three","four","five","six","seven","eight",
"nine","ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen",
"seventeen","eighteen","nineteen","twenty","twenty-one","twenty-two",
"twenty-three","twenty-four","twenty-five","twenty-six","twenty-seven",
"twenty-eight","twenty-nine","thirty","thirty-one","thirty-two",
"thirty-three","thirty-four","thirty-five","thirty-six","thirty-seven",
"thirty-eight","thirty-nine","forty","forty-one","forty-two"};
long start = System.currentTimeMillis();
clique(elements, 0, 0, new Object[6]);
long end = System.currentTimeMillis();
System.out.println("cnt="+cnt+" (took "+(end-start)+"ms)");
}
public static void clique(Object[] things, int i, int j, Object[] chosen) {
if (i == chosen.length) {
/*for (int k = 0; k < chosen.length; k++) {
System.out.print(chosen[k] + " ");
}
System.out.println();*/
cnt++;
} else {
for (int k = j; k <= (things.length - chosen.length) + i; k++) {
chosen[i] = things[k];
clique(things, i + 1, k + 1, chosen);
}
}
}
}
It takes less than half a second on my computer. Here's the output
cnt=5245786 (took 438ms)
Whatchu talkin bout WIllis?
Whoops... You meant the OP's calculation, not mine. Ah-so.
Another way
class Combinations3From5
{
String str = "ABCDE";
public Combinations3From5()
{
int combo = 3;
int[] arr = new int[combo];
for(int i = 0; i < combo; i++) arr[i] = i;
getCombos(arr);
System.exit(0);
}
private void getCombos(int arr[])
{
String thisCombo = "";
for(int x = 0; x < arr.length ; x++) thisCombo += str.charAt(arr[x]);
System.out.println(thisCombo);
if(arr[0] == (str.length()-1)-(arr.length-1)) return;
if(arr[arr.length-1] == str.length()-1)
{
for(int i = 0; i < arr.length;i++)
{
if(arr[i] == (str.length()-1)-(arr.length-1-i))
{
arr[i-1]++;
for(int ii = i; ii < arr.length; ii++)
{
arr[ii] = arr[ii-1] + 1;
}
break;
}
}
}
else
{
arr[arr.length-1]++;
}
getCombos(arr);
}
public static void main(String[] args) {new Combinations3From5();}
}
> Another wayI got a stack overflow when I tried (42,6)
> > Another way
>
> I got a stack overflow when I tried (42,6)
Yes, and overflows at a lot less than (42,6)
This seems to work a bit better (not really tested though)
class Combinations3From5
{
String str = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnop";
//String str = "ABCDE";
int combo = 6;
//int combo = 3;
int[] arr = new int[combo];
public Combinations3From5()
{
for(int i = 0; i < combo; i++) arr[i] = i;
getCombos();
System.exit(0);
}
private void getCombos()
{
String thisCombo;
while(true)
{
thisCombo = "";
for(int x = 0; x < arr.length ; x++) thisCombo += str.charAt(arr[x]);
System.out.println(thisCombo);
if(arr[0] == (str.length()-1)-(arr.length-1))break;
if(arr[arr.length-1] == str.length()-1)
{
for(int i = 0; i < arr.length;i++)
{
if(arr[i] == (str.length()-1)-(arr.length-1-i))
{
arr[i-1]++;
for(int ii = i; ii < arr.length; ii++)
{
arr[ii] = arr[ii-1] + 1;
}
break;
}
}
}
else
{
arr[arr.length-1]++;
}
}
}
public static void main(String[] args) {new Combinations3From5();}
}
I guess i'm just an avergage java programmer, unable to solve anything mathematical ... :-s
Were my worst classes in secondary school, and even now when (if) i graduate this year, i hate the classes.
I've been trying to rework the code to print numbers instead of the letters (like this: 1-5-34-23-9-17)
I just tried to print the numerical values of the characters for now, i was going to rebuild them - 63 to start A from 1, and to put those '-' in between.
But it seems he doesn't handle those as strings anymore and just totals them ... and he puts a newline in between every number...maybe because it isn't like this in the array i don't know.
private void getCombos() {
String thisCombo;
while (true) {
thisCombo = "";
Character chr = new Character('1');
for (int x = 0; x < arr.length; x++)
chr = new Character(str.charAt(arr[x]));
Integer numericValue = new Integer(Character.getNumericValue(chr.charValue()));
thisCombo += numericValue.toString() + "-";
//for(int x = 0; x < arr.length ; x++)
//thisCombo += str.charAt(arr[x]);
System.out.println(thisCombo);
if (arr[0] == (str.length() - 1) - (arr.length - 1))
break;
if (arr[arr.length - 1] == str.length() - 1) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == (str.length() - 1) - (arr.length - 1 - i)) {
arr[i - 1]++;
for (int ii = i; ii < arr.length; ii++) {
arr[ii] = arr[ii - 1] + 1;
}
break;
}
}
} else {
arr[arr.length - 1]++;
}
}
}
What should i do to get numbers ? :-S
Here's another implementation, just for the fun of it -- class Combo implements Enumeration {
private int lo, hi, n;
private int[] c= null;
private int[] init() {
c= new int[n];
for (int i= 0, j= lo; i < n; c[i++]= j++);
return c;
}
private int findPivot() {
if (c == null) return 0;
for (int i= n; --i >= 0; )
if (c[i] <= hi-(n-i)) return i;
return -1;
}
public Combo(int lo, int hi, int n) {
this.lo= lo;
this.hi= hi;
this.n = n;
}
public boolean hasMoreElements() { return findPivot() >= 0; }
public Object nextElement() {
if (c == null) return init();
int i= findPivot();
if (i < 0) return null;
for (int j= c[i]; i < n; c[i++]= ++j);
return c;
}
}
If you want, say 6 numbers out of the range [ 1 ... 41 ], this is how it's done -- Combo cc= new Combo(1, 41, 6);
while (cc.hasMoreElements()) {
int[] c= (int[])cc.nextElement();
for (int i= 0; i < c.length; i++)
System.out.print(c[i]+" ");
System.out.println();
}
kind regards,
Jos
JosAH at 2007-7-2 20:34:17 >
Thx JosAH for that algorithm :-) it was exactly what i was looking for.
I guess 'ill try to find some information about that Enumeration interface over there and the functions you used.
It printed it exacly the way i wanted to.
Only :-) i guess my notebook has too low memory (i guess everyone's pc has) to print all this information in an orderly way...Somewhat about 800,000 it began to have problems and at 1,100,000 IntelliJ and my notebook gave up and gave errors and crashed.
But either way :-) it works...going to try to get this to PHP to put it on a site, or maybe in JSP or something, guess i'll take JSP, now that i have this algorithm in Java.
Ty very much
> Only :-) i guess my notebook has too low memory (i guess everyone's pc has) to print all this information
> in an orderly way...Somewhat about 800,000 it began to have problems and at 1,100,000 IntelliJ and my
> notebook gave up and gave errors and crashed.
Ahhh ... too bad, because C(41, 6) is just a bit less than four and a half million combinations ... ;-)
If you used six integers per combination, that'll be just about a measle one hundred megabytes ...
kind regards,
Jos
JosAH at 2007-7-2 20:34:17 >
When I was creating an algorithm to compare characteristics of the elements of an array (of Set playing cards), I did the following:
//this function tests all the possible sets to see if there is a valid set. If so, it returns a value of true. If not, it returns a boolean value of false.
public boolean validSetExists()
{
boolean result = false;
int a = null;
int b = null;
int c = null;
int d = null;
int e = null;
int f = null;
int count1;
int count2;
int count3;
while ((result = false) && (count1 < 18))
{
for (count1 = 0;
count1 < 18, //18 is number of elements involved
count1 ++)
{
for (count2 = (count1 + 1),
count2 < 18,
count2 ++)
{
for (count3 = (count2 + 1),
count3 < 18,
count3 ++)
{
a = (count1 / 3); // Three is the number of columns in the array
b = (count1 % 3);
c = (count2 / 3);
d = (count2 % 3);
e = (count3 / 3);
f = (count3 % 3);
result = testSet(a,b,c,d,e,f);
}
}
}
return result;
}
return result;
}
This allows me to check each of the elements currently in the array (it changes often in my application), by finding ordered pairs based on my counts, which should go through and check every combination by setting card 1 equal to the first element, and the second card equal to the second, and then iterating through each card after that for the third, and then repeating for each possible second card, and then for every possible first card.
