获取所有可能的唯一排列

Question

有一个 small 数组和一些像 ['^','^','>','>','+','<','<'] 这样的符号，我怎样才能得到所有不同的排列？我知道有人问过类似的问题（并且已经有了一些很好的答案），例如：

Shuffle an array as many as possible
Permutations in JavaScript?

但是他们没有提供独特的结果。我怎样才能有效地获得每个可能的结果一次？

Answer 1

好吧，独特的结果问题显然会成为效率杀手，因为您每次创建新排列时都必须检查结果列表。至于算法，它的工作方式与其他排列算法基本相同，但您的删除重复标准将涉及更多检查。如果数组的大小很小，效率应该不是一个大问题。如果已经找到的值不添加到数组中，只需循环遍历答案数组。加快此检查过程的一种方法是确定一种对答案数组进行排序的方法。例如 ^ 总是在 * 之前出现在 ( 然后你不必每次都检查整个数组。还有其他方法可以加快速度，但在一天结束时它仍然是一个非常计算昂贵的要求。因为你array 很小，它根本不重要，除非你计划做这个排列 ALOT

Answer 2

对于小型数组，您可以使用其中一种参考算法，将每个排列映射到一个字符串，然后将整个数组放入 Set 中以丢弃重复项。类似于：

let a = ['^','^','>','>','+','<','<'];
let ps = permutations(a);  // return value should be array of arrays.
let qs = ps.map(p => p.join(""));
let s = new Set(qs);

这对于具有 < 10 个符号的数组应该可以正常工作。

否则，请参阅 here and here 了解可以转化为 JavaScript 的各种方法。

一种流行的方法是Pandita algorithm which enumerates permutations in lexicographic order using a succession rule, effectively only generating "unique" permutations. An short explanation of this approach is given here and here。这是一个 JavaScript (ES6) 实现：

function swap(a, i, j) {
    const t = a[i];
    a[i] = a[j];
    a[j] = t;
}

function reverseSuffix(a, start) {
    if (start === 0) {
        a.reverse();
    }
    else {
        let left = start;
        let right = a.length - 1;

        while (left < right)
            swap(a, left++, right--);
    }
}

function nextPermutation(a) {
    // 1. find the largest index `i` such that a[i] < a[i + 1].
    // 2. find the largest `j` (> i) such that a[i] < a[j].
    // 3. swap a[i] with a[j].
    // 4. reverse the suffix of `a` starting at index (i + 1).
    //
    // For a more intuitive description of this algorithm, see:
    //   https://www.nayuki.io/page/next-lexicographical-permutation-algorithm
    const reversedIndices = [...Array(a.length).keys()].reverse();

    // Step #1; (note: `.slice(1)` maybe not necessary in JS?)
    const i = reversedIndices.slice(1).find(i => a[i] < a[i + 1]);

    if (i === undefined) {
        a.reverse();
        return false;
    } 

    // Steps #2-4
    const j = reversedIndices.find(j => a[i] < a[j]);
    swap(a, i, j);
    reverseSuffix(a, i + 1);
    return true;
}

function* uniquePermutations(a) {
    const b = a.slice().sort();

    do {
        yield b.slice();
    } while (nextPermutation(b));
}

let a = ['^','^','>','>','+','<','<'];
let ps = Array.from(uniquePermutations(a));
let qs = ps.map(p => p.join(""));

console.log(ps.length);
console.log(new Set(qs).size);

nextPermutation 函数将数组就地转换为字典序后继数组，或者如果数组已经是字典序最大值，则转换为字典序最小值。在第一种情况下，它 returns true，否则 false。这允许您从最小（已排序）数组开始循环遍历所有排列，直到 nextPermutation 翻转和 returns false。

获取所有可能的唯一排列

Get all the possible unique permutations

javascript

algorithm

permutation