问在c++中实现组合算法(“把苹果放在不同的盘子里”)

EN

#!/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()