唯一的排列没有镜像或圆重复

Question

一些背景：我正在写一个或多或少暴力搜索算法为解决一个问题，我有。为了做到这一点，我需要生成和评估所有可能性，以找出哪些是最好的。由于评估实际上需要一些时间我会更喜欢以产生尽可能少的解决方案，完全复盖了我的搜索空间。此外，更多的因素我可以这样做，越好。对任何数目K那里通常是K!排列组合，并产生它们的所有将硬数字高于-10.

真正的问题：搜索空间应包含所有排列的两个要素(N次el1和M次el2，其中K=M+N)，这些限制：

1. 他们必须是独特的(即我只想[a b b]一旦)
2. 我不需要反的任何排列(即如果我有的信[b]，我也不需要[一个])
3. 我考虑排列以是圆的，这样的信[b]=的信[b]=[b一个一]

如果我能够做到这一点，可能性的数量将减少大幅下降。由于K将理想的情况是大的，是不可行的第一次产生的所有排列，然后过滤器他们根据这些标准。我已经完成了第一个限制(见下文)，它削减的数量从2^K Matlab的正常排列功能(权限)至K!/N!M!, 这是一个巨大的胜利。第二个限制将只数量减少可能性中的一半(在最好的情况下)，但我认为第三也应该能够真正的削减量的可能性。

如果有人知道如何做到这一点，最好还是如何计算有多少可能会有的，那将会帮助我很多的!我会更喜欢一种解释，但是代码也被罚款(我可以读C-喜欢的语言，Java(剧本)，蟒蛇，红宝石，List/方案)。

---

对于有兴趣：这里是的算法对于只得到独特的排列，我们迄今为止:

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,然后你可以用它们要找到排列N and M通过插入e1到他们。你不能只是插入无处不在，因为然后你会得到重复。我不知道为什么这一工程，但可以计算数量的新的可能性，你将会产生从一个老人(我把这个叫做'收益').这个号码开始在M+1的第一次老置换和减少通过一个为每个老置换，直到它会成为零，在这一点上，它可以追溯到米，等等。(只适用，如果M>=N)。所以如果你想要计算的排列N=3和M=3和你有10排列N=2和M=3，他们的收益将[4 3 2 1 3 2 1 2 1 1].减去这一增长的置换，以及你获得的索引可以开始插入新的元素，而无需作重复。

Answer 1

什么你是之后的一个子集2元的手镯(子集定义通过确切n字和m的符B)。该组 所有 手镯允许的数量的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;
}

Answer 2

我觉得你想要产生2-ary免项链。看看 这个问题 链接，文件，和一些代码。

Answer 3

你是在寻找合其是以独立的。Matlab计算出这一正确K!/N!M!这是精确的计算公式组合的数量。

Answer 4

假设你有一系列不同的排列组合，可以把的内容列入一散列。然后这将工作(一个小小的暴力，但它是一个开始):

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

Answer 5

如果你只有两个元素，你的空间大小：2^k而不是k!.

尝试一种办法是这样的：

1. 通过所有数从1到2^k。
2. 写信的数量在二进制形式。
3. 翻译所有0到1至b。现在你有一个置换。
4. 把你的顺序，并生成2k序列通过环状排列的逆转。你只需要评估1这些2k序列。
5. 在2k序列，选择一个各种各样的第一个字母顺序排列。
6. 检查你的记录来看，如果你已经做了这个。如果是这样，跳过。
7. 如果这个人是新的，评估，及添加到"完成"日志。(如果空间允许，你可以加入所有2k元件的"家庭"的完成日志，这样你可以移动的步骤(6)正后的步骤(3)。你也可以储存的数量，而不是序列a和b、在"完成"日志。)

如果你有j可能的符号，而不仅仅是两个，做同样的事情，但使用基j而不是基2.