Generating combinations

[pauljwilliams]

Hi there,

I'm looking for an algorithm that will generate combinations in the
following way:

Given a lower bound, and an upper bound, generate a set of size n
containing all combinates of numbers between the bounds.

e.g if lower_bound = 5, upper bound = 7, size = 3, the algorithm would
generate:

555
556
557
565
566
567
575
576
577
655

etc.....

(in an ideal world i'd eliminate dupes as well, so 557 wont be produced
as well as 575).

I thought initially of generating a 'master set' such as '555666777',
and running next_permutation on it to get all the subsets, just taking
the first 3 each time, but in the biggest case( 9 numbers, 1 to 9) this
would take ages.

Is there a simple way?

 

[Zara]

Hi there,

I'm looking for an algorithm that will generate combinations in the
following way:

Given a lower bound, and an upper bound, generate a set of size n
containing all combinates of numbers between the bounds.

e.g if lower_bound = 5, upper bound = 7, size = 3, the algorithm would
generate:

555
556
557
565
566
567
575
576
577
655

etc.....

(in an ideal world i'd eliminate dupes as well, so 557 wont be produced
as well as 575).

I thought initially of generating a 'master set' such as '555666777',
and running next_permutation on it to get all the subsets, just taking
the first 3 each time, but in the biggest case( 9 numbers, 1 to 9) this
would take ages.

Is there a simple way?

Hint: you may use recursion. To avoid duplicates, never generate a new
digit which is less than a previous digit.

 

[Someonekicked]

555
556
557
566
567
577
666
667
677
777


start at the right digit, IF you can add 1 to it, and it would still be less
than upper_bound, then update this digit (old digit + 1) and update all the
digits to the right of it as equal to it, ELSE move to the next digit to the
left, and try the same.
Stop when you cant update the first digit to the left.

 

[Jon Slaughter]

Hi there,

I'm looking for an algorithm that will generate combinations in the
following way:

Given a lower bound, and an upper bound, generate a set of size n
containing all combinates of numbers between the bounds.

e.g if lower_bound = 5, upper bound = 7, size = 3, the algorithm would
generate:

555
556
557
565
566
567
575
576
577
655

notice that the above sequence is the same as with an appropriate mapping

000 = 0
001 = 1
002 = 2
010 = 3
011 = 4
012 = 5
020 = 6
021 = 7
022 = 8
100 = 9
101 = 10
102 = 11
110 = 12
etc...


i.e, (upper bound - lower bound) is your base and the "order" is size

so to generate the list above in base 10 you simply do

for(int i=0; i< something; i++)
{
list = i;
}

very simple huh? (Ofcourse you don't need to use a list to store them
though)


by converting val to the your bass and using the a digit mapping array you
can easily get what you want.

i.e. 000 = 555 because '0' = '5', etc...

022 = 577 because '0' = '5' and '2' = 7


Hopefully that makes sense. Basicaly you just need to figure out how to
convert from base 10 to base (upper bound - lower bound) and write a routine
to generate a conversion mapping and then it should be pretty easy.

etc.....

(in an ideal world i'd eliminate dupes as well, so 557 wont be produced
as well as 575).

I'm not exactly sure what you mean by dupes ;/

I thought initially of generating a 'master set' such as '555666777',
and running next_permutation on it to get all the subsets, just taking
the first 3 each time, but in the biggest case( 9 numbers, 1 to 9) this
would take ages.

Is there a simple way?

It think so...


Jon

 

[Ben Pope]

I'm not exactly sure what you mean by dupes ;/

Duplications.

Combinations vs. Permutations.

Ben