要素が配置されていない順列を見つける
-
06-07-2019 - |
質問
各要素が元の場所と異なる順列で作業しています。 {入力の長さ、行、桁}を指定して、出力番号を取得するアルゴリズムが欲しいです。次に例を示します。
入力長が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より大きい。)
解決
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()
他のヒント
ツリーを構築して繰り返し処理するだけではどうですか?
たとえば、数字 0123
がある場合、左端の数字は set {1,2,3}
からのみであることがわかります。これは、ツリーの最初のレベルとして機能します。
その後、1から始まるパスを進むと、 {0、2、3}
の3つのオプションしかありません。最初のレベルで2で始まるパスを下る場合、2つのオプション {0,3}
のみがあります(左から2番目の数字に1を使用できず、2は既に使用されています(選択リストから2をポップできます)、など。
このアプローチで注意すべきことは、3が唯一のオプションであるブランチの最後に到達した場合です。その場合、それを削除するだけです。
nの場合> 10
すべての順列を生成してからフィルタリングすると、問題が発生する可能性があります。ツリーを構築すると、これが大幅に削減されます。
必要に応じてその場でツリーを構築できます。順序は、ツリーの走査方法によって定義できます。