代码之家 › 专栏 › 技术社区 › Jordi

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

necklaces combinatorics permutation algorithm

Jordi · 技术社区 · 15 年前

一些背景:我正在写一个或多或少的蛮力搜索算法来解决我的问题。为了做到这一点,我需要生成并评估所有的可能性,找出哪一个是最好的。由于评估实际上需要一些时间,我希望生成尽可能少的完全覆盖搜索空间的解决方案。而且,我能做的元素越多越好。对于任何数字k,通常都有k!对于大于~10的数字,排列和生成它们都是困难的。

实际问题:搜索空间应包含两个元素的所有排列(n乘以el1和m乘以el2,其中k=m+n),并有以下限制:

它们必须是独一无二的(即我只想要[A A A B B]一次)
我不需要任何相反的排列(即,如果我有[A A A B],我也不需要[B A A A])
我认为排列是圆形的,所以[A A A B]=[A B A]=[B A A]

如果我能做到这一点,可能性的数量将大大减少。因为k在理想情况下是大的,所以首先生成所有排列,然后根据这些标准过滤它们是不可行的。我已经完成了第一个限制(见下文),它将matlab的正常置换函数(perms)的2^k缩减为k!/N!M!这是一个巨大的胜利。第二个限制只会将可能性减少一半(在最好的情况下),但我认为第三个限制也应该能够真正减少可能性的数量。

如果有人知道怎么做,最好也知道如何计算有多少可能性,那将对我有很大帮助!我更喜欢解释,但代码也很好(我可以阅读C语言,Java(脚本),Python,Ruby,Lisp/Stand)。

对于感兴趣的人:这里是我目前为止只得到唯一排列的算法:

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开始,对于每个旧排列,此数字将减少一个,直到变为零,此时它将返回m等(仅在m>=n时有效)。因此,如果你想计算n=3和m=3的排列,并且你有10个n=2和m=3的排列,它们的收益将是[4 3 2 1 3 2 1 2 2 1 1 1 1]。从排列的长度中减去这个增益,就得到了一个索引,在这个索引中可以开始插入新的元素,而不需要重复。

5 回复 | 直到 15 年前

caf 15 年前

你所追求的是2元手镯的一个子集(该子集由字符A的N和字符B的M精确定义)。一套 全部的 手镯可以让A和B的数量不同。

下面的代码打印出您所追求的序列,并以词法顺序和恒定的摊销时间进行打印。它基于 this paper by Sawada -要了解它是如何工作的,请参阅那篇论文。

#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;
}

Community pid 7 年前

我想你想制作2元的免费项链。见 this question 用于链接、论文和一些代码。

Michael Donohue Reno 15 年前

您正在寻找组合-它们是顺序独立的。matlab用k正确地计算了这一点!n!M!这正是计算组合数的公式。

yrral 15 年前

假设您有一个包含所有排列的数组,您可以将数组的内容放入哈希。然后这会起作用(有点蛮力,但这是一个开始):

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

Mike Kantor 15 年前

如果你只有两个元素,那么你的空间要小得多:2^k而不是k!.

尝试这样的方法:

运行1到2^k之间的所有数字。
用二进制形式写这个数字。
把0都翻译成A,把1翻译成B。现在你有了一个排列。
取你的序列,通过循环排列和反转生成2K序列。您只需要评估其中1个2K序列。
在2K序列中,选择按字母顺序排序的序列。
检查您的日志,看看您是否已经完成了这项工作。如果是,跳过。
如果这个是新的,评估它,并添加到“完成”日志中。(如果空间允许,可以将“族”的所有2K元素添加到完成日志中,这样就可以在步骤(3)之后将步骤(6)右移。您还可以在“完成”日志中存储数字,而不是A和B的序列。)

如果你有j个可能的符号,而不仅仅是两个,那么做同样的事情,但是使用基数j而不是基数2。