当前位置: 动力学知识库 > 问答 > 编程问答 >

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 :)

分享给朋友:
您可能感兴趣的文章:
随机阅读: