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]

pa***********@lycosmax.co.uk wrote:

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.

<pa***********@lycosmax.co.uk> wrote in message
news:11*********************@g44g2000cwa.googlegro ups.com...

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?

[Jon Slaughter]

<pa***********@lycosmax.co.uk> wrote in message
news:11*********************@g44g2000cwa.googlegro ups.com...

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

Jon Slaughter wrote:

<pauljwilliams> wrote in message
news:11*********************@g44g2000cwa.googlegro ups.com...

(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 ;/

Duplications.

Combinations vs. Permutations.

Ben
--
I'm not just a number. To many, I'm known as a String...