1

私は、各要素が元の場所とは異なる順列で作業しています。{入力の長さ、行、桁}を指定すると、出力番号が得られるアルゴリズムが必要です。次に例を示します。

入力長が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言語では素晴らしいでしょう。

（宿題ではなく、仕事用です。知っておく必要がある場合はカッコウのハッシュです。各段階で行うスワップをランダムに選択して、テーブルの数が2を超える場合にBFSよりも優れているかどうかを確認したいと思います。 。）

4

2 に答える 2

1

木を作ってそれを繰り返してみませんか？

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

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

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

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

必要に応じて、その場でツリーを構築できます。順序は、ツリーをどのようにトラバースするかによって定義できます。

于 2009-08-31T03:02:44.303 に答える
0

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()
于 2009-06-21T19:14:03.493 に答える