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

- 141K All Categories
- 103.8K Programming Languages
- 6.5K Assembler Developer
- 1.9K Basic
- 40K C and C++
- 2.9K C#
- 7.9K Delphi and Kylix
- 4 Haskell
- 9.7K Java
- 4.1K Pascal
- 1.3K Perl
- 2K PHP
- 551 Python
- 37 Ruby
- 4.4K VB.NET
- 1.6K VBA
- 20.9K Visual Basic
- 2.6K Game programming
- 317 Console programming
- 92 DirectX Game dev
- 1 Minecraft
- 112 Newbie Game Programmers
- 2 Oculus Rift
- 9K Applications
- 1.8K Computer Graphics
- 744 Computer Hardware
- 3.5K Database & SQL
- 535 Electronics development
- 1.6K Matlab
- 628 Sound & Music
- 258 XML Development
- 3.3K Classifieds
- 199 Co-operative Projects
- 198 For sale
- 190 FreeLance Software City
- 1.9K Jobs Available
- 604 Jobs Wanted
- 210 Wanted
- 2.9K Microsoft .NET
- 1.8K ASP.NET
- 1.1K .NET General
- 3.4K Miscellaneous
- 7 Join the Team
- 355 Comments on this site
- 70 Computer Emulators
- 2.1K General programming
- 187 New programming languages
- 628 Off topic board
- 216 Mobile & Wireless
- 88 Android
- 126 Palm Pilot
- 340 Multimedia
- 156 Demo programming
- 184 MP3 programming
- Bash scripts
- 27 Cloud Computing
- 53 FreeBSD
- 1.7K LINUX programming
- 370 MS-DOS
- Shell scripting
- 321 Windows CE & Pocket PC
- 4.1K Windows programming
- 942 Software Development
- 417 Algorithms
- 68 Object Orientation
- 92 Project Management
- 95 Quality & Testing
- 269 Security
- 7.7K WEB-Development
- 1.8K Active Server Pages
- 62 AJAX
- 5 Bootstrap Themes
- 55 CGI Development
- 28 ColdFusion
- 224 Flash development
- 1.4K HTML & WEB-Design
- 1.4K Internet Development
- 2.2K JavaScript
- 37 JQuery
- 308 WEB Servers
- 151 WEB-Services / SOAP

sin26102003
Member Posts: **5**

in Algorithms

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.

:

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

Terms of use / Privacy statement / Publisher: Lars Hagelin

Programmers Heaven articles / Programmers Heaven files / Programmers Heaven uploaded content / Programmers Heaven C Sharp ebook / Operated by CommunityHeaven

© 1997-2017 Programmersheaven.com - All rights reserved.

## Comments

100Principle:

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]

5Thanks, 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.

reply

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

:

5[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]

:

100[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.

51n = 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.)

6Thank in advance who ever helps me .

6Thank in advance who ever helps me .