# python - Eliminating consecutive number combinations from a result set

I have a list of 30 numbers:

``[1, 3, 5, 6, 7, 8, 9, 10, 15, 19, 20, 22, 23, 24, 26, 27, 28, 32, 33, 35, 37, 38, 39, 40, 41, 42, 43, 44, 47, 48]``

I'm printing out all possible 8 digit combinations, which is working great using this code:

``possible_combinations = itertools.combinations(dedup_list, 8)combos = []for e in possible_combinations:combos.append(e)print combos``

What I'd like to do now is eliminate ALL combinations containing consecutive 3 digit numbers, for example:

`[1, 5, 9,`22, 23, 24, `33, 37]`

Suggestions?

I think this does the trick:

``````from itertools import combinations, groupby
from operator import itemgetter

data = [1, 3, 5, 6, 7, 8, 9, 10, 15, 19, 20, 22, 23, 24, 26, 27, 28, 32, 33, 35, 37, 38, 39, 40, 41, 42, 43, 44, 47, 48]

def find_consecutive(lst, min_string=3):
for k, g in groupby(enumerate(lst), lambda (i,x):i-x):
num_string = map(itemgetter(1), g)
if len(num_string) >= 3:
yield num_string

for i in combinations(data, 8):
if not any(find_consecutive(i, min_string=3)):
print i
``````

returns:

``````(1, 3, 5, 6, 8, 9, 15, 19)
(1, 3, 5, 6, 8, 9, 15, 20)
(1, 3, 5, 6, 8, 9, 15, 22)
(1, 3, 5, 6, 8, 9, 15, 23)
(1, 3, 5, 6, 8, 9, 15, 24)
``````

...et cetera, et cetera

Here's one way by calculating the differences (similar to numpy's `diff`):

``````def diff(lst):
return map(lambda x,y: y-x, lst[:-1],lst[1:])

def remove_consecutive(lst):
previous = None
for i, current in enumerate(diff(lst)):
if previous != 1 and current != 1:
yield lst[i]
previous = current
if current != 1:
yield lst[-1]

list(remove_consecutive([1, 5, 9, 22, 23, 24, 33, 37]))
# [1, 5, 9, 33, 37]
``````

Which works from the observation that an item is not consecutive only if neither the previous and the next differences are 1.

Not the slick `itemgetter` technique like hexparrot, closer to how Balthamos did it in their post.

``````sec = []
for combo in combo_lst:
seq = combo[:]
for i in combo:
if list(combo[combo.index(i):combo.index(i)+3]) == range(i, i+3):
break
combo = combo[combo.index(i)+1:]
if len(combo) == 0:
sec.append(seq)
break
``````

This probably won't win any efficiency awards, but you get style points for the list comprehensions.

This is how I would approach the problem. Make a list of a sliding window of size 3.

``````>>> nums = [1, 3, 5, 6, 7, 8, 9, 10, 15, 19, 20, 22, 23, 24, 26, 27, 28, 32, 33, 35, 37, 38, 39, 40, 41, 42, 43, 44, 47, 48]
>>> [nums[i:i+3] for i in xrange(len(nums))]
[[1, 3, 5], [3, 5, 6], [5, 6, 7], [6, 7, 8], [7, 8, 9], [8, 9, 10], [9, 10, 15], [10, 15, 19], [15, 19, 20], [19, 20, 22], [20, 22, 23], [22, 23, 24], [23, 24, 26], [24, 26, 27], [26, 27, 28], [27, 28, 32], [28, 32, 33], [32, 33, 35], [33, 35, 37], [35, 37, 38], [37, 38, 39], [38, 39, 40], [39, 40, 41], [40, 41, 42], [41, 42, 43], [42, 43, 44], [43, 44, 47], [44, 47, 48], [47, 48], [48]]
``````

Next step, get rid of the consecutive items, which is trivially easy now. This predicate will get cleverly filter out the consecutive items.

``````>>> [nums[i] for i in xrange(len(nums)) if nums[i:i+3] != range(nums[i],nums[i]+3)]
[1, 3, 9, 10, 15, 19, 20, 23, 24, 27, 28, 32, 33, 35, 43, 44, 47, 48]
``````

EDIT:

Eric brought up a good point, the solution above does not work entirely. If you want this to work, then predicate is going to need some beefing up. First, I derived these equations. They perform the windowing operation. Convince yourself that they are true:

``````a = [1,2,3,4,5]
i = 2
a[i-0:i+3] == range(a[i-0], a[i]+3) # left
a[i-1:i+2] == range(a[i-1], a[i]+2) # center
a[i-2:i+1] == range(a[i-2], a[i]+1) # right
``````

Then you could jam it in there sideways...

``````[a for i,a in enumerate(nums) if all(nums[i-j:i+k] != range(nums[i-j], nums[i]+k) for j,k in zip(xrange(0,3,1), xrange(3,0,-1)))]
``````

But if you don't want to get shot, pull out the predicate into a function:

``````consec_to_buddies = lambda i, xs: (
xs[i-0:i+3] == range(xs[i-0], xs[i]+3) or
xs[i-1:i+2] == range(xs[i-1], xs[i]+2) or
xs[i-2:i+1] == range(xs[i-2], xs[i]+1)
)

[a for i,a in enumerate(nums) if not consec_to_buddies(i, nums)]
``````

Again, this isn't the most efficient, as you will be calculating the predicate for every item, even if you already know you are taking it out. The price you pay for elegance :)