查找并行化 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

您可以创建一个 table 阶乘。如果使用 64 位无符号整数，则最大值为 20！ = 2432902008176640000，或者对于 32 位无符号整数，最大值为 12！ = 479001600，所以 table 很小。

数学部分的先前话题：

https://math.stackexchange.com/questions/60742/finding-the-n-th-lexicographic-permutation-of-a-string

Answer 2

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

#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. Since 13! > 2³², 21! > 2⁶⁴, and 35! > 2¹²⁸, there are only a very few possible results for 32, 64, or 128-bit unsigned integer permutation_t types, it would be better to simply use an array lookup for the factorials instead (as ).

的一个缓慢但谨慎的实现

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

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

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

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

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

Finding nth permutation for parallelized C/C++

c

c++

algorithm

parallel-processing

mpi