algorithm - 在 C++ ("put apples in different plates"中实现组合算法)

Question

我生成了一组 n 元素数组，其中交替包含 1 和 -1，后跟零，所有元素都以 1 开头。

例如，对于 n=5，数组为:10000,1-1000,1-1100,1-11-10,1-11-11,

我需要在每个数组的非零数字之间“插入”零:对于上例中的1-1100，枚举为:

1 -1 1 0 0,(允许某些1和-1之间没有0。)

1 -1 0 1 0,

1 0 -1 1 0,

1 0 -1 0 1,

1 0 0 -1 1,

1 -1 0 0 1(第一个元素仍需为1)

是否有一个好的算法可以为具有上述格式的给定数组生成这样的枚举？

我认为这个问题就像将相同的苹果放入不同的盘子中(因为将零放入不同的间隙会产生不同的枚举)并允许一些盘子保持空白。

我需要打印出所有的可能性，而不仅仅是计算它们。但目前我想不出一个好的方法。

Answer 1

这比看起来要简单。

第一个元素总是 1。因此，我们可以忽略它，只在我们的答案前加上 1。

初始 1 之后的非零元素始终为 -1、1、-1 等。由于这个模式是固定的，我们可以用 1 替换所有非零值，然后翻译回去。

所以现在我们只有一个 0 和 1 的列表，需要生成它们的所有排列。

用 Python 将它们放在一起:

#!/usr/bin/env python3

N = 5

def main():
    # k = number of nonzeros, minus the initial one that's always there
    for k in range(N):
        seq = [0] * (N - 1 - k) + [1] * k
        for p in next_permutation(seq):
            result = decorate(p)
            print(" ".join("{:2d}".format(i) for i in result))

# adapted from http://stackoverflow.com/questions/4250125
def next_permutation(seq):
    seq = seq[:]
    first = 0
    last = len(seq)
    yield seq

    if last == 1:
        raise StopIteration

    while True:
        next = last - 1
        while True:
            next1 = next
            next -= 1
            if seq[next] < seq[next1]:
                mid = last - 1
                while seq[next] >= seq[mid]:
                    mid -= 1
                seq[next], seq[mid] = seq[mid], seq[next]
                seq = seq[:next1] + list(reversed(seq[next1:last])) + seq[last:]
                yield seq[:]
                break
            if next == first:
                raise StopIteration
    raise StopIteration

def decorate(seq):
    # Convert 1's to alternating -1, 1, then prepend a 1 to whole thing
    seq = seq[:]
    n = -1
    for i in range(len(seq)):
        if seq[i]:
            seq[i] = n
            n = -n
    return [1] + seq

main()