1

数字が同じ場所に配置されないように、または同様の数字が配置されたのと同じ場所に配置されないように、一連の数字（同様のアイテムを含む可能性がある）を再配置できる方法の数を見つけるにはどうすればよいですか。

たとえば、[0,0,0,1,1,1]は 1 つの方法でのみ再配置でき、それは[1,1,1,0,0,0]です。

[0,0,0,1,1,1,1]どうにもアレンジできません。

[1,2,2,14]2 つの方法で配置できます[2,1,14,2], [2,14,1,2]。

[1,1,2,2,14]4 つの方法で配置できます[14,2,1,1,2], [2,2,14,1,1], [2,2,1,14,1], [2,14,1,1,2]。

数学の解決策は利用可能ですが、プログラミングの概念を使用して簡単な方法を考えていました。数学コードは、このようなものです.. (すみません、正しい形式で投稿できませんでした)

∫∞0 Ln1(x)..Lnr(x)e−xdx

ここで、r は項目の数、ni は項目 i の出現回数、Lk は k 番目のラゲール多項式です。たとえば、1,1,2,2,14 の場合、r=3、n1=2、n2=2、n3=1 なので、符号までの再配置の数は

∫∞0 L2(x)L2(x)L1(x)e−xdx 
= ∫∞0 12(x2−4x+2)12(x2−4x+2)(1−x)e−xdx 
= ∫∞0(−14x5+94x4−7x3+9x2−5x+1)e−xdx
= −4

しかし、私たちが望むようにすべての順列を生成できる Python ライブラリがあるかどうかを考えていました。

4

3 に答える 3

3

より複雑ですが、長い入力シーケンスではかなり高速になるはずです:

from collections import Counter

def _rearrange(orig, rem):
    if len(orig)==1:
        v = rem[0][0]
        if v != orig[0]:
            yield [v]
    else:
        o, orig = orig[0], orig[1:]
        for i,(v,c) in enumerate(rem):
            if v != o:
                for r in _rearrange(orig, rem[:i]+([(v,c-1)] if c>1 else [])+rem[i+1:]):
                    yield [v]+r

def rearrange(orig):
    if len(orig) > 1:
        return list(_rearrange(orig, Counter(orig).items()))
    else:
        return []

def main():
    print rearrange([0,0,0,1,1,1])
    print rearrange([1,1,2,2,14])

if __name__=="__main__":
    main()

結果は

[[1, 1, 1, 0, 0, 0]]
[[2, 2, 1, 14, 1], [2, 2, 14, 1, 1], [2, 14, 1, 1, 2], [14, 2, 1, 1, 2]]

.

編集:関数のランタイムを比較すると、次のようになります。

ここに画像の説明を入力

(Tim は青、私のものは緑。点はデータ、線は最適 (データの対数の最小二乗)。x 軸はシーケンスの長さ、y 軸は実行時間 (対数目盛り)。データ ポイントは 10 のベスト)シーケンスの長さごとに 20 個のランダム シーケンスのそれぞれで実行されます。)

結論:

  • Tim の fn の実行時間は 7.44 * * n になります。私のは3.69 * * nとして成長します。

  • 10 項目のシーケンスで、彼の平均 fn は私の 0.93 秒に対して 53.9 秒です。シーケンス内の余分な項目ごとに、差は 2 倍強になります。

  • 彼の fn の実行時間ははるかに一貫しています。私のものは、シーケンス内の繰り返されるアイテムの数に応じて、非常に変動します。

  • 直線近似は最良の予測子のようには見えません。runtimes は、k * * n ではなく、n! の関数でなければなりません。ただし、これをモデル化する方法がわかりません。提案？

于 2012-05-21T14:35:10.067 に答える
3

itertools.permutations を試しましたか?

http://docs.python.org/library/itertools.html#itertools.permutations

import itertools

def my_combos(val):
    results = []
    l = itertools.permutations(val, len(val))
    for c in l:
        if all([x != y for (x,y) in zip(c,val)]):
            results.append(c)
    return list(set(results))


print my_combos([0,0,0,1,1,1])
print my_combos([1,1,2,2,14])

収量:

[(1, 1, 1, 0, 0, 0)]
[(2, 14, 1, 1, 2), (2, 2, 1, 14, 1), (14, 2, 1, 1, 2), (2, 2, 14, 1, 1)]
于 2012-05-21T10:47:08.313 に答える
1

ブルートフォース使用itertools：

import itertools
def arrangements(arr):
    p = itertools.permutations(arr)
    return set(item for item in p if all(x!=y for x,y in zip(item,arr)))

結果：

>>> arrangements([0,0,0,1,1,1])
{(1, 1, 1, 0, 0, 0)}
>>> arrangements([0,0,0,1,1,1,1])
set()
>>> arrangements([1,2,2,14])
{(2, 14, 1, 2), (2, 1, 14, 2)}
>>> arrangements([1,1,2,2,14])
{(2, 14, 1, 1, 2), (2, 2, 1, 14, 1), (14, 2, 1, 1, 2), (2, 2, 14, 1, 1)}
于 2012-05-21T11:00:37.423 に答える