假设我们有元素0和1，它可以occour不止一次，像00 00 11，00 00 11 11或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 10
01 01
到底是一样的，还是
01 20 12
02 10 21
10 21 02
12 01 20
...
对于用碱0，1并2从起动00 11 22。
它们被认为是相同的，因为相同的数字位于相同的位置。只需切换两个数字（例如0与1），您就会得到另一个。
同样，所有这些示例都被分成两组，以提高可读性。00 11 22含义与相同001122，其中每个数字都是输入数组中的单个元素。
创建排列后，是随后过滤元素的最快方法，还是可以在函数中实现此条件？
编辑：不需要它是置换数组的生成器函数
编辑2：为了更清楚让事情：我给第一个例子有模式abab，其中a可以是0或1且b是相反的。第二个例子遵循模式abcabc，其中a，b和c可以全部或者0，1或2（但不相同）。
在不同排列之间具有相等条件后，我们需要为每个模式（相等类）建立规范形式。然后，我们将尝试仅生成那些。
在你的情况，其中顺序1S，2S和3s没有问题，我们可以决定它们各自的第一出现一定的顺序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);
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句