python - 分多个步骤填写列表

Question

假设您有一个包含 y 个位置的列表(对于这个问题，为 0)。如果 y = 10:

[0,0,0,0,0,0,0,0,0,0]

您想要将相邻位置填充到给定值 x 并将其附加到空列表中。如果 x = 4:

[[1,1,1,1,0,0,0,0,0,0], [0,1,1,1,1,0,0,0,0,0], [0,0,1,1,1,1,0,0,0,0], ... , [0,0,0,0,0,0,1,1,1,1]]

我通过这个函数实现了这一点:

def permutations(number=4, limit=10):

    perms = [] 

    if type(number) == int:
        a = -1
        b = a + number
        while b < limit:
            a+=1
            b = a + number
            start = [0 for x in range(limit)]
            for i in range(a, b):
                start[i] = 1
            perms.append(start)

这很好，但如果我想做同样的事情，但传递一个元组而不是整数，我希望输出为:

如果数字 = (4,3):

[[1,1,1,1,0,1,1,1,0,0], [1,1,1,1,0,0,1,1,1,0], [1,1,1,1,0,0,0,1,1,1],
 [0,1,1,1,1,0,1,1,1,0], [0,1,1,1,1,0,0,1,1,1],
 [0,0,1,1,1,1,0,1,1,1]]

两个 1 分组之间的 0 是必需的，元组的第一个值对应于第一分组中 1 的数量，元组的第二个值对应于第二分组中 1 的数量。理想情况下，此函数适用于具有 2 个以上值的元组。

这个想法有点难以理解，所以如果您需要任何说明，请告诉我。

感谢您的帮助!

Answer 1

我能想到的最简单的方法是生成 1 和 0 的所有可能组合，并过滤掉所有不具有正确分组长度的组合。

import itertools

def permutations(tup, limit=10):
    for candidate in itertools.product([0,1], repeat=limit):
        segment_lengths = [len(list(b)) for a,b in itertools.groupby(candidate) if a == 1]
        if tup == tuple(segment_lengths):
            yield candidate

for seq in permutations((4, 3), 10):
    print seq

结果:

(0, 0, 1, 1, 1, 1, 0, 1, 1, 1)
(0, 1, 1, 1, 1, 0, 0, 1, 1, 1)
(0, 1, 1, 1, 1, 0, 1, 1, 1, 0)
(1, 1, 1, 1, 0, 0, 0, 1, 1, 1)
(1, 1, 1, 1, 0, 0, 1, 1, 1, 0)
(1, 1, 1, 1, 0, 1, 1, 1, 0, 0)

请注意，对于较大的 limit 值来说，这非常慢 - 它必须评估 2^limit 候选序列。 limit = 10 还不错；只需要评估 1024 名候选人。但它很快就会增长到数百万甚至更多，并达到更大的限制。

<小时/>

编辑:受到 user2097159 的精彩评论的启发，这里有一个具有更好运行时间的方法。

import itertools

"""Finds all non-negative integer sequences whose sum equals `total`, and who have `size` elements."""
def possible_sums(total, size):
    if total == 0:
        yield [0]*size
        return
    if size == 1:
        yield [total]
        return
    for i in range(total+1):
        left = [i]
        for right in possible_sums(total-i, size-1):
            yield left + right

"""
combines two lists a and b in order like:
[a[0], b[0], a[1], b[1]...]

"""
def interleave(a,b):
    result = []
    for pair in itertools.izip_longest(a,b):
        for item in pair:
            if item is not None:
                result.append(item)
    return result

"""flattens a list of lists into a one dimensional list"""
def flatten(seq):
    return [x for item in seq for x in item]

def permutations(tup, limit):
    one_segments = [[1]*size for size in tup]
    for i in range(len(tup)-1):
        one_segments[i].append(0)
    remaining_zeroes = limit - sum(tup) - len(tup) + 1
    assert remaining_zeroes >= 0, "not enough room to separate ranges!"
    for gap_sizes in possible_sums(remaining_zeroes, len(tup)+1):
        zero_segments = [[0]*size for size in gap_sizes]
        yield flatten(interleave(zero_segments, one_segments))

for seq in permutations((4, 3), 10):
    print seq