要素が配置されていない順列を見つける

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

同じ場所に数字がない（すべての数字が移動した）順列：

1032,1230,1302,
2031,2301,2310,
3012,3201,3210

番号付けは0から始まるため、関数への入力が{4,0,0}の場合、出力は0番目（最初）の置換の0番目（左端）の数字でなければなりません。 1032の最初の数字は1です。

入力が{4,1,1}の場合、出力は1230の2桁目である2です。

行番号は、順列の数よりも大きい場合があります。その場合、置換の数を法とする剰余を取ります（上記の場合、9を法とする行）。

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

（それは宿題ではなく、仕事のためです。知っておくべきなら、カッコウハッシュ。各段階で作成するスワップをランダムに選択して、テーブルの数がBFSよりも良いかどうかを確認します。 2より大きい。）

Answer 1

Pythonのブルートフォースアプローチ（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から始まるパスを進むと、 {0、2、3} の3つのオプションしかありません。最初のレベルで2で始まるパスを下る場合、2つのオプション {0,3} のみがあります（左から2番目の数字に1を使用できず、2は既に使用されています（選択リストから2をポップできます）、など。

このアプローチで注意すべきことは、3が唯一のオプションであるブランチの最後に到達した場合です。その場合、それを削除するだけです。

nの場合＆gt; 10 すべての順列を生成してからフィルタリングすると、問題が発生する可能性があります。ツリーを構築すると、これが大幅に削減されます。

必要に応じてその場でツリーを構築できます。順序は、ツリーの走査方法によって定義できます。