Question 185540 in Javascript Question posted in
A very good W3school tutorial can be found here.

Permutations of string characters in n slots in Javascript

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

Tags:

2

Answers


  1. 0

    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)!.

    Login or Signup to reply.
  2. 0

    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)
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search