要素が残っていない順列を見つける

Question

各要素が元の位置と異なる順列を扱っています。私は与えられたアルゴリズム{入力の長さ、行と数字}、私に出力番号を与えたいと思います。ここでは例です：

入力の長さが4である場合には、0123の全ての順列は次のとおりです。

：何桁が同じ場所（すべての桁が移動した）ではありませんれ

0123,0132,0213,0231,0312,0321, 
1023,1032,1203,1230,1302,1320, 
2013,2031,2103,2130,2301,2310, 
3012,3021,3102,3120,3201,3210 

順列

番号は0から始まり、関数への入力が{4,0,0}の場合、出力は0番目（最初の）置換の0番目（左端）の数字になります。入力は、出力が2

行番号である1230の第二の数字は、のnubmer高くなることがあり、{4,1,1}である場合には1032の最初の桁が1

あります順列。その場合、置換の数を法とする剰余を取る（上記の場合は、9を法とする行）。

C言語では素晴らしいでしょう。

（これは宿題ではありません。あなたが知っていなければならないのであれば、Cuckoo hashingです。私は、ステージごとにスワップをランダムに選択して、BFSよりも優れているかどうかを確認したいと思います2以上である）Pythonで

Answer 1

強引なアプローチは、（あなたがCの実装をテストするためにそれを使用することができます）：。

#!/usr/bin/env python 
from itertools import ifilter, islice, permutations 

def f(length, row, digit): 
    """ 
    >>> f(4, 0, 0) 
    1 
    >>> f(4, 1, 1) 
    2 
    """ 
    # 1. enumerate all permutations of range (range(3) -> [0,1,2], ..) 
    # 2. filter out permutations that have digits inplace 
    # 3. get n-th permutation (n -> row) 
    # 4. get n-th digit of the permutation (n -> digit) 
    return nth(ifilter(not_inplace, permutations(range(length))), row)[digit] 

def not_inplace(indexes): 
    """Return True if all indexes are not on their places. 

    """ 
    return all(i != d for i, d in enumerate(indexes)) 

def nth(iterable, n, default=None): 
    """Return the nth item or a default value. 

    http://docs.python.org/library/itertools.html#recipes 
    """ 
    return next(islice(iterable, n, None), default) 

if __name__=="__main__": 
    import doctest; doctest.testmod() 

Answer 2

理由だけでツリーを構築し、それを反復処理しませんか？

たとえば、数字が0123の場合、左端の数字はset {1,2,3}からのみであることがわかります。これはあなたのツリーの最初のレベルとして機能します。

次に、1から始まるパスに進む場合は、3つのオプション、{0, 2, 3}しかありません。最初のレベルで2で始まるパスを下った場合、2つのオプションしかありません{0,3}（左から2番目の数字では1を使用できないため、2はすでに使用されています（リストから2をポップできます

このアプローチで注意すべきことは、唯一のオプションである3つのブランチの終わりに達した場合です。この場合、削除するだけです。

n > 10の場合、すべての順列が生成され、その後フィルタリングが問題になる可能性があります。私は木を構築することがこれを大幅にトリミングすると思う。

必要に応じて、オンザフライでツリーを構築できます。あなたの注文は、ツリーをどのようにトラバースするかによって定義できます。