c++ - 查找并行化 C/C++ 的第 n 个排列

Question

我目前正在寻找一种方法，通过使用函数来按字典顺序查找数组的第 n 个排列。我有一个使用 C++ 库中的 next_permutation 编写的顺序代码(其余代码是普通的旧 C)，但由于 next_permutation 的工作方式，它是不仅效率低下，而且很难在代码的并行版本中使用。我正在使用 Open MPI，因此每个进程都必须使用 next_permutation 并且此时数学变得非常困惑。此外，next_permutation 每次最多计算 n 次，因此每个进程必须执行比应有的更多的计算。我听说过使用因式分解来找到第 n 个排列，但我一直无法找到有关其使用的任何信息。 C/C++ 库中是否有提供因子的函数，或者是否有我能找到的很好的资源来执行此操作？有没有更好的方法来找到特定数组的第 n 个排列？

例如:

数组[3] = {1, 2, 3}

factoradicFunc(3) --> 2, 1, 3

factoradicFunc(4) --> 2, 3, 1

等等

Answer 1

我已经在其他地方发布了以下示例，但让我在这里重复一遍:

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

typedef char           element_t;
typedef unsigned long  permutation_t;

static permutation_t factorial(const permutation_t n)
{
    permutation_t i, result = 1;
    for (i = 2; i <= n; i++) {
        const permutation_t  newresult = result * i;
        if ((permutation_t)(newresult / i) != result)
            return 0;
        result = newresult;
    }
    return result;
}

int permutation(element_t *const        buffer,
                const element_t *const  digits,
                const size_t            length,
                permutation_t           index)
{
    permutation_t  scale;
    size_t         i, d;

    if (!buffer || !digits || length < 1)
        return errno = EINVAL;

    scale = factorial(length);
    if (!scale)
        return errno = EMSGSIZE;
    if (index >= scale)
        return errno = ENOENT;

    /* Copy original ordered set to mutable buffer */     
    memmove(buffer, digits, length * sizeof (element_t));

    for (i = 0; i < length - 1; i++) {
        scale /= (permutation_t)(length - i);
        d = index / scale;
        index %= scale;
        if (d > 0) {
            const element_t c = buffer[i + d];
            memmove(buffer + i + 1, buffer + i, d * sizeof (element_t));
            buffer[i] = c;
        }
    }

    return 0;
}

factorial() 函数只是 factorial 的一个缓慢但谨慎的实现.从 13 岁开始! > 2³², 21! > 2⁶⁴，和 35! > 2¹²⁸，对于 32、64 或 128 位无符号整数 permutation_t 类型，只有极少数可能的结果，最好简单地使用数组查找取而代之的是阶乘(如 rcgldr already mentioned )。

permutation(buffer, digits, length, index) 函数采用长度为 length 的目标 buffer，并用 index第 digits 的排列。 (digits 是只读的，不可变的。)

这不是最快的实现，但它会在 O(length) 时间复杂度内计算任何排列(忽略 memmove() 操作；O (length²) 如果您考虑 memmove())。它是次优的，因为它使用 memmove() 对目标 buffer 中的项目重新排序，并且每个元素需要两次除法(和一个具有相同除数的模数) .

考虑到最大实际长度限制(12、20 或 34 个元素，取决于 permutation_t 类型的大小)，memmove() 的使用不是一个问题(因为数据在一个或最多几个缓存行中)。

这是线程安全的，只要同一时间只有一个线程操作同一个目标buffer；多个线程从同一源 digits 缓冲区生成不同的目标 buffer 是线程安全的。