#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

#### Categories

Welcome to the new platform of Programmers Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use it's exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

# simple combination

Posts: 5Member
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.

· ·

• Posts: 100Member
[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]
· ·
• Posts: 5Member

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]
:

· ·
• Posts: 5Member
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]
:

· ·
• Posts: 100Member
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.
· ·
• Posts: 5Member
don"t worry about what i said, it works thanks very much for your help. later
· ·
• Posts: 1Member
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.)
· ·
• Posts: 6Member
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 .
· ·
• Posts: 6Member
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 .
· ·