Solving a Permutations problem with Heap's Algorithm in Javascript

Question

I'm working through some "Kata's" on CodeWars.com, and am stuck on the Permutations problem.

Here is the problem: n this kata you have to create all permutations of an input string and remove duplicates, if present. This means, you have to shuffle all letters from the input in all possible orders.

Examples:
permutations('a'); // ['a']
permutations('ab'); // ['ab', 'ba']
permutations('aabb'); // ['aabb', 'abab', 'abba', 'baab', 'baba', 'bbaa']
The order of the permutations doesn't matter.

Here is my solution:

function permutations(string) {


const swap = (string, x, y) => {
    const stringArray = string.split('')
    const swapVar = stringArray[x]
    stringArray[x] = stringArray[y]
    stringArray[y] = swapVar
    return stringArray.join('')
  }

  const permutate = (k, arr) => {
    if (k === 1) {
      return arr
    } else {
      for (let i = 0; i < k - 1; i++) {
        if (k % 2 === 0) {
          arr.push(swap(string, i, k-1))
        } else {
          arr.push(swap(string, 0, k-1))
        }
      }
      permutate(k - 1, arr)
    }
  }
  
  return permutate(string.length, [string])
}

When you pass in a single letter, it works fine. Two letters and it returns undefined. I've console logged the if statement block with the return and it should be returning the correct answer, but the result is still undefined. Considering it's getting the correct answer in the if statement and isn't progressing into the else block, I'm at a loss for why this isn't working.

Thank you in advance!

JTP709 · Accepted Answer · 2020-07-01 16:19:10Z

1

I figured it out - I was missing the return statement before the recursive function call.

answered Jul 1, 2020 at 16:19

JTP709

1302 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Lyes · Accepted Answer · 2020-07-01 15:17:29Z

0

Here is a basic solution

 String.prototype.replaceAt = function(index, replacement) {
 return this.substr(0, index) + replacement + this.substr(index + 
 replacement.length);}


var words = [];
var string = "lyes";


for(var i = 0;i< string.length;i++){

for(var j = 0;j<string.length;j++){
    
    var tempChar;
    
    if(i!==j){
        
        tempChar = string[j]
        var str = string.replaceAt(j,string[i])
        str = str.replaceAt(i,tempChar)
        if(!words.includes(str)){
            words.push(str)
            console.log(str)
        }
        
      } 
   }
 }

 console.log(words.length +" words found")

answered Jul 1, 2020 at 15:17

Lyes

4775 silver badges21 bronze badges

1 Comment

Scott Sauyet Over a year ago

This does not find all permutations. For your example of 'lyes', you only end up with six results, but there are 24 actual permutations of four distinct items.

Collectives™ on Stack Overflow

Solving a Permutations problem with Heap's Algorithm in Javascript

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related