Shuffle a Given Array using Fisher-Yates Shuffle Algorithm, Interleave a String of Two Other Strings, Generate All Permutations of a Given String

Because naive shuffle can be biased, the Fisher-Yates shuffle is an algorithm for randomly shuffling a finite sequence.

To shuffle a given array of numbers randomly, in naive shuffle,

const shuffle = (arr) => {
     let shuffledArray = [];
     while (arr.length > 0) {
          let randomIndex = Math.random();
          randomIndex *= arr.length;
          randomIndex = Math.floor(randomIndex);
          shuffledArray.push(arr[randomIndex]);
          arr = [...arr.slice(0, randomIndex), ...arr.slice(randomIndex + 1)]
     };
     return shuffledArray;
};

we multiply the random index in (0, 1) by the length of the input array, round to the lower bound because indices start at 0, 1, …, remove the element at the random index, for which Array.prototype.slice does not mutate the original array, and return the shuffled array.¹

In the Fisher-Yates approach,

const shuffle = (input) => {
     const shuffledInput = [...input];
     for (let i = 0; i < input.length; i++) {
          const randomI = Math.floor(Math.random() * i);
          [shuffledInput[i], shuffledInput[randomI]] = [shuffledInput[randomI], shuffledInput[i]];
     };
     return shuffledInput;
};²

we destructure the input so we can change shuffledInput and not the original input, and swap values.³

Given a string, return an array of all permutations of that string.

const perms = (str) => {
     if (str.length === 1) {
          return [str];
     }
     if (str.length === 2) {
          return [ str, `${str[1]}${str[0]}` ];
     }
     const set = new Set();
     [...str].forEach((el, i) => {
          const newStr = [...str.slice()];
          const splicedStr = newStr.splice(i, 1);
          perms(newStr).forEach(el => {
               set.add(splicedStr.concat(el).join(""))
          });
     })
     return [...set];
}

Array.prototype.slice() is a shallow copy of str,⁴ while Array.prototype.splice(i, 1) is the character at the i index of newStr. For each element in each permutation, join it with the splicedStr letter.⁵

console.assert(JSON.stringify(perms("hello")) === JSON.stringify([
     "hello", "helol", "heoll", "hlelo", "hleol", 
     "hlleo", "hlloe", "hloel", "hlole", "hoell", 
     "holel", "holle", "ehllo", "ehlol", "eholl", 
     "elhlo", "elhol", "ellho", "elloh", "elohl", 
     "elolh", "eohll", "eolhl", "eollh", "lhelo", 
     "lheol", "lhleo", "lhloe", "lhoel", "lhole", 
     "lehlo", "lehol", "lelho", "leloh", "leohl", 
     "leolh", "llheo", "llhoe", "lleho", "lleoh", 
     "llohe", "lloeh", "lohel", "lohle", "loehl", 
     "loelh", "lolhe", "loleh", "ohell", "ohlel", 
     "ohlle", "oehll", "oelhl", "oellh", "olhel", 
     "olhle", "olehl", "olelh", "ollhe", "olleh"
]));⁶

Create the function interleave that accepts strings as arguments:

interleave(“FOO”, “bar”);

The task is to “interleave” the strings, such that the resulting string (return value) looks like:

interleave(“FOO”, “bar”);

RETURNS: “Fb0a0r”

Also, interleave can accept any number of strings:

interleave(“HHh”, “Aaa”, “!.?”);

RETURNS: “HA!Ha.ha?”

interleave(“987”, “you”, “ARE”, “the”, “246”);

RETURNS: “9yAt28oRh47uEe6”⁷

Approach 1: One by one (non-recursively).

We can whittle down each string by taking (without replacement) the first element and adding it to the result.⁸

const interleave = (...args) => {
     let res = '';
     let someArgNotEmpty = true;
     while (someArgNotEmpty) {
          for (let i = 0; i < args.length; i++) {
               if (args[i][0]) {
                    res += args[i][0]
               }
               args[i] = args[i].substring(1);
          }
          someArgNotEmpty = false;
          for (let element of args) {
               if (element.length > 0) {
                    someArgNotEmpty = true;
               }
          }
     }
     return res;
};

Remove the first character from each arg and then add it to string while some arg is not empty; if the string still has a first element, then shift the string until it is empty.

Approach 2: With recursion.

const interleave = (...strings) => {
     const ilStr = strings.map(str => str[0]).join("");
     const nextArr = strings.map(str => str.slice(1)).filter(str => str.length);
     return nextArr.length ? ilStr.concat(interleave(...nextArr)) : ilStr;
}

ilStr is the join of the first element across all strings (this doesn’t alter the strings array). Since we’re using .slice, which doesn’t modify the original string, we “have” to map it to its shifted version str[1:] and then filter out all strings which are found to be newly empty. If there’s anything left, then make a recursive call on the new shifted and filtered set of strings; once we get to the end return ilStr.

[1]: JavaScript array: Randomly arrange or shuffle an array — w3resource
https://www.w3resource.com/javascript-exercises/javascript-array-exercise-17.php

[2]: Let’s Get IT 자바스크립트 프로그래밍: 6장 해설 노트
https://thebook.io/080270/partxt/solution/06/

[3]: Shuffle An Array With Code Examples
https://www.folkstalk.com/2022/07/shuffle-an-array-with-code-examples.html

[4]: Array.prototype.slice() — JavaScript | MDN
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/slice

[5]: Array.prototype.splice() — JavaScript | MDN
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/splice

[6]: RosettaGit/permutations.md at master · ad-si/RosettaGit
https://github.com/ad-si/RosettaGit/blob/master/content/drafts/permutations.md

[7]: Solved sers\vedi AppData\Local\Packages\Microsoft Microsoft | Chegg.com
https://www.chegg.com/homework-help/questions-and-answers/zipjava-foldjava-mapjava-arrayoperationmainjava-interleavejava-pairjava-asks-code-comments-q43373047

[8]: We can whittle down each string by taking (without replacement) the first element and adding it to the result.