10

いくつかの背景: 私は、私が抱えている問題を解決するための多かれ少なかれ力ずくの検索アルゴリズムを書いています。これを行うには、すべての可能性を生成して評価し、最適なものを見つける必要があります。評価には実際には時間がかかるため、検索スペースを完全にカバーするソリューションをできるだけ生成しないようにします。さらに、これを実行できる要素が多ければ多いほど良いです。任意の数 K に対して、通常は K です! 順列、およびそれらすべてを生成することは、~10 を超える数では困難です。

実際の問題: 検索空間には、2 つの要素 (N 回の el1 と M 回の el2、ここで K=M+N) のすべての順列が含まれている必要がありますが、次の制限があります。

  1. それらは一意である必要があります (つまり、[aabbb] は 1 回だけ必要です)
  2. 順列の逆は必要ありません (つまり、[aab] がある場合、[baa] も必要ありません)。
  3. 順列は循環的であると考えているため、[aab] = [aba] = [baa]

これができれば、可能性の数は大幅に減少します。K は理想的には大きいため、最初にすべての順列を生成してから、これらの基準に従ってそれらをフィルター処理することは現実的ではありません。私はすでに最初の制限 (以下を参照) を行っており、Matlab の通常の順列関数 (perms) の 2^K から K!/N!M! に数を減らしました。これは大きな勝利です。2 番目の制限は可能性の数を半分に削減するだけですが (最良の場合)、3 番目の制限も可能性の数を実際に削減できるはずだと思います。

誰かがそれを行う方法を知っていて、できれば可能性の数を計算する方法を知っていれば、それは私を大いに助けてくれるでしょう! 説明を希望しますが、コードも問題ありません (C に似た言語、Java(Script)、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] になります。
4

6 に答える 6

3

あなたが求めているのは、2-aryブレスレットのサブセットです（サブセットは、文字Aのnと文字Bのmによって正確に定義されます）。すべてのブレスレットのセットでは、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;
}
于 2009-07-20T02:33:53.917 に答える
0

すべての順列の配列があると仮定すると、配列の内容をハッシュに入れることができます。次に、これが機能します（少し力ずくですが、その始まりです）：

for each (element in array of permutations){
  if (element exists in hash){
    remove each circular permutation of element in hash except for element itself
  }
}
于 2009-07-16T13:24:21.733 に答える
0

順序に依存しない組み合わせを探しています。Matlab はこれを K!/N!M! で正しく計算しました。これは、組み合わせの数を計算するための正確な式です。

于 2009-07-16T13:17:42.613 に答える
0

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

次のようなアプローチを試してください。

  1. 1 から 2^k までのすべての数字を実行します。
  2. 数値を 2 進数で書きます。
  3. すべての 0 を a に、1 を b に変換します。これで順列ができました。
  4. シーケンスを取得し、巡回順列と反転によって 2k シーケンスを生成します。これらの 2k シーケンスの 1 つだけを評価する必要があります。
  5. 2k のシーケンスの中で、最初にアルファベット順にソートされるものを選択します。
  6. ログをチェックして、これを既に行っているかどうかを確認してください。その場合は、スキップしてください。
  7. これが新しい場合は、評価して「完了」ログに追加します。(スペースが許せば、「ファミリー」の 2k 要素すべてを完了ログに追加できるので、ステップ (6) をステップ (3) の直後に移動できます。a のシーケンスではなく、番号を保存することもできます。および b は「完了」ログに記録されます。)

可能なシンボルが 2 つではなく j 個ある場合は、同じことを行いますが、基数 2 ではなく基数 j を使用します。

于 2009-07-16T13:15:26.050 に答える