マルチセットのすべての一意の円形順列を生成するアルゴリズムはありますか？

StackOverflow https://stackoverflow.com/questions/3467914

質問

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

Aの場合、Aの場合、P（a）がA. P（a）のすべての可能な順列のセットを示すと、同等のクラスである分離サブセットに自然に分割され、等価関係は「円形シフトによって関連する可能性があります」。それらのそれぞれから正確に1つのメンバーを生成することにより、これらすべての等価クラスを列挙します。

たとえば、マルチセット{0、1、1、2}を検討してください。順列「0112」と「1201」は一意の順列ですが、後者は前者を円形に変えることで見つけることができ、その逆も同様です。目的のアルゴリズムは両方を生成してはなりません。

もちろん、ブルートフォースアプローチが可能です。マルチセット順列アルゴリズムのいずれかを使用して、円形の複製に関係なく順列を生成し、以前の結果と比較して見つかった重複を破棄します。ただし、これは実際には非効率的である傾向があります。目的のアルゴリズムには、簿記ゼロではないにしても、最小限の最小限のものが必要です。

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

役に立ちましたか？

解決

サワダのアルゴリズム

他のヒント

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

aに1つの要素のみが含まれている場合、p（a）には1つの順列も含まれます。 Aが2つの要素しか含まれていない場合、同じ作品を見るのは簡単です。

ここで、n要素を使用するAのすべてのp（a）が既にあると仮定し、1つの要素を追加します。 P（a）の順列のいずれかのnスポットのいずれかに到達できます。

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

編集：私は、Aが重複する要素を含むかもしれないという事実を無視したことを知っていますが、それでもその部分について考えています:)

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

問題を直感的に理解するために、私たちはこの比phorを採用できると思います。壁の時計を視覚化しますが、顔に12個の位置を持つ代わりに、nはセットの要素の数です。

次に、各等価クラスは、クロックフェイスの位置へのAの要素の単なる割り当てにすぎません。

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

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

これで、アルゴリズムは、たとえばa = {a、b、c、d}に4つの要素があり、視覚の12、3、6、9のポジションにそれぞれ4つの要素があったとすることです。明快さ。次に、最初の操作はAとbを交換することです。次に、aとc、次にaとd、次にbに移動して、3位の要素と交換します。現在はcです。

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

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

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

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

さらなる考えのために編集：

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

1つの要素を使用すると（今が繰り返されていると仮定します）、その順列だけを見ることができ、どのサイクルが一般性を失うことなく「ロック」できると仮定する前に、サイクルシフトの繰り返しを可能にします。たとえば、このセットに合計6つの要素があり、Aが2回表示される場合は、次のことができます。

aaxxxx、axaxxx、axxaxx、axxxax、axxxxa

これらの最後は、最初の（循環シフト内）と同じであるため、無視できます。 3番目の（axxaxx）は、自体に戻るために3つずつサイクリングできますので、サイクルの可能性があります。最初の2つは、何回サイクリングしてもサイクルを生み出すことはできないため、残りの要素を分配するだけで、それらが一意の分布であることを確認し、サイクル結果によって一意になることが保証されます。

サイクリングできる3番目のパターン（AxxAxx）の場合、要素Bを調べて、それらのプロセスを繰り返す必要があります。今回は、時間を節約するために最初の値をロックするトリックを使用することができないでしょう。

これを完全に機能するプログラムにどのように作成するかは100％確信していませんが、ブルートフォースを避ける方法についてのいくつかのトゥーグスです。

ここでは、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']
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top