How to create permutations of tuple-like list where identical integer pairs are not permuted

Question

I have this array of arrays, where the inner arrays are uniformly structured (“tuple-like”) with a unique ID (a string) and a non-unique integer:

[
    ["A",2], 
    ["B",1], 
    ["C",1]
]

I need the JavaScript function to create the list of permutations below, that does not permute tuples with the same integer value:

[
    ["A", "B", "C"],
    ["B", "A", "C"],
    ["B", "C", "A"]
]

Quoting user pilchard in the comments below, I'm trying to permute “by the second index and avoid duplicates”.

The list should therefore not include these permutations:

[
    ["A", "C", "B"], // integers same as in ["A", "B", "C"]
    ["C", "A", "B"], // integers same as in ["B", "A", "C"]
    ["C", "B", "A"]  // integers same as in ["B", "C", "A"]
]

Also, it is preferable to avoid “movement” inside the array. Therefore, ["A", "B", "C"] is a better permutation than ["A", "C", "B"]

In the simplest scenario, the input could be this:

[
    ["A",1], 
    ["B",1], 
    ["C",1], 
    ["D",1]
]

The result should simply be 1 permutation, as opposed to the 24 that is the result when also permuting identical integers:

[
    ["A", "B", "C", "D"]
]

Again, “movement” inside the array should be avoided, so ["A", "B", "C", "D"] is the preferred alternative.

Answer 1

Instead of operating on an array of characters, operate on an array of groups of characters. You can take any of these solutions, and instead of removing the chosen character from the input to put it into the output, remove the first character of the chosen group and remove the group only when it's empty.

function groupPermutations(groups) {
  if (!groups.length) return [[]];
  return groups.flatMap((group, i) => {
    // assert(group.length > 0)
    const [val, ...rest] = group;
    const remaining = rest.length
      ? [...groups.slice(0,i), rest, ...groups.slice(i+1)]
      : [...groups.slice(0,i), ...groups.slice(i+1)];
    return groupPermutations(remaining).map(p => [val, ...p]);
  });
}

console.log(groupPermutations(["A", "BC"]));
console.log(groupPermutations(["ABCD"]));

Now you only need a trivial conversion of your tuple input format to the grouping:

const pairs = [
  ["A",2], 
  ["B",1], 
  ["C",1],
];
const byInteger = new Map();
for (const [val, key] of pairs) {
  if (!byInteger.has(key)) byInteger.set(key, []);
  byInteger.get(key).push(val);
}
const groups = Array.from(byInteger.values());
console.log(groupPermutations(groups));