获得所有可能的独特排列 [英] Get all the possible unique permutations

问题描述

小数组包含一些符号，例如 ['^'，'^'，'>'，'>'，'+'，'< '，'<'] ，我怎样才能获得所有不同的排列？我知道类似的问题已被提出（并且已经有一些很好的答案），例如：

Having a small array with some symbols like ['^','^','>','>','+','<','<'], how can I get all the different permutations? I know that similar questions have been asked (and already have some excellent answers) like:

• 尽可能多地随机播放数组


• JavaScript中的排列？

• Shuffle an array as many as possible
• Permutations in JavaScript?

但是它们不会显示唯一结果。我怎样才能有效只获得一次可能的结果？

however they don't present unique results. How can I efficiently get each possible outcome only once?

推荐答案

对于小阵列，你可以使用其中一个引用的算法，将每个排列映射到一个字符串，并将整个数组抛出到设置以丢弃重复项。类似于：

For a small array, you can use one of the referenced algorithms, map each permutation to a string, and throw the whole array into a Set to discard duplicates. Something like:

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 符号。

否则，请参阅此处和此处了解可以转换为JavaScript的各种方法。

Otherwise, see here and here for a variety of approaches that you can translate to JavaScript.

一种流行的方法是 Pandita算法使用连续规则列举字典顺序中的排列，实际上只生成唯一排列。 此处和here 。这是一个JavaScript（ES6）实现：

One popular method is the 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. Here's a JavaScript (ES6) implementation:

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 函数转换数组 - 如果数组已经是词典最大值，则放入词典后继词或词典最小值。在第一种情况下，它返回 true ，否则 false 。这允许您循环遍历从最小（已排序）数组开始的所有排列，直到 nextPermutation 翻转并返回 false 。

The nextPermutation function transforms an array in-place into either the lexicographic successor, or the lexicographic minimum if the array is already the lexicographic maximum. In the first case, it returns true, otherwise false. This allows you to cycle through all the permutations starting from the minimum (sorted) array until nextPermutation rolls over and returns false.

这篇关于获得所有可能的独特排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！