JavaScript 中具有重复元素的唯一排列

Question

假设我们有元素 0 和 1，它们可以出现多次，例如00 00 11, 00 00 11 11or 01 11（分成 2 组以提高可读性）。我已经有一个函数来生成所有唯一的排列：class UniqueElement {  constructor(value, occurrences) {    this.value = value;    this.occurrences = occurrences;  }}function permUnique(elements) {  let set = new Set(elements);  let listunique = Array.from(set).map((i) => new UniqueElement(i, elements.filter((el) => el === i).length));  let u = elements.length;  return permUniqueHelper(listunique, "0".repeat(u).split("").map((i) => parseInt(i)), u - 1);}function* permUniqueHelper(listunique, result_list, d) {  if (d < 0) {    yield [...result_list];  } else {    for (const i of listunique) {      if (i.occurrences > 0) {        result_list[d] = i.value;        i.occurrences--;        for (const g of permUniqueHelper(listunique, result_list, d - 1)) yield g;        i.occurrences++;      }    }  }}// call like:// permUnique([0,0,1,1])console.log(Array.from(permUnique([0,0,1,1])).join('\n'));从这里翻译成 JavaScript：https : //stackoverflow.com/a/6285203/10362619现在我的目的是将这些生成的排列用作其他对象的索引。然后在代码中使用这些对象，其中这些对象的顺序无关紧要：10 1001 01例如，最终是相同的，或者01 20 1202 10 2110 21 0212 01 20...对于用碱0，1并2从起动00 11 22。它们被认为是相同的，因为相同的数字处于相同的位置。只需切换两个数字（例如 0 和 1），您就会得到另一个。同样，为了更好的可读性，所有这些示例都被分成两组。00 11 22表示与 相同001122，其中每个数字都是输入数组中的一个元素。是在创建排列之后过滤元素的最快方法还是可以在函数中实现这个标准？编辑：不要求它是一个置换数组的生成器函数编辑 2：为了让事情更清楚：我给出的第一个例子有一个模式abab，其中a可以是0或，1并且b是相反的。第二个示例遵循模式abcabcwhere a, bandc都可以是0, 1or 2（但不一样）。

Answer 1

在不同排列之间有一个相等标准之后，我们需要为每个模式（相等类）建立一个规范形式。然后我们将尝试只生成那些。

在您的情况下，在1s、2s 和3s 的顺序无关紧要的情况下，我们可以决定它们各自的第一次出现必须在 order 中123，并且2不能在没有1和3不没有的情况下出现2。因此，无论模式是aabcbc, aacbcb, bbacac, ..., 还是ccbaba，我们想要生成的唯一形式是112323。或图案时，aaa/ bbb/ccc我们只生成111而不是222或333。

然后我们可以编写一个算法，它遵循这些规范形式的规则：

function patterns(values, len) {

    function* recurse(list, used, depth) {

        if (depth == len) {

            yield list.slice();

        } else {

            for (let j=0; j<used; j++) { // only put already used values at this position

                list[depth] = values[j];

                yield* recurse(list, used, depth+1);

            }

            if (used < values.length) { // or the single next unused value

                list[depth] = values[used];

                yield* recurse(list, used+1, depth+1); // which is counted as used here

            }

        }

    }

    return recurse([], 0, 0);

}

这只是从 distinct 生成特定长度的所有组合values，但您可以在算法中使用相同的方法，从一定数量的非唯一值生成排列。不过它确实变得有点复杂：121如果我们只有122可用的值，则无法实现规范形式，但212仍应生成模式。我们需要调整我们的规则，以便排序要求仅在出现次数相同的元素之间。所以我们必须used为它们保留不同的计数。

function permutationPatterns(elements) {

    const len = elements.length;

    const unique = new Map(elements.map(el => [el, {value: el, occurrences: 0}]));

    let max = 0;

    for (const el of elements) {

        const o = unique.get(el);

        max = Math.max(max, ++o.occurrences);

    }

    const byOccurrences = Array.from({length: max+1}, () => ({elements: [], used: 0}));

    for (const o of unique.values()) {

        byOccurrences[o.occurrences].elements.push(o);

    }

    function* generate(list, depth) {

        if (depth == len) {

            yield list.slice();

        } else {

            for (const options of byOccurrences) {

                options.used++;

                for (const option of options.elements.slice(0, options.used)) {

                    if (option.occurrences == 0) continue;

                    option.occurrences--;

                    list[depth] = option.value;

                    yield* generate(list, depth+1);

                    option.occurrences++;

                }

                options.used--;

            }

        }

    }

    return generate([], 0);

}

Answer 2

如果12和21相同，就像10和01毕竟相同，那么首先不要创建所有这些。这里的关键思想是为每个值都有一个规范的形式，例如可以是数字按升序排序。所以你只有值00, 01, 02, 11,12和22。

如果序列中的顺序也不重要，那么您不应该生成排列。同样，为序列选择规范形式。

然后，您可以轻松地仅生成升序形式，并为您的部分和整个序列使用相同的生成器一次：

function* generate(values, len) {

    if (len == 0)

        yield [];

    else

        for (const [i, val] of values.entries())

            for (const rest of generate(values.slice(i), len-1))

                yield [val, ...rest];

}

const duos = Array.from(generate([0, 1, 2], 2), x => x.join(""));

for (const x of generate(duos, 3))

    console.log(x.join(" "))