Permutations of string characters in n slots in Javascript

Question

I have been searching around. Many people have asked similar questions, like "How to list all the permutations of a string". However, all these answers are just listing out the possible character arrangements in the string like permuter(givenArray) or permuter(givenString) which are actually not a permutation function but a factorial function n! = nx(n-1)x ... x1

What I am after is a list of all strings that can be fitted into a given set of slots. The permutation formula to it should be P(n, r) = n!/(n-r)! so it should be The_Real_Permuter(givenString_n , slotsCount_r).

This js function should be something very commonly seen. So before I go reinvent the wheel, I decide to ask the internet first, but I have had no luck so far. Am I searching for the wrong keywords? Can anyone point me to a javascript implementation that can list all permutations of a given string into a set of given slots?

Example

There are 16 cars. The factorial listing functions I found from other answers so far are show all possible different orders to arrange 16 cars. This is simply factorial(16) = 16!

What I really want to see is, say given 4 parking lots (1 car per lot), show all possible different orders to fit 16 cars into 4 parking lots.

That is, 1 parking lot can only fit 1 car. 16 cars can race for these 4 lots. So, each time only 4 cars can occupy these 4 lots. At this time, the other 12 cars would have no parking. That also means order matters, parking at the left lot is not the same as parking at the middle or the right lot. The formula for this is P(16, 4) = 16!/(16-4)!

`P(n, r) = n!/(n-r)!` looks more like the [combination](https://en.wikipedia.org/wiki/Combination) formula. (Disclaimer: I'm bad at math.) — InSync, Jun 13 '23 at 13:33
@InSync They are actually similar. `C(n, r) = n!/(n-r)!r!`, anyway, the calculation is easy enough. I would like to find the listing function of this formula. — Tom, Jun 13 '23 at 13:35
What you call "factorial function" is known mathematically as **permutation**. Your definition of "permutation" is known mathematically as **combination**. — slebetman, Jun 13 '23 at 13:36
@slebetman, `Factorial(n) = n!`, `Permutation(n, r) = n!/(n-r)!` , `Combination(n, r) = n!/(n-r)!r!` — Tom, Jun 13 '23 at 13:41
Do you actually want to generate all the strings of length r? — Matt Timmermans, Jun 13 '23 at 13:59
@MattTimmermans, It can be the generation of all the characters in string from 1 to r, or just r. E.g, `a,b,c,ab,ac,bc...` or just `abc,acb,bac...`, either way is cool. — Tom, Jun 13 '23 at 14:03
`fit 16 cars into 4 parking slots.` Do you mean like -> `16,0,0,0`, `15,1,0,0`, `14,1,1,0` etc. That would equal 969.. — Keith, Jun 13 '23 at 14:34
@Keith sorry my bad, it was confusing. I mean 1 parking lot can only fit 1 car. (updated) 16 cars can race for these 4 lots. So, each time only 4 cars can occupy these 4 lots. At this time, the other 12 cars would have no parking. That also means order matters, parking at the left lot is not the same as parking at the middle or the right lot. — Tom, Jun 13 '23 at 14:38
@Tom, oh, in that case the answer is `43680`, agsigma's answer looks good, basically use `'abcdefghijklmnop', 4` — Keith, Jun 13 '23 at 14:44
This question would be more interesting, and maybe not a duplicate, if you required support for duplicate characters without duplicate outputs, but I guess that's not the case, since your counting formula would no longer apply. — Matt Timmermans, Jun 13 '23 at 16:54

score 1 · Accepted Answer · answered Jun 13 '23 at 14:21

It's a little bit more complicated than it appears, because you have to keep track of used characters in case of multiple occurrences of the same character in the string (look at last test below). Anyway here is short snippet, is it what you were looking for?

const solution = function(s, slots_no) {
  const result = [];
  const chars_left = new Map()
  for (let c of s) {
    chars_left.set(c, (chars_left.get(c) || 0) + 1)
  }
  const f = (slots_left, partial="") => {
    if (slots_left === 0) {
      result.push(partial);
      return;
    }
    for (let c of s) {
      if (chars_left.get(c) > 0) {
        chars_left.set(c, (chars_left.get(c) || 0) - 1)
        f(slots_left-1, partial + c)
        chars_left.set(c, (chars_left.get(c) || 0) + 1)
      }
    }
  }
  f(slots_no)
  return [...new Set(result)];
}

console.log(solution('abcde', 2).length == 5*4)
console.log(solution('abcde', 1).length == 5)
console.log(solution('aaabbc', 1).length == 3)

Spot on about the case of multiple occurrences of the same chars! Because input could be something like `'aaabbbcccddd'`. Thanks for the nice demonstration of the use of new Map and new Set. — Tom, Jun 13 '23 at 23:20

Ali Ali · Answer 2 · 2023-06-13T14:54:22.927

I explain this question from your example. First, there are 16 cars and every car has own number such as 1,2,3,... and 16. And there are 4 parking slots and name A,B,C,D.

Let's think from A. You choose 4 cars from 16 for A. So the possible choice is the C(16,4). After that you must park 4 cars from 12(because 4 cars already parked in A slot) in slot B. So the possible choice is the C(12,4).

Like same method. For slot C, C(8,4). For slot D, C(4,4).

After all, the possible choice is C(16,4)*C(12,4)*C(8,4)*C(4,4).

If one slot allowed only one car, you can think in the same way.

For A slot=> C(16,1)
For B slot=> C(15,1)
For C slot=> C(14,1)
For D slot=> C(13,1)

After all, the possible choice is C(16,1)*C(15,1)*C(14,1)*C(13,4).

And this moment, you are right C(16,4)=16!/(16-4)!.

Permutations of string characters in n slots in Javascript

2 Answers2