CODEWITHSUNDEEP
python
Guy
Guy

Reputation: 624

Select integers from a given range

I need to select 6 integers from range(1, 51) such that no two consecutive integers are selected. (1, 3, 6, 9, 13, 28) is a valid selection but (1, 3, 4, 9, 13, 28) is not. I need to build a list of all such possible combinations, with each combination in a tuple. Instead of a list a generator will also do. I understand I need to use something like itertools.combinations here, but I can't figure out how to eliminate the tuples with consecutive values. I wrote this code,

>>> import itertools
>>> l = list(itertools.combinations(range(1, 51), 6))
>>> len(l)
13983816

That is the length I am expecting if there were no constraints on what tuples can be selected, i.e, 50!/(44!6!). Any help?

Upvotes: 3

Views: 291

Answers (3)

user2357112
user2357112

Reputation: 281624

from itertools import combinations, imap
from operator import add
from functools import partial

result = imap(partial(map, add, range(6)), combinations(range(1, 46), 6))

This solution makes use of a bijection from the desired combinations to the set of all combinations of 6 integers from 1 to 45. We pick 6 increasing numbers x0, x1, x2, x3, x4, x5 from 1 to 45, then compute

x0, x1+1, x2+2, x3+3, x4+4, x5+5

This new combination is guaranteed to fall within the range 1-50 and have no consecutive numbers, and any desired combination y0, y1, y2, y3, y4, y5 can be produced by the unique choice of x values

y0, y1-1, y2-2, y3-3, y4-4, y5-5

This works a few times faster than a solution based around filtering out the undesired combinations. The downside is that it takes longer to understand. I had to write a substantial amount of explanation for this, while the other solution is much more straightforward. With longer combinations, this algorithm would have a substantial advantage. For example, if we were picking 16 numbers instead of 6, the other algorithm would consider about 1212 times the number of combinations this algorithm would.

Upvotes: 5

Floris
Floris

Reputation: 46425

If you think about it, your first (lowest) value cannot be "any one of 50" values - it has to be less than or equal to 40 since (40, 42, 44, 46, 48, 50) is the "last valid tuple". There must always be 5 "unused values" in between the ones you pick, so the simplest way to achieve this is to select "unconstrained" values from 1 to 45, then add 0, 1, 2, ... 5 to the (sorted) values you get.

Thus:

for t in itertools.combinations(range(1,46), 6):
    print tuple(x+y for x,y in zip(t, (0,1,2,3,4,5)))

This is more efficient as it doesn't generate any combinations it won't use. With the numbers you are talking about that is significant. Original = 50!/(44!*6!), new = 45!/(39!*6!). That makes it about 2x more efficient (50*49*48*47*46*45 / (45*44*43*42*41*40)) ~ 1.95... (and thanks user2357112 for pointing out the glaring arithmetic mistake I made - there was an extra factor 6! that had crept in...)

Upvotes: 3

Ashwini Chaudhary
Ashwini Chaudhary

Reputation: 251106

You can use all with a generator expression:

>>> t = (1,3,4,9,13,28)
>>> all( x-y > 1 for x, y in zip(t[1:], t))
False
>>> t = (1,3,6,9,13,28)
>>> all( x-y > 1 for x, y in zip(t[1:], t))
True

Code:

import itertools
for t in itertools.combinations(range(1, 20), 6):
    if all( x-y > 1 for x, y in zip(t[1:], t)):
        #do something with t

Upvotes: 7

Related Questions