获取大量元素的第 n 个排列

Question

我想编写一个 JavaScript 程序，以所有可能的排列（每秒 10 个排列）排列一组 36 个数字。排列这些数字的阶乘方式有 36 种。

我知道我的节目要到地球的尽头才会结束:)（这正是我想要展示的）。

它以以下顺序开始：

排列：0,1,2,3,4,5,6,...,32,33,34,35
排列：0,1,2,3,4,5,6,...,32,33,35,34
排列：0,1,2,3,4,5,6,...,32,34,33,35

.....（这里还有很多排列）....

有没有一种方法可以计算出第 5'595'000'000 个（自 2000 年 1 月 1 日以来以分秒为单位的时间）排列而不计算之前的所有排列？计算之前的那些真的会花很长时间！

此外，如果我知道第 5'595'000'000 个排列，我需要一种方法来计算下一个排列。

我发现的所有排列算法一次计算所有排列。这不是一个有这么多排列的选项。

这是可能的还是我注定要失败？

Answer 1

这里有两个函数：

getPermutationByRank：通过排列数得到一个排列（数组）。灵感来自 this answer;
nextPermutation：将给定排列变异为顺序中的下一个排列。灵感来自 this answer

这基本上就是你所需要的，但我添加了一个生成器，它使用上述两个函数生成从某个等级开始的排列。

最后，格式化函数将给定的排列转换为字符集（10 位数字 + 26 个字母 = 36 个不同的字符）。

该代码段计算自 2000 年 1 月 1 日以来的当前分秒数并输出相应的排列，每隔分秒将其更新为下一个排列：

// See 
function getPermutationByRank(n, rank) {
    // Sageguard for inaccurate calculations: rank <= 9007199254740991
    if (rank > Number.MAX_SAFE_INTEGER) throw "Too large rank for JavaScript";
    var perm = (function loop(i, fact) {
        // Calculate factorials and subtract from rank from highest to lowest
        return i > n ? [] :
               [loop(i+1, fact * i).concat(Math.floor(rank / fact) % n),
                rank = rank % fact][0];
    })(1, 1);
    // Readjust values to obtain the permutation
    // start from the end and check if preceding values are lower
    for (let k = n - 1; k > 0; --k)
      for (let j = k - 1; j >= 0; --j)
         if (perm[j] <= perm[k])
            perm[k]++;
    return perm;
}

// See 
function nextPermutation(perm) {
    // Find longest non-increasing suffix
    var i = perm.length - 2;
    while (i >= 0 && perm[i] >= perm[i + 1])
        i--;
    // Now i is the head index of the suffix
    
    // Are we at the last permutation already?
    if (i < 0) return; // no more permuations
    
    // Let perm[i] be the pivot
    // Find rightmost element that exceeds the pivot
    var j = perm.length - 1;
    while (perm[j] <= perm[i])
        j--;
    // Now the value perm[j] will become the new pivot
    // Assertion: j >= i
    
    // Swap the pivot with j
    [perm[i], perm[j]] = [perm[j], perm[i]];
    
    // Reverse the suffix
    j = perm.length - 1;
    i++;
    while (i < j) {
        [perm[i], perm[j]] = [perm[j], perm[i]];
        i++;
        j--;
    }
    return perm;
}

// Create a generator using above two functions:
function* generatePermutationsFrom(n, rank) {
    var perm = getPermutationByRank(n, rank);

    yield perm;
    while (nextPermutation(perm)) {
        yield perm;
    }
}

// Utility functions for OP specific requirements
function deciSecondsSince(dt) {
    return Math.floor((Date.now() - dt.getTime())/100);
}

function permToString(perm) {
    var chars = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
    return perm.map ( v => chars[v] ).join('');
}

var deciSecs = deciSecondsSince(new Date('2000-01-01')); // ~5293000000 
var iter = generatePermutationsFrom(36, deciSecs);

// Output next permuation every decisecond:
document.body.textContent = permToString(iter.next().value);
setInterval(function () {
    document.body.textContent = permToString(iter.next().value);
}, 100);

body { font-family: monospace }

免责声明：

这适用于您询问的排名数字（如 5293000000），但如果排名超过 JavaScript 可以提供的精度，结果将是错误的。事实上，在第一个函数中计算的阶乘只能精确到 18!，之后它们就会失去精度。这对算法没有影响，只要您的排名在 JavaScript 支持的范围内（大约 16 位）。第一个函数因此有了保障。
setInterval 不是一种与时间保持同步的非常可靠的方法，因此一段时间后，迭代次数可能与自那以后经过的实际分秒数不同步第一次迭代。但这对您的目的来说似乎并不那么重要。如果是，那么看看 this answer 来弥补这种漂移 .

获取大量元素的第 n 个排列

Get the n-th permutation of a large set of elements

javascript

algorithm

permutation

largenumber