# simple combination

Hi All,
:
: I am having a big math problem and would really appreciate some help.
anyway.

i want to generate all the combinations where
n = 20 ie. 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 and
r = 5

1)i known the amount of different combinations it have 15504, but i want to generate the sets of numbers.
eg. 1,3,5,7,9 -- this is a set because it has 5 numbers
2,7,10,19,20 -- this is also correct.

2) in a given set like the ones above a digit can only be used once in a set.
eg 2,5,7,2,19 this is wrong because the number 2 is repeated.

thanks everyone.

• [b][red]This message was edited by Bodkin at 2006-1-23 4:36:19[/red][/b][hr]
Principle:
The first combination is simply made by assigning consecutive values to the r numbers,
ie number[1] = 1, number[2] = 2, ... , number[r] = r

The following combinations are made by increasing the highest indexed number that can be increased,
ie For r=5 the highest index is 5, if number[5] is less than n then it can be increased and a new combination has been found.
If number[5] equals n then it cannot be increased, so the next highest number is increased , ie number[4]=number[4]+1 and the value of following higher indexes are assigned consecutive values, ie. number[5]=number[4]+1, number[6]=number[5]+1, etc. and a new combination has been found.
A number can only be increased if number[index] < n-r+index
If none of the numbers can be increased then no more combinations can be found.

eg for n=20, r=5
[CODE]
index
| 1 | 2 | 3 | 4 | 5 |
combination ---------------------
| 1 | 2 | 3 | 4 | 19| number[5] < n-r+5? => number[5] < 20? YES => increase IS possible. Next combination = 1,2,3,4,20

| 1 | 2 | 3 | 4 | 20| number[5] < n-r+5? => number[5] < 20? NO => increase IS NOT possible.
number[4] < n-r+4? => number[4] < 19? YES => increase IS possible. Next combination = 1,2,3,5,6

| 1 | 2 | 3 | 19| 20| number[5] < n-r+5? => number[5] < 20? NO => increase IS NOT possible.
number[4] < n-r+4? => number[4] < 19? NO => increase IS NOT possible.
number[3] < n-r+3? => number[3] < 18? YES => increase IS possible. Next combination = 1,2,4,5,6
[/CODE]

This code should be easily ported to other languages.
Remarks:
The [italic]number[/italic] array mentioned above is called [italic]combination[/italic] in the code.
In the explanation above [italic]number[/italic] is indexed from 1 to r, in the code below the index goes from 0 to r-1, hence the use of [leftbr]index-1[rightbr] and [leftbr]index-2[rightbr].
[CODE]

n = 20
r = 5

var combination = new Array(r);

for(i=0; i r)
index = r;
while(combination[leftbr]index-1[rightbr]==n+index-r && index>0)
index--;
if(index==0)
return false;
combination[leftbr]index-1[rightbr]++;
for(index++; index

[/CODE]

• Thanks, but the program is still not working. your principle is great but the version i have is not compatible.

the

:
:
in the begining and end makes no difference and i cannot find the error to end the file.

: [b][red]This message was edited by Bodkin at 2006-1-23 4:36:19[/red][/b][hr]
: Principle:
: The first combination is simply made by assigning consecutive values to the r numbers,
: ie number[1] = 1, number[2] = 2, ... , number[r] = r
:
: The following combinations are made by increasing the highest indexed number that can be increased,
: ie For r=5 the highest index is 5, if number[5] is less than n then it can be increased and a new combination has been found.
: If number[5] equals n then it cannot be increased, so the next highest number is increased , ie number[4]=number[4]+1 and the value of following higher indexes are assigned consecutive values, ie. number[5]=number[4]+1, number[6]=number[5]+1, etc. and a new combination has been found.
: A number can only be increased if number[index] < n-r+index
: If none of the numbers can be increased then no more combinations can be found.
:
: eg for n=20, r=5
: [CODE]
: index
: | 1 | 2 | 3 | 4 | 5 |
: combination ---------------------
: | 1 | 2 | 3 | 4 | 19| number[5] < n-r+5? => number[5] < 20? YES => increase IS possible. Next combination = 1,2,3,4,20
:
: | 1 | 2 | 3 | 4 | 20| number[5] < n-r+5? => number[5] < 20? NO => increase IS NOT possible.
: number[4] < n-r+4? => number[4] < 19? YES => increase IS possible. Next combination = 1,2,3,5,6
:
: | 1 | 2 | 3 | 19| 20| number[5] < n-r+5? => number[5] < 20? NO => increase IS NOT possible.
: number[4] < n-r+4? => number[4] < 19? NO => increase IS NOT possible.
: number[3] < n-r+3? => number[3] < 18? YES => increase IS possible. Next combination = 1,2,4,5,6
: [/CODE]
:
: This code should be easily ported to other languages.
: Remarks:
: The [italic]number[/italic] array mentioned above is called [italic]combination[/italic] in the code.
: In the explanation above [italic]number[/italic] is indexed from 1 to r, in the code below the index goes from 0 to r-1, hence the use of [leftbr]index-1[rightbr] and [leftbr]index-2[rightbr].
: [CODE]
:
:
:
: n = 20
: r = 5
:
: var combination = new Array(r);
:
: for(i=0; i r)
: index = r;
: while(combination[leftbr]index-1[rightbr]==n+index-r && index>0)
: index--;
: if(index==0)
: return false;
: combination[leftbr]index-1[rightbr]++;
: for(index++; index<=r; index++)
: combination[leftbr]index-1[rightbr] = combination[leftbr]index-2[rightbr]+1;
: }
: return true;
: }
: function showNext() {
: val = getNextCombination(n, r);
: if(!val) // No more combinations found
: return val;
:
: txt = "";
: for(i in combination)
: txt+=combination[leftbr]i[rightbr]+", ";
:
: // Show the combination somewhere
: window.status = txt;
:
:
: return val;
: }
: function init() {
: for(p=0; p<50000 && showNext(); p++); // Shows the first 50000 combinations or as many as there are
: }
: </script>
:
:
:
:
: [/CODE]
:

