simple combination - Algorithms - Forums at ProgrammersHeaven.com

Algorithms

Moderators: None (Apply to moderate this forum)

Number of threads: 402
Number of posts: 786

With full replies

Topics only

Algorithms

Forum Info

This Forum Only

Single Post View Linear View Threaded View f

Printer Friendly

RSS Feed

simple combination Posted by sin26102003 on 22 Jan 2006 at 4:20 PM

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.

Share By Email

Re: simple combination Posted by Bodkin on 23 Jan 2006 at 4:27 AM

This message was edited by Bodkin at 2006-1-23 4:36:19

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

                    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

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

<html>
<head>
<script>
n = 20
r = 5

var combination = new Array(r);

for(i=0; i<r; i++)
	combination[i] = 0;

function getNextCombination(n, r) {
	if(combination[0]==0) { // First time here, make the initial combination
		for(i=0; i<r; i++)
			combination[i] = i+1;
	}
	else {
		// n+index-r is max value (index : 1 -> r)
		index = r;
		while(combination[index-1]==n+index-r && index>0)
			index--;
		if(index==0)
			return false;
		combination[index-1]++;
		for(index++; index<=r; index++)
			combination[index-1] = combination[index-2]+1;
	}
	return true;
}
function showNext() {
	val = getNextCombination(n, r);
	if(!val) // No more combinations found
		return val;

	txt = "";
	for(i in combination)
		txt+=combination[i]+", ";

	// 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>
</head>
<body onload="init()">
</body>
</html>

Share By Email

Re: simple combination Posted by sin26102003 on 26 Jan 2006 at 5:07 PM

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

the
<html>
: <head>
: <script>
in the begining and end makes no difference and i cannot find the error to end the file.

reply

: This message was edited by Bodkin at 2006-1-23 4:36:19

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

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

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

: <html>
: <head>
: <script>
: n = 20
: r = 5
: 
: var combination = new Array(r);
: 
: for(i=0; i<r; i++)
: 	combination[i] = 0;
: 
: function getNextCombination(n, r) {
: 	if(combination[0]==0) { // First time here, make the initial combination
: 		for(i=0; i<r; i++)
: 			combination[i] = i+1;
: 	}
: 	else {
: 		// n+index-r is max value (index : 1 -> r)
: 		index = r;
: 		while(combination[index-1]==n+index-r && index>0)
: 			index--;
: 		if(index==0)
: 			return false;
: 		combination[index-1]++;
: 		for(index++; index<=r; index++)
: 			combination[index-1] = combination[index-2]+1;
: 	}
: 	return true;
: }
: function showNext() {
: 	val = getNextCombination(n, r);
: 	if(!val) // No more combinations found
: 		return val;
: 
: 	txt = "";
: 	for(i in combination)
: 		txt+=combination[i]+", ";
: 
: 	// 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>
: </head>
: <body onload="init()">
: </body>
: </html>
:

Share By Email

Re: simple combination Posted by nrkamlesh on 21 May 2010 at 5:32 AM

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 .

Share By Email

Re: simple combination Posted by sin26102003 on 26 Jan 2006 at 5:26 PM

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

This message was edited by Bodkin at 2006-1-23 4:36:19

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

: <html>
: <head>
: <script>
: n = 20
: r = 5
: 
: var combination = new Array(r);
: 
: for(i=0; i<r; i++)
: 	combination[i] = 0;
: 
: function getNextCombination(n, r) {
: 	if(combination[0]==0) { // First time here, make the initial combination
: 		for(i=0; i<r; i++)
: 			combination[i] = i+1;
: 	}
: 	else {
: 		// n+index-r is max value (index : 1 -> r)
: 		index = r;
: 		while(combination[index-1]==n+index-r && index>0)
: 			index--;
: 		if(index==0)
: 			return false;
: 		combination[index-1]++;
: 		for(index++; index<=r; index++)
: 			combination[index-1] = combination[index-2]+1;
: 	}
: 	return true;
: }
: function showNext() {
: 	val = getNextCombination(n, r);
: 	if(!val) // No more combinations found
: 		return val;
: 
: 	txt = "";
: 	for(i in combination)
: 		txt+=combination[i]+", ";
: 
: 	// 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>
: </head>
: <body onload="init()">
: </body>
: </html>
:

Share By Email

Re: simple combination Posted by Bodkin on 27 Jan 2006 at 9:11 AM

To print the combination on the screen simply replace

window.status = txt;

with

document.write(txt+"<br />");

But you might get a warning because it takes very long time (in computer terms) to complete.

Share By Email

Re: simple combination Posted by sin26102003 on 29 Jan 2006 at 8:23 AM

don"t worry about what i said, it works thanks very much for your help. later

Share By Email

Re: simple combination Posted by twinks23 on 9 Apr 2010 at 12:36 PM

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

Share By Email

Re: simple combination Posted by nrkamlesh on 21 May 2010 at 5:31 AM

Share By Email

Algorithms

Recent Jobs