Unique permutations with repeating elements in JavaScript

Question

Suppose we have the elements 0 and 1, which can occour more than once, something like 00 00 11, 00 00 11 11 or 01 11 (split into groups of 2 for better readability).

I've already a function to generate all unique permutations:

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'));

Translated into JavaScript from here: https://stackoverflow.com/a/6285203/10362619

Now my intention is to use these generated permutations as indices for other objects. These are then used in code, where the order of these objects doesn't matter:

10 10
01 01

are the same in the end for example, or

01 20 12
02 10 21
10 21 02
12 01 20
...

for a base with 0, 1 and 2 starting from 00 11 22.

They are considered the same, because equal numbers are in the same position. Just switch two numbers (e.g. 0 with 1) and you'll get the other.

Again, all these examples are just split into groups of two for better readability. 00 11 22 means the same as 001122, where each digit is a single element in the input array.

Is the fastest way to filter the elements afterwards after the permutations have been created or can this criteria be implemented in the function?

Edit: It is no requirement that it is a generator function that permutes the array

Edit 2: To make things even more clear: The first example I gave has the pattern abab where a can be either 0 or 1 and b is the opposite. The second example follows the pattern abcabc where a, b and c can all be either 0, 1 or 2 (but not the same).

Answer 1

After having an equality criteria between the different permutations, we need to establish a canonical form for each pattern (equality class). We will then try to only generate those.

In your case, where order of 1s, 2s and 3s does not matter, we could decide that their respective first occurrences must be in the order 123, and 2 cannot appear without 1 and 3 not without 2. So whether the pattern is aabcbc, aacbcb, bbacac, …, or ccbaba, the only form that we want to generate is 112323. Or when the pattern is aaa/bbb/ccc we only generate 111 but not 222 or 333.

We can then write an algorithm which follows these rules for canonical forms:

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);
}

This simply generates all combinations of a certain length from the distinct values, but you can use the same approach in your algorithm that generates permutations from a certain amount of non-unique values. It does get a bit more complicated though: the canonical form 121 cannot be achieved if we only have the values 122 available, but the pattern 212 still should be generated. We need to adjust our rule so that the ordering requirement is only amongst elements of the same number of occurrences. So we have to keep different used counts for them.

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

If 12 and 21 are the same, like 10 and 01 are the same after all, then don't create all of them in the first place. The key idea here is to have a canonical form for each of the values, which could e.g. be that the digits are sorted ascending. So you'd only have the values 00, 01, 02, 11, 12 and 22.

If the order in the sequence doesn't matter either, then you shouldn't be generating permutations. Again, choose a canonical form for the sequences.

You can then easily generate only ascending forms, and use the same generator once for your parts and once for the whole sequence:

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(" "))

Answer 3

I've now wrapped the generator function inside a filter generator function as @PatrickRoberts suggested in the comments of the question.

class UniqueElement {
 constructor(value, occurrences) {
  this.value = value;
  this.occurrences = occurrences;
 }
}

function uniquePermutations(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 uniquePermutationsHelper(listunique, "0".repeat(u).split("").map((i) => parseInt(i)), u - 1);
}
function* uniquePermutationsHelper(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 uniquePermutationsHelper(listunique, result_list, d - 1)) yield g;
    i.occurrences++;
   }
  }
 }
}
function* uniquePermutationPatterns(elements) {
 let patterns = [];
 for (const perm of uniquePermutations(elements)) {
  // contains all unique elements in the order they appear. call patternVars.indexOf(element) and use its index for the patterns array
  let patternVars = Array.from(new Set(perm));

  let pattern = perm.map((p) => patternVars.indexOf(p));
    // convert the pattern to a number to avoid comparing array references and use the faster number comparison than the slower string comparison
  pattern = parseInt(pattern.join(""), patternVars.length);
  if (!patterns.length || !patterns.includes(pattern)) {
   patterns.push(pattern);
   yield perm;
  }
 }
}

let elements = [0,0,1,1];
let all = [...uniquePermutations(elements)];
let filtered = [...uniquePermutationPatterns(elements)];

console.log(`all permutations: (${all.length})`);
console.log(all.map((i) => i.join("")).join("\n"));
console.log(`\nfiltered permutations: (${filtered.length})`);
console.log(filtered.map((i) => i.join("")).join("\n"));

But that is about 3.2 times slower than simply generating all permutations. Which doesn't matter in my case. I only tested the performance for the array of elements [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2] and that only a few times (less than 10)