10

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

真正的问题：搜索空间应该包含两个元素的所有排列（N 次 el1 和 M 次 el2，其中 K=M+N），具有以下限制：

  1. 它们必须是唯一的（即我只想要 [aabbb] 一次）
  2. 我不需要任何排列的反转（即，如果我有 [aab]，我也不需要 [baa]）
  3. 我认为排列是循环的，所以 [aab] = [aba] = [baa]

如果我能够做到这一点，那么可能性的数量将大大减少。由于 K 在理想情况下会很大，因此首先生成所有排列然后根据这些标准过滤它们是不可行的。我已经完成了第一个限制（见下文），它将 Matlab 的正常排列函数（perms）的数字从 2^K 减少到 K!/N!M!，这是一个巨大的胜利。第二个限制只会将可能性的数量减少一半（在最好的情况下），但我认为第三个也应该能够真正减少可能性的数量。

如果有人知道该怎么做，最好还知道如何计算有多少可能性，那将对我有很大帮助！我更喜欢解释，但代码也很好（我可以阅读类 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 开始，对于每个旧排列减一，直到它变为零，此时它又回到 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 元手镯的子集（该子集由字符 A 的 n 和字符 B 的 m 定义）。所有手镯的集合允许 A 和 B 的数量变化。

下面的代码打印出您所追求的序列，并按词汇顺序和恒定摊销时间打印。它基于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;
}
于 2009-07-20T02:33:53.917 回答
1

我认为您想生成 2 元免费项链。请参阅此问题以获取链接、论文和一些代码。

于 2009-07-16T20:31:29.303 回答
0

如果你只有两个元素，你的空间要小得多：2^k 而不是 k!。

尝试这样的方法：

  1. 遍历从 1 到 2^k 的所有数字。
  2. 以二进制形式写出数字。
  3. 将所有 0 转换为 a，将 1 转换为 b。现在你有一个排列。
  4. 获取您的序列并通过循环排列和反转生成 2k 个序列。您只需要评估这 2k 个序列中的 1 个。
  5. 在 2k 个序列中，选择按字母顺序排在第一位的序列。
  6. 检查你的日志，看看你是否已经完成了这个。如果是这样，请跳过。
  7. 如果这是新的，请评估它，并添加到“完成”日志中。（如果空间允许，您可以将“family”的所有 2k 元素添加到完成的日志中，因此您可以将步骤（6）移到步骤（3）之后。您还可以存储数字，而不是 a 的序列和 b，在“完成”日志中。）

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

于 2009-07-16T13:15:26.050 回答
0

您正在寻找与订单无关的组合。Matlab 用 K!/N!M! 正确计算了这个！这正是计算组合数量的公式。

于 2009-07-16T13:17:42.613 回答
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

我对 k-ary 案例的想法如下：

参考：

  1. Python 算法：项链生成 / 循环排列
  2. 如何使用生成器在 Python 中生成没有“反向重复”的列表排列
def findPermutations(n):
    """
    Descriptions
    ------------
    Find all possible permutations for a given positive integers n such that the elements are 0, 1, 2,..., n-1,  
    excluding mirrored or circular repetitions.
    Example: if n = 3, there in only one possible permutation:
            [0, 1, 2]
    Parameters
    ----------
    n : positive integers

    Returns
    -------
    x : list
        x[i][:] refers to the site order in the ith permutation
    """
    
    ls = np.arange(0,n).tolist()
    permutations = []
    for p in itertools.permutations( ls[1:] ):
        if p <= p[::-1]:
            permutations += [p]
           
    for end in permutations:
        yield [ls[0]] + list(end) 

x = list(findPermutations(4))

输出应该是

[[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3]]
于 2021-07-30T16:24:56.387 回答