Имея критерии равенства между различными перестановками, нам нужно установить каноническую форму для каждого шаблона (класс равенства).Затем мы попытаемся только сгенерировать их.
В вашем случае, когда порядок 1 s, 2 s и 3 s не имеет значения, мы могли бы решить, что их соответствующие первые появления должны бытьв порядке 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);
}
Это просто генерирует все комбинации определенной длины из отличных 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);
}