c ++で組み合わせアルゴリズムを実装する（「リンゴを別のプレートに置く」）

debugcn 投稿 Dev

ビウ

1と-1が交互に続き、その後にゼロが続く、すべて1で始まるn要素配列のグループを生成しました。

たとえば、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である必要があります）

上記の形式で特定の配列に対してそのような列挙を生成するための優れたアルゴリズムはありますか？

問題は、同じリンゴを異なるプレートに入れて（異なるギャップにゼロを入れると異なる列挙が得られるため）、一部のプレートを空のままにしておくようなものだと思います。

数えるだけでなく、すべての可能性を印刷する必要があります。しかし、現在、私はそれを行うための良い方法を理解することができません。

トム・ザイチ

これは見た目よりも簡単です。

最初の要素は常に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()

この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。

侵害の場合は、連絡してください[email protected]