-1

How to combine array of strings in all possible ways

Example 1

input

const words = ["foo", "bar"]

Output

["foobar", "barfoo"]

Example 2

input

const words = ["word","good","best"];

Output

[
  "wordgoodbest",
  "wordbestgood",
  "bestwordgood",
  "bestgoodword",
  "goodbestword",
  "goodwordbest"
]

And so on if input size increased

Abdelrhman Mohamed
  • 167
  • 11
  • See here for solutions in several languages: https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/ – Carsten Massmann Jul 31 '22 at 15:50
  • maybe https://stackoverflow.com/questions/18681165/shuffle-an-array-as-many-as-possible will help – cmgchess Jul 31 '22 at 15:53

3 Answers3

2

function combineWords(words) {
  const result = [];

  if (words.length === 1) {
    return words;
  }

  for (let i = 0; i < words.length; ++i) {
    const word = words[i];

    const rest = words.slice(0, i).concat(words.slice(i + 1));

    const combinations = combineWords(rest);

    for (let j = 0; j < combinations.length; ++j) {
      result.push(word + combinations[j]);
    }
  }

  return result;
}

// Example by OP in original question
console.log(combineWords(["word","good","best"]))
// Example by OP in comments
console.log(combineWords(["word", "good", "best", "hi"]))
// permutations are length of input factorial
console.log(combineWords(["word","good","best", "another", "more"]).length)

The function first checks if the array only contains one word. If so, it simply returns the array.

Otherwise, it loops through all the words in the array. For each word, it creates a new array that contains all the other words in the original array, excluding the current word. It then calls the function recursively on this new array, which will return an array of all possible combinations of the words in this new array.

Finally, it loops through all the combinations returned by the recursive call and appends the current word to each one, before adding it to the final array of results.

Felix G
  • 724
  • 5
  • 17
  • OP asked for an algorithm that worked with N number of inputs. – WillD Jul 31 '22 at 15:46
  • This not works as expected if i increase the input to 4 strings it return 3 string combined only it should be 4 (arr.length) for example ``["word", "good", "best", "hi"]`` it should be "wordgoodbesthi" and so on – Abdelrhman Mohamed Jul 31 '22 at 15:50
  • 1
    @AbdelrhmanMohamed I've updated the code to work with any amount of words. – Felix G Jul 31 '22 at 15:53
0

I don't know how efficient it would be but might get you what you need.

  1. Remove duplicate entries from input array
  2. outer loop n times (total no of elements in input array)
  3. inner loop n-1 times (all elements except current outer loop)
Gaurav Kumar
  • 26
  • 1
0

Here's an alternative solution.

This creates a set of nested loops (one for each word in the set) using a recursive function. If within the innermost loop the indexes of all the loops comprise a unique set (no repeated numbers. i.e. 1,2,3,4 or 2,1,4,3.) Then pull each of the words in that order and add them to the results array.

function getCombinations(words){
  const results = [];
  const indexes = [];
  const wordCount = words.length;

  function looper(loopNumber){  
    for(indexes[loopNumber] = 0; indexes[loopNumber] < wordCount; indexes[loopNumber]++){
       if(loopNumber < wordCount - 1){
        looper(loopNumber + 1);
       }
       else {
         if(indexes.length === new Set(indexes).size){
            results.push(indexes.map(index => words[index]).join(''))
         }
      }
    }
  }
  looper(0);

    return results;
}

console.log(getCombinations(['a','b']));
console.log(getCombinations(['a','b','c']));
console.log(getCombinations(['a','b','c','d']));
console.log(getCombinations(["word","good","best"]));
WillD
  • 5,170
  • 6
  • 27
  • 56