2

可能な順列の半分だけを計算するアルゴリズムを探しています。たとえば、要素 abc には次の順列があります。

abc

acb

バック

紀元前

タクシー

cba

順列が別の順列の反対 (逆順) である場合、それらは同じであると見なされます。たとえば、(abc) ~ (cba) です。順列の半分だけを計算するアルゴリズムが必要です。この場合、それは (abc) (acb) (bac) または (cba) (bca) (cab) のいずれかになります。アルゴリズムによっては、3 つの異なるセットも可能だと思います。

私はこのアルゴリズムを検索しようとしましたが、順列インデックス付きの組み込み関数を使用して言語固有のアルゴリズムを見つけました。一般的な擬似コードが必要です。私はVB.NETで作業しています

ありがとうございました ！

4

3 に答える 3

4

あなたはこのようにすることができます：

  1. 二重の for ループを使用して、順列の開始と終了を修正しindex[end] > index[beginning]ます。
  2. 残りの要素のすべての順列を生成し、それらを間に配置します。

たとえば、4 つの要素の場合:

a * * b -> a c d b, a d c b
a * * c -> a b d c, a c d b
a * * d -> a b c d, a c b d
b * * c -> b a d c, b d a c
b * * d -> b a c d, b c a d
c * * d -> c a b d, c b a d

この方法で順列を生成すると、最初と最後の要素が別の順列の最後と最初の要素になることは決してなく、正確なn! / 2順列を生成しているため、すべての順列の半分しか得られないことが保証されます。

于 2013-05-19T21:48:58.420 に答える
0

お手伝いありがとう。将来誰かが必要とする場合に備えて、この問題の疑似コードを投稿します。

SET of size (n)
SUBSET of size (n-2)

for i=1 to n
    for j=i+1 to n
        create SUBSET = SET \ { SET[i] , SET[j] }
        do permutations loop, function for SUBSET
        {
          calculate a permutation P for SUBSET
          construct full permutation FP = SET[i] & P & SET[j]
          print or use FP
          continue permutations loop
        }
    next j
next i
于 2013-05-20T11:39:04.160 に答える