CODEWITHSUNDEEP
javascriptalgorithmrecursionpermutationheaps-algorithm
JTP709
JTP709

Reputation: 130

Solving a Permutations problem with Heap's Algorithm in Javascript

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!

Upvotes: 1

Views: 1648

Answers (2)

JTP709
JTP709

Reputation: 130

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

Upvotes: 1

Lyes
Lyes

Reputation: 477

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")

Upvotes: 0

Related Questions