ミラー化または円形の繰り返しのないユニークな順列

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

質問

背景：私は、私が持っている問題を解決するために多かれ少なかれブルートフォース検索アルゴリズムを書いています。これを行うには、すべての可能性を生成して評価して、どれが最適かを調べる必要があります。評価には実際に時間がかかるので、検索スペースを完全にカバーする可能性のあるソリューションをほとんど生成したいと思います。さらに、これを行うことができる要素が多いほど、任意の数のkについて、通常はkがあります！順列、およびそれらをすべて生成することは、〜10を超える数値では困難です。

実際の問題：検索スペースには、2つの要素のすべての順列（n倍EL1およびm回EL2、ここでk = m+n）を含む必要があります。

  1. 彼らはユニークでなければなりません（つまり、私は[aabbb]が一度しか欲しいです）
  2. 順列の逆は必要ありません（つまり、[aab]がある場合、[baa]も必要ありません）
  3. 私は順列が円形であると考えているので、[aab] = [aba] = [baa

これを行うことができれば、可能性の数は劇的に減少します。 Kは理想的には大きいため、最初にすべての順列を生成してから、これらの基準に従ってフィルタリングすることは実行可能ではありません。私はすでに最初の制限を行っています（以下を参照）、Matlabの通常の順列関数（Perms）の2^kからK！/n！M！までの数を削減します。これは大きな勝利です。 2番目の制限は、可能性の数の数を半分に削減します（最良の場合）が、3番目の可能性の数を実際に減らすことができるはずだと思います。

誰かがそれを行う方法を知っているなら、できれば、いくつの可能性があるかを計算する方法もできれば、それは私を大いに助けてくれるでしょう！私は説明を好みますが、コードも問題ありません（私はCのような言語、Java（スクリプト）、Python、Ruby、Lisp/Schemeを読むことができます）。

興味のある人：これは、私がこれまでに持っているユニークな順列のみを取得するためのアルゴリズムを紹介します。

function genPossibilities(n, m, e1, e2)
     if n == 0
         return array of m e2's
     else
         possibilities = genPossibilities(n-1, m, e1, e2)
         for every possibility:
             gain = number of new possibilities we'll get for this smaller possibility*
             for i in max(0,(m+n-gain))
                 if possibility(i) is not e1
                     add possiblity with e1 inserted in position i
         return new possibilities
  • n-1とmのすべての順列がある場合は、それらを使用して、e1をそれらに挿入することにより、nとmの順列を見つけることができます。ただし、どこにでも挿入することはできません。なぜなら、複製が得られるからです。なぜこれが機能するのかはわかりませんが、古いものから生成する新しい可能性の数を計算できます（これを「ゲイン」と呼びます）。この数値は、最初の古い順列のM+1で始まり、各古い順列がゼロになるまで1つずつ減少し、その時点でMなどに戻ります（M> = Nの場合にのみ機能します）。したがって、n = 3とm = 3の順列を計算し、n = 2とm = 3の10の順列がある場合、それらのゲインは[4 3 2 1 3 2 1 2 1 1]になります。順列の長さからこのゲインを減算すると、複製を作成せずに新しい要素の挿入を開始できるインデックスを取得します。
役に立ちましたか？

解決

あなたが望んでいるのは、2-areブレスレットのサブセットです（サブセットは、文字bの文字Aとmの正確なNで定義されます）。のセット 全て ブレスレットは、AとBの数を変えることができます。

次のコードは、あなたが後にしているシーケンスを印刷し、字句順で一定の償却時間でそれを行います。一般的なアルゴリズムに基づいています 佐藤によるこの論文 - それがどのように機能するかについての説明については、その紙を参照してください。

#include <stdlib.h>
#include <stdio.h>

static int *a;
static int n;

void print_bracelet(int n, int a[])
{
    int i;

    printf("[");
    for (i = 0; i < n; i++)
        printf(" %c", 'a' + a[i]);
    printf(" ]\n");
}

int check_rev(int t, int i)
{
    int j;

    for (j = i+1; j <= (t + 1)/2; j++)
    {
        if (a[j] < a[t-j+1])
            return 0;
        if (a[j] > a[t-j+1])
            return -1;
    }

    return 1;
}

void gen_bracelets(int n_a, int n_b, int t, int p, int r, int u, int v, int rs)
{
    if (2 * (t - 1) > (n + r))
    {
        if (a[t-1] > a[n-t+2+r])
            rs = 0;
        else if (a[t-1] < a[n-t+2+r])
            rs = 1;
    }
    if (t > n)
    {
        if (!rs && (n % p) == 0)
            print_bracelet(n, a + 1);
    }
    else
    {
        int n_a2 = n_a;
        int n_b2 = n_b;

        a[t] = a[t-p];

        if (a[t] == 0)
            n_a2--;
        else
            n_b2--;

        if (a[t] == a[1])
            v++;
        else
            v = 0;

        if ((u == (t - 1)) && (a[t-1] == a[1]))
            u++;

        if ((n_a2 >= 0) && (n_b2 >= 0) && !((t == n) && (u != n) && (a[n] == a[1])))
        {
            if (u == v) {
                int rev = check_rev(t, u);

                if (rev == 0)
                    gen_bracelets(n_a2, n_b2, t + 1, p, r, u, v, rs);

                if (rev == 1)
                    gen_bracelets(n_a2, n_b2, t + 1, p, t, u, v, 0);
            }
            else
                gen_bracelets(n_a2, n_b2, t + 1, p, r, u, v, rs);
        }

        if (u == t)
            u--;

        if (a[t-p] == 0 && n_b > 0)
        {
            a[t] = 1;

            if (t == 1)
                gen_bracelets(n_a, n_b - 1, t + 1, t, 1, 1, 1, rs);
            else
                gen_bracelets(n_a, n_b - 1, t + 1, t, r, u, 0, rs);
        }
    }
}

int main(int argc, char *argv[])
{
    int n_a, n_b;

    if (argc < 3)
    {
        fprintf(stderr, "Usage: %s <a> <b>\n", argv[0]);
        return -2;
    }

    n_a = atoi(argv[1]);
    n_b = atoi(argv[2]);

    if (n_a < 0 || n_b < 0)
    {
        fprintf(stderr, "a and b must be nonnegative\n");
        return -3;
    }

    n = n_a + n_b;
    a = malloc((n + 1) * sizeof(int));

    if (!a)
    {
        fprintf(stderr, "could not allocate array\n");
        return -1;
    }

    a[0] = 0;

    gen_bracelets(n_a, n_b, 1, 1, 0, 0, 0, 0);

    free(a);
    return 0;
}

他のヒント

2つの無料のネックレスを生成したいと思います。見る この質問 リンク、論文、およびいくつかのコード用。

あなたは組み合わせを探しています - それは独立しています。 Matlabはこれをk！/n！mで正しく計算しました！これはまさに組み合わせの数を計算するための式です。

すべての順列の配列があると仮定すると、配列の内容をハッシュに入れることができます。その後、これは機能します（少しブルートフォースですが、スタート）：

for each (element in array of permutations){
  if (element exists in hash){
    remove each circular permutation of element in hash except for element itself
  }
}

2つの要素しかない場合、スペースははるかに小さくなります：2^kではなく2^k！。

このようなアプローチを試してみてください：

  1. 1〜2^kのすべての数値を実行します。
  2. バイナリ形式で番号を書きます。
  3. すべての0をaおよび1sにbに変換します。これで、順列ができました。
  4. シーケンスを取り、周期的な順列と反転により2Kシーケンスを生成します。これらの2Kシーケンスのうち1つを評価する必要があります。
  5. 2Kシーケンスの中から、最初にアルファベット順にソートするシーケンスを選択します。
  6. ログを確認して、すでにこれを行っているかどうかを確認してください。もしそうなら、スキップします。
  7. これが新しい場合は、それを評価し、「完了」ログに追加します。 （スペースが許可されている場合は、「ファミリー」のすべての2K要素を完了ログに追加できるため、ステップ（6）をステップ（3）の直後に移動できます。およびBは、「完了」ログで。）

j可能なシンボルを2つだけではなく持っている場合、同じことをしますが、ベース2ではなくベースJを使用します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top