13

熱心なプログラミングを行っているときに、この問題に遭遇しました。問題は次のように表現できます。

マルチセット A について、P(A) が A のすべての可能な順列のセットを表すとします。P(A) は、等価関係が「循環シフトによって関連付けられる可能性がある」状態で、等価クラスである互いに素なサブセットに自然に分割されます。それぞれから正確に 1 つのメンバーを生成することにより、これらすべての等価クラスを列挙します。

たとえば、マルチセット {0, 1, 1, 2} を考えてみましょう。順列 "0112" と "1201" は一意の順列ですが、後者は前者を循環シフトすることで見つけることができ、逆も同様です。目的のアルゴリズムで両方を生成することはできません。

もちろん、強引なアプローチも可能です。循環重複に関係なく、任意のマルチセット置換アルゴリズムを使用して順列を生成し、以前の結果との比較によって見つかった重複を破棄するだけです。ただし、これは実際には非効率的である傾向があります。必要なアルゴリズムは、簿記がゼロではないにしても、最小限で済む必要があります。

この問題への洞察は深く感謝しています。

4

5 に答える 5

8

澤田のアルゴリズム

于 2010-08-12T13:31:42.813 に答える
1

このボトムアップに行く方が少し簡単です。

A に 1 つの要素しか含まれていない場合、P(A) にも 1 つの順列が含まれます。A に 2 つの要素しか含まれていない場合、同じ動作を簡単に確認できます。

ここで、n 個の要素を持つ A のすべての P(A) が既にあり、1 つの要素を追加するとします。P(A) の任意の順列の n 個のスポットのいずれかに入ることができます。

このアイデアは、選択した言語の再帰アルゴリズムにかなり直接的に変換されると思います。私の説明が十分に明確であることを願っています。

編集: A に重複要素が含まれる可能性があるという事実を無視したことは知っていますが、その部分についてはまだ考えています:)

とはいえ、順列アルゴリズムを開始する前に A をソートした場合、これにより重複が排除される可能性があると思います。（それもまだ考え中）

于 2010-08-12T13:31:05.717 に答える
1

ここで、Pythonで実装されたソリューションを提案します

import itertools as it

L = ['a','b','c','d']
B = it.combinations(L,2)
swaplist = [e for e in B]
print 'List of elements to permute:' 
print swaplist
print
unique_necklaces = []
unique_necklaces.append(L)
for pair in swaplist:
    necklace = list(L)
    e1 = pair[0]
    e2 = pair[1]
    indexe1 = L.index(e1)
    indexe2 = L.index(e2)
    #swap
    necklace[indexe1],necklace[indexe2] = necklace[indexe2], necklace[indexe1]
    unique_necklaces.append(necklace)

for n in unique_necklaces:
    # Commented code display the rotation of the elements in each necklace
    print 'Necklaces'
    print n#, [n[-r:]+n[:-r]for r in (1,2,3)]

アイデアは、2 つの要素の順列によって異なるネックレスを構築することです。4 つの要素 a、b、c、d のリストの場合、アルゴリズムは次のようになります。

['a', 'b', 'c', 'd']
['b', 'a', 'c', 'd']
['c', 'b', 'a', 'd']
['d', 'b', 'c', 'a']
['a', 'c', 'b', 'd']
['a', 'd', 'c', 'b']
['a', 'b', 'd', 'c']
于 2014-04-08T13:15:34.090 に答える
0

問題を直感的に理解するために、この比喩を使用できると思います。壁に掛けられた時計を視覚化しますが、文字盤に 12 の位置がある代わりに、n があります。ここで、n はセット内の要素の数です。

次に、各等価クラスは、A の要素を時計の文字盤上の位置に割り当てるだけです。

割り当てられると、壁の時計を回転させるだけで、同じ等価クラスから別の順列を生成できます。

A の別の無関係な順列を生成するには、要素が少なくとも 1 つの他の要素をスキップする必要があります。

今私が見ているアルゴリズムは、たとえば、A = {a、b、c、d} に 4 つの要素があり、それらを視覚的にそれぞれ 12、3、6、9 の位置に割り当てたとします。明快さ。次に、最初の操作は a と b を交換することです。次に a と c、次に a と d、次に b に移動し、3 番目の位置にある要素 (現在は c) と交換します。

d に到達するまでこれを行うと、すべての等価クラスから代表が生成されます。

これは重複を処理しませんが、A のすべての順列を生成するよりもはるかに効率的です。

于 2010-08-12T14:01:52.680 に答える
0

私の頭に浮かんだ考えは、一度しか現れない要素が少なくとも 1 つあるセットについては、その要素をすべての回答のリストの最初の位置に配置し、残りの数字のすべての順列を生成できるということです。最初の要素が一意であるという事実により、要素をサイクルシフトすることによって同等のものがないことが保証されるため、これは非常に簡単な解決策です。明らかに、生成するすべてのソリューションは一意でなければなりません。

明らかな問題は、シングルの要素がない場合、これが完全に崩壊することです。これを入れた主な理由は、重複を処理しないソリューションが他にもいくつかあり、これはそれらよりも効果的である（より多くのケースを解決する）ので、言及する価値があると思うからです。また、それがどのように機能するかを理解し、実装するという点でも非常に簡単です。私の推論が正しいことを願っています。;-)

さらに考えを編集する：

この原則は、ある程度の重複がある状況にまで拡張できると思います。

1 つの要素 (現在は繰り返されていると仮定) を取得すると、その順列と、一般性を失うことなく 1 つの場所で「ロック」できると仮定する前のように、どの順列がサイクル シフトの繰り返しを許可するかを調べることができます。たとえば、合計 6 つの要素があり、このセットに A が 2 回出現する場合は、次のようになります。

AAXXXX、AXAXXX、AXXAXX、AXXXAX、AXXXXA

これらの最後のものは最初のものと同じ (巡回シフト内) であるため、2 番目と 4 番目と同じように無視できます。3 番目 (AXXAXX) は 3 でサイクルして、それ自体に戻ることができるため、サイクルの可能性があります。最初の 2 つは、何回サイクルしてもサイクルを発生させることはできないため、必要な残りの要素を配布する場合は、それらが一意の配布であることを確認するだけで、サイクルごとに一意の結果が得られることが保証されます。

循環可能な 3 番目のパターン (AXXAXX) については、要素 B を調べて、それらのプロセスを繰り返す必要があります。今回は残念ながら、時間を節約するために最初の値をロックするというトリックを使用できません。

これを完全に機能するプログラムにする方法については100％確信が持てませんが、ブルートフォースを回避する方法についていくつかの考えがあります.

于 2010-08-12T14:15:18.957 に答える