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.

Instead of operating on an array of characters, operate on an array of groups of characters. Take [any of these solutions](https://stackoverflow.com/a/30551462/1048572), 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. — Bergi, Jul 21 '22 at 21:44
So given `[ ["A",2], ["A",1], ["A",1]]` you would expect `[ ["A", "A", "A"], ["A", "A", "A"], ["A", "A", "A"]]` as output? — pilchard, Jul 21 '22 at 21:44
@pilchard I have updated the question to clarify that the string should be unique. But if that was not the case, then yes, your output would be desirable, as it is 3 inner arrays and not 6. — bjornte, Jul 21 '22 at 21:47
understood, so you're just permutating by the second index and avoiding duplicates. — pilchard, Jul 21 '22 at 21:48
@pilchard Yes. I have included your rephrasing in the question in an attempt to clarify. — bjornte, Jul 21 '22 at 21:49
[This question](https://stackoverflow.com/q/56672545/1048572) actually might be related (but it's not a duplicate, just good for the general approach) — Bergi, Jul 21 '22 at 21:52
@Etheryte , I am able to create the “usual” permutations. E.g. if the original array has 4 inner arrays, then I can create the 24 resulting permutations. And I guess I can deduplicate these after the fact. But obviously for performance reasons, it would be preferable to have a more elegant function that did not create the undesirable permutations in the first place. — bjornte, Jul 21 '22 at 21:58
There is still some ambiguity, surely your last example could be any of the permutations of `[1,1,1,1]` so `["B", "D", "A", "C"]` for example. But there is this: [Get all the possible unique permutations](https://stackoverflow.com/questions/40264376/get-all-the-possible-unique-permutations) with decent links in the answer to related questions/algorithms — pilchard, Jul 21 '22 at 22:00
@pilchard Again thank you for your disambiguation assistance! I have added that “movement” inside the array should be avoided. And thank you so much for that link, looking forward to reviewing that — bjornte, Jul 21 '22 at 22:11

Bergi · Accepted Answer · 2022-07-21T22:24:57.277

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

Verified that this indeed produces the intended result! I don't have enough expertise to understand the `flatMap` part, but I'll take it for granted that this function is a ton more efficient than anything I could have coded myself. I have to say, this is the best response I have ever had on Stack Exchange. Super grateful! — bjornte, Jul 22 '22 at 11:34
@bjornte Actually it's not very efficient with all the array copying, one could probably optimise this a lot. It only demonstrates the algorithmic approach. Try to understand what [`flatMap`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/flatMap) does and have a look at caub's original `permutations` implementation I linked. — Bergi, Jul 22 '22 at 11:59

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

1 Answers1