algorithm - 重複を含む数値のすべての一意の順列をリストするアルゴリズム

Question

問題は次のとおりです。重複を含む可能性のある数値のコレクションが与えられた場合、すべての一意の順列を返します。

単純な方法は、(C++ の) セットを使用して順列を保持することです。これにはO ( n ! × log( n !)) の時間がかかります。より良い解決策はありますか？

Answer 1

最も簡単なアプローチは次のとおりです。

1. リストを並べ替えます。O(n lg n)
2. ソートされたリストは最初の順列です
3. 前の順列から「次の」順列を繰り返し生成します。O(n! * <complexity of finding next permutaion>)

ステップ3は、次の順列を、順列のリストが並べ替えられた場合に現在の順列の直後に表示される順列として定義することで実行できます。例：

1, 2, 2, 3
1, 2, 3, 2
1, 3, 2, 2
2, 1, 2, 3
2, 1, 3, 2
2, 2, 1, 3
...

次の辞書式順列の検索はO（n）であり、Wikipediaページの「辞書式順序での生成」という見出しの下の順列について簡単に説明します。野心的な場合は、単純な変更を使用してO（1）で次の順列を生成できます

Answer 2

1）バックトラッキング/再帰検索のバリエーションは、通常、この種の問題を解決します。（n-1）オブジェクトのすべての順列のリストを返す関数を指定して、次のようにn個のオブジェクトのすべての順列のリストを生成します。リスト内の各要素について、n番目のオブジェクトをすべての可能な位置に挿入し、重複をチェックします。これは特に効率的ではありませんが、この種の問題に対して簡単なコードを生成することがよくあります。

2） http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_orderでウィキペディアを参照してください

3）学者はこれの詳細に多くの時間を費やしてきました。Knuth Vol 4Aのセクション7.2.1.2を参照してください。これは、Amazonに関する次の簡単な目次を備えた大きなハードカバーの本です。

第7章：組み合わせ検索1

7.1：ゼロとワン47

7.2：すべての可能性を生み出す281

Answer 3

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

これは、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_perm3(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 = [0, 1, 2, 2, 2]
    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: [0, 1, 2, 2, 2]
  0 [0, 1, 2, 2, 2]
  1 [0, 2, 1, 2, 2]
  2 [2, 0, 1, 2, 2]
  3 [2, 0, 2, 1, 2]
  4 [0, 2, 2, 1, 2]
  5 [2, 2, 0, 1, 2]
  6 [2, 2, 0, 2, 1]
  7 [0, 2, 2, 2, 1]
  8 [2, 0, 2, 2, 1]
  9 [2, 2, 2, 0, 1]
 10 [2, 2, 2, 1, 0]
 11 [2, 1, 2, 2, 0]
 12 [1, 2, 2, 2, 0]
 13 [2, 2, 1, 2, 0]
 14 [2, 2, 1, 0, 2]
 15 [1, 2, 2, 0, 2]
 16 [2, 1, 2, 0, 2]
 17 [2, 1, 0, 2, 2]
 18 [1, 2, 0, 2, 2]
 19 [1, 0, 2, 2, 2]

Answer 4

Paddy3118 のソリューションを少し改善したので、再帰的ではなく、遅延評価 (完全にジェネレーターに基づく) になり、約 30% 高速になりました。

def _handle_item(xs, d, t):
    l = len(xs)

    try:
        m = xs.index(t)
    except ValueError:
        m = l

    if d:
        g = range(l, -1, -1)
    else:
        g = range(l + 1)

    q = [t]
    for i in g:
        if i <= m:
            yield xs[:i] + q + xs[i:]

def _chain(xs, t):
    d = True

    for x in xs:
        yield from _handle_item(x, d, t)

        d = not d

def permutate(items):
    xs = [[]]

    for t in items:
        xs = _chain(xs, t)

    yield from xs

PS Paddy3118 が彼の実装でジェネレーターも使用していることに気付きましたが、ブログ投稿で実装に反対していましたが、これはより多くのメモリを消費します。このバージョンはよりクリーンであると見なされる可能性があるため、とにかくこれを投稿しています。