8

次の文字列が2桁異なる、長さnのバイナリ文字列とk個のバイナリ文字列のシーケンスを生成するアルゴリズムについて疑問に思っています。

例えば：

11100
11010
11001
10101
10110
10011
00111
01011
01101
01110
11100

もちろん、すべてのn \choose kバイナリ文字列を使用する必要があります。

4

3 に答える 3

2

これは再帰を使用して設定できると思います。

私は次のアイデンティティに触発されました：

choose(n,k) = choose(n-1,k-1) + choose(n-1,k)

したがって、要求されたシーケンス（つまり、連続する文字列が2ビット異なるように正確にkビットが設定された長さnのバイナリ文字列のシーケンス）を生成する関数F（n、k）を定義します。

まず、F（n、k）の列を好きなように並べ替えて、同じように有効な別のF（n、k）を生成できることを確認します。

上記の同一性は、F（n-1、k-1）とF（n-1、k）を使用してF（n、k）を構築することを示唆しています。最後の文字列がk-1sで終わるように、F（n-1、k-1）の列を並べ替えて、それぞれ1にaを追加して、 Aを取得した文字列1とします。最初の文字列がksで終わるように、F（n-1、k）の列を並べ替えて、それぞれ1にaを追加して得られる文字列をBとします0。その場合、F（n、k）はAとBの単なる連結です。結果は有効なF（n、k）です。これは、AとBの内部で、文字列が2ビット異なり、Aの最後の文字列と最初の文字列が異なるためです。 Bの文字列は2ビット異なります（k + 1番目から最後のビットと最後のビット）。

n = 5、k=2を使用した例を示します。次の2つのFシーケンスを再帰的に取得します。

F(4,1): 0001
        0010
        0100
        1000

F(4,2): 0011
        0101
        1001
        1010
        0110
        1100

Aを作成するには、F（4,1）の最初と最後の列を入れ替えて、1それぞれに追加します。

A: 10001
   00101
   01001
   00011

Bを作成するには、列を入れ替える必要がないため、0F（4,2）の各行にaを追加するだけです。

B: 00110
   01010
   10010
   10100
   01100
   11000

その場合、F（5,2）はAとBの単なる連結です。

于 2012-08-01T04:54:21.593 に答える
2

この種の順列に関する私のブログ投稿（とりわけ）を読んで、より多くの背景を取得する必要があります-そしてそこにあるリンクのいくつかをたどってください。

これは、Steinhaus–Johnson–Trotter順列ジェネレーターの生成シーケンスの後に作成された辞書式順列ジェネレーターのバージョンであり、要求どおりに実行されます。

def l_perm3(items):
    'Generator yielding Lexicographic permutations of a list of items'
    if not items:
        yield [[]]
    else:
        dir = 1
        new_items = []
        this = [items.pop()]
        for item in l_perm(items):
            lenitem = len(item)
            try:
                # Never insert 'this' above any other 'this' in the item 
                maxinsert = item.index(this[0])
            except ValueError:
                maxinsert = lenitem
            if dir == 1:
                # step down
                for new_item in [item[:i] + this + item[i:] 
                                 for i in range(lenitem, -1, -1)
                                 if i <= maxinsert]:
                    yield new_item                    
            else:    
                # step up
                for new_item in [item[:i] + this + item[i:] 
                                 for i in range(lenitem + 1)
                                 if i <= maxinsert]:
                    yield new_item                    
            dir *= -1

from math import factorial
def l_perm_length(items):
    '''\
    Returns the len of sequence of lexicographic perms of items. 
    Each item of items must itself be hashable'''
    counts = [items.count(item) for item in set(items)]
    ans = factorial(len(items))
    for c in counts:
        ans /= factorial(c)
    return ans

if __name__ == '__main__':
    n = [1, 1, 1, 0, 0]
    print '\nLexicograpic Permutations of %i items: %r' % (len(n), n)
    for i, x in enumerate(l_perm3(n[:])):
        print('%3i %r' % (i, x))
    assert i+1 == l_perm_length(n), 'Generated number of permutations is wrong'

上記のプログラムからの出力は、たとえば次のとおりです。

Lexicograpic Permutations of 5 items: [1, 1, 1, 0, 0]
  0 [1, 1, 1, 0, 0]
  1 [1, 1, 0, 1, 0]
  2 [1, 0, 1, 1, 0]
  3 [0, 1, 1, 1, 0]
  4 [0, 1, 1, 0, 1]
  5 [1, 0, 1, 0, 1]
  6 [1, 1, 0, 0, 1]
  7 [1, 0, 0, 1, 1]
  8 [0, 1, 0, 1, 1]
  9 [0, 0, 1, 1, 1]
于 2012-08-01T05:09:20.763 に答える
0
  1. グレイコード （連続する各番号が1ビット異なるシーケンス）を取ります。
  2. 別のビットを付加して、との間で循環させ0ます1。
0000
1001
0011
1010
0110
1111
0101
1100

これにより、nビット文字列のちょうど半分が生成されます。これはあなたが得ることができる最も多いものです-たとえば、すべての文字列で始まり0、一度に2ビットを変更すると、常に偶数の1'が存在するため、残りの半分は生成できません。

于 2012-07-31T16:55:57.820 に答える