Javascript – Get all unique permutations of a string (special case)

May 4, 2022

Given a string like "this is a search with spaces", I want to return all permutations of that string where the spaces are replaced with a dash. For example, this is the result that I want:

["this-is-a-search-with-spaces"]
["this-is-a-search-with", "spaces"]
["this", "is-a-search-with-spaces"]
["this-is", "a-search-with-spaces"]
["this-is-a-search", "with-spaces"]
["this-is-a", "search-with-spaces"]
…and so on.

I can do half of this, but the problem is that it matches ["query1-query2", "query3"] but not the opposite way around like ["query1", "query2-query3"].

This is my current code:

const sliced = query.split(/ +/g)
let permutations = []
for (let i = 1; i <= sliced.length; i++) {
  let permuteArr = []
  for (let j = 0; j < sliced.length; j+=i) {
    permuteArr.push(sliced.slice(j, j+i).join("-"))
  }
  permutations.push(permuteArr)
}

Thanks for helping me.

>Solution :

Here is a recursive generator that yields the combinations:

function permutations(query) {
    
    function* iterRecur(sliced) {
        if (sliced.length == 1) return yield sliced;
        for (const result of iterRecur(sliced.slice(1))) {
            yield [sliced[0] + "-" + result[0], ...result.slice(1)];
            yield [sliced[0], ...result];
        }
    }

    const sliced = query.split(/ +/g);
    return [...iterRecur(sliced)];
}

console.log(permutations("this is a test"));