Howdy, Stranger!

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

Categories

simple combination

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








Comments

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

    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.

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

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

  • BodkinBodkin Member Posts: 100
    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.
  • sin26102003sin26102003 Member Posts: 5
    don"t worry about what i said, it works thanks very much for your help. later
  • twinks23twinks23 Member Posts: 1
    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.)
  • nrkamleshnrkamlesh Member Posts: 6
    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 .
  • nrkamleshnrkamlesh Member Posts: 6
    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 .
Sign In or Register to comment.