Set the length of a permutation

Question

How to set the length of a generated permutation?

for example:

permutator(['as', 'dd', 'ff'], 2);

This is what I got so far:

function permutator(inputArr, lngth){
  let results = [];
  
  function permute(arr, mem){
    let cur, memo = mem || [];
 
    for (let i = 0; i < arr.length; i++) {
      cur = arr.splice(i, 1);   
   
      if (arr.length === 0) {
        results.push(memo.concat(cur).join(''));
  
      }
      permute(arr.slice(), memo.concat(cur));
      arr.splice(i, 0, cur[0]);
   
    }
    return results;
  }
  return permute(inputArr);
}

console.log(permutator(['as','dd','ff'], 2));

This returns by 3 but not in 2 permutations:

["as,dd,ff", "as,ff,dd", "dd,as,ff", "dd,ff,as", "ff,as,dd", "ff,dd,as"]

i want it to return something like this:

["as,dd", "as,ff", "dd,as", "dd,ff", "ff,as", "ff,dd", ...................... ]

Your recursion uses the `arr.length` as the structure to recurse on. Just use the `length` instead - after ensuring it is `<= arr.length`. (Btw, you should do your base case outside of the loop) — Bergi, Apr 23 '20 at 20:22

score 1 · Accepted Answer · answered Apr 23 '20 at 20:32

You could check the length of mem instead of arr.length.

if (memo.length + 1 === lngth) {

function permutator(inputArr, lngth) {
  function permute(arr, mem) {
    
    let cur, memo = mem || [];

    for (let i = 0; i < arr.length; i++) {
      cur = arr.splice(i, 1);

      if (memo.length + 1 === lngth) {
        results.push(memo.concat(cur).join(''));
      }
      permute(arr.slice(), memo.concat(cur));
      arr.splice(i, 0, cur[0]);
    }
    return results;
  }


  let results = [];
  return permute(inputArr);
}

console.log(permutator(['as', 'dd', 'ff'], 2));

score 1 · Answer 2 · answered Apr 23 '20 at 21:12

Another approach is to write a more generic permutation-generator, and move the string concatenation to a wrapper function. With a simple modification to a permutation function from another answer, we can create shorter-length permutations, and then write a simple wrapper that converts ['dd', 'as'] to 'ddas'.

Here is a version that does that:

const without = (n) => (xs) => 
  [... xs .slice (0, n), ... xs .slice (n + 1)]

const permutations = (xs, n = xs .length) =>
  xs .length == 0 || n == 0
    ? []
  : xs .length == 1 || n == 1
    ? xs .map (x => [x])
  : // else
    xs .flatMap (
      (x, i) => permutations (without (i) (xs), n - 1) .map (p => [x, ...p])
    )

const permutator = (xs, n) => 
  permutations (xs, n) .map (ss => ss .join (''))


console .log (
  permutator (['as', 'dd', 'ff'], 2)
)

thanks for the recommendation Scott! 2 months later boom! I started using ur code instead.. — Rakushoe, May 16 '20 at 17:59
I've never tested the performance. At a guess, it's slower than, for instance, the answer from Nina. But my suggestion is always to write the simplest code that will work (while not being absolutely stupid about performance!) and then, if the code **test** too slow, find the hotspots and optimize them until you achieve your desired performance. Often we find there are no performance problems and we can keep our clean code. — Scott Sauyet, May 16 '20 at 23:52

Set the length of a permutation

2 Answers2