Geek asks and answers

Select integers from a given range

I need to select 6 integers from range(1, 51)so that no two consecutive integers are selected. (1, 3, 6, 9, 13, 28)- an acceptable choice, but (1, 3, 4, 9, 13, 28)no. I need to make a list of all possible combinations with each combination in the tuple. Instead of a list, a generator will also be created. I understand that I need to use something like itertools.combinationshere, but I cannot figure out how to eliminate tuples with sequential values. I wrote this code,

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

This is the length that I expect if there were no restrictions on which tuples can be selected, i.e. 50!/(44!6!). Any help?

+3
source share
3 answers

You can use allwith 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

The 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
+7
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))

6 1 45. 6 x0, x1, x2, x3, x4, x5 1 45,

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

1-50 , y0, y1, y2, y3, y4, y5 x

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

, , . , . , . . , 16 6, 1212 , .

+5

, ( ) " 50" - 40, (40, 42, 44, 46, 48, 50) " ". 5 " " , , - "" 1 45, 0, 1, 2,... 5 ( ) .

In this way:

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 since it does not generate any combinations that it will not use. With the numbers you are talking about, this is important. Original = 50!/(44!*6!), new = 45!/(39!*6!). This makes it about 2 times more efficient ( 50*49*48*47*46*45 / (45*44*43*42*41*40)) ~ 1.95... (and thanks to user2357112 for pointing out the explicit arithmetic error I made - an extra coefficient was added 6!that crept in ...)

+3
source

More articles:


All Articles