• i got it to work but cannot print it, have any ideas:

[b][red]This message was edited by Bodkin at 2006-1-23 4:36:19[/red][/b][hr]
: Principle:
: The first combination is simply made by assigning consecutive values to the r numbers,
: ie number[1] = 1, number[2] = 2, ... , number[r] = r
:
: The following combinations are made by increasing the highest indexed number that can be increased,
: ie For r=5 the highest index is 5, if number[5] is less than n then it can be increased and a new combination has been found.
: If number[5] equals n then it cannot be increased, so the next highest number is increased , ie number[4]=number[4]+1 and the value of following higher indexes are assigned consecutive values, ie. number[5]=number[4]+1, number[6]=number[5]+1, etc. and a new combination has been found.
: A number can only be increased if number[index] < n-r+index
: If none of the numbers can be increased then no more combinations can be found.
:
: eg for n=20, r=5
: [CODE]
: index
: | 1 | 2 | 3 | 4 | 5 |
: combination ---------------------
: | 1 | 2 | 3 | 4 | 19| number[5] < n-r+5? => number[5] < 20? YES => increase IS possible. Next combination = 1,2,3,4,20
:
: | 1 | 2 | 3 | 4 | 20| number[5] < n-r+5? => number[5] < 20? NO => increase IS NOT possible.
: number[4] < n-r+4? => number[4] < 19? YES => increase IS possible. Next combination = 1,2,3,5,6
:
: | 1 | 2 | 3 | 19| 20| number[5] < n-r+5? => number[5] < 20? NO => increase IS NOT possible.
: number[4] < n-r+4? => number[4] < 19? NO => increase IS NOT possible.
: number[3] < n-r+3? => number[3] < 18? YES => increase IS possible. Next combination = 1,2,4,5,6
: [/CODE]
:
: This code should be easily ported to other languages.
: Remarks:
: The [italic]number[/italic] array mentioned above is called [italic]combination[/italic] in the code.
: In the explanation above [italic]number[/italic] is indexed from 1 to r, in the code below the index goes from 0 to r-1, hence the use of [leftbr]index-1[rightbr] and [leftbr]index-2[rightbr].
: [CODE]
:
:
:
: n = 20
: r = 5
:
: var combination = new Array(r);
:
: for(i=0; i r)
: index = r;
: while(combination[leftbr]index-1[rightbr]==n+index-r && index>0)
: index--;
: if(index==0)
: return false;
: combination[leftbr]index-1[rightbr]++;
: for(index++; index<=r; index++)
: combination[leftbr]index-1[rightbr] = combination[leftbr]index-2[rightbr]+1;
: }
: return true;
: }
: function showNext() {
: val = getNextCombination(n, r);
: if(!val) // No more combinations found
: return val;
:
: txt = "";
: for(i in combination)
: txt+=combination[leftbr]i[rightbr]+", ";
:
: // Show the combination somewhere
: window.status = txt;
:
:
: return val;
: }
: function init() {
: for(p=0; p<50000 && showNext(); p++); // Shows the first 50000 combinations or as many as there are
: }
: </script>
:
:
:
:
: [/CODE]
:

• To print the combination on the screen simply replace
[CODE]
window.status = txt;
[/CODE]
with
[CODE]
document.write(txt+"
");
[/CODE]
But you might get a warning because it takes very long time (in computer terms) to complete.
• don"t worry about what i said, it works thanks very much for your help. later
• Your design is close, but it did not produce the intended results.

n = 10
r = 3

sample output:

1, 2, 3,
1, 2, 4,
1, 2, 5,
1, 2, 6,
1, 2, 7,
1, 2, 8,
1, 2, 9,
1, 2, 10,
1, 3, 4,
1, 3, 5,
1, 3, 6,
1, 3, 7,
1, 3, 8,
1, 3, 9,
1, 3, 10,
1, 4, 5,
1, 4, 6,
1, 4, 7,
1, 4, 8,
1, 4, 9,
1, 4, 10,
1, 5, 6,
1, 5, 7,
1, 5, 8,
1, 5, 9,
1, 5, 10,

note that combinations should also include
111
112
113
114 ... etc.
121
122
123 (ok)
124 (ok)

and note how the distance in the leftmost digit decreases in your output. Close, but no cigar. I'm working on a solution as well and will post when I have a recursive solution (nested foreach loops work well, but are not ideal...that's what I like about your solution.)
• i want the same result in in php and my condition is i want to pass different king of numbers in . now this combinations goes sequence number like 1,2,3,4,5,6 and i want a combinations of different numbers from a array like i need a result of array(1,12,32,24,14) and r value is default 7 . can any one provide me a solution for this in php.

Thank in advance who ever helps me .
• i want the same result in in php and my condition is i want to pass different king of numbers in . now this combinations goes sequence number like 1,2,3,4,5,6 and i want a combinations of different numbers from a array like i need a result of array(1,12,32,24,14) and r value is default 7 . can any one provide me a solution for this in php.

Thank in advance who ever helps me .