Generating all possible combinations

65c6277c91fae06e80a574be3c8440db
0
udvat 101 Jun 03, 2012 at 16:49

Hi,

I want to generate all possible combinations from a set of n numbers and
want to exclude the combinations with hold two consecutive numbers.

For example,

S={1,2,3}

I just want to generate
1;
2;
3;
1,3;

Is there any smart way of doing this other than generating all combinations first and
removing the unwanted ones?

Thanks in advance

4 Replies

Please log in or register to post a reply.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Jun 04, 2012 at 03:04

To generate all the combinations you’ll need nested loops, e.g. for combinations of two you’d have a loop to choose the first number and a loop to choose the second number. Just start the inner loop two later than the outer value rather than one later, and it’ll skip the consecutive ones.

65c6277c91fae06e80a574be3c8440db
0
udvat 101 Jun 04, 2012 at 08:07

It’s not just a combination of two, it can be combination of any size upto n.

820ce9018b365a6aeba6e23847f17eda
0
geon 101 Jun 04, 2012 at 08:41

Your list of results is not consistent with your description. None of the sequences below have two consecutive digits, I think?

3,1
2,1
2,1,3
2,3,1
1,3,2

Or did you mean something else?

Perhaps you could show us how you would implement it in the naïve way?

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Jun 04, 2012 at 16:05

@udvat

It’s not just a combination of two, it can be combination of any size upto n.

The same approach should still work. Generalizing it to size n is left as an exercise for the reader. ;)