Search code examples
javascriptpythonmathbacktrackingrecursive-backtracking

Python - how to change the multiple assignment to the syntax of JavaScript and get the right permutations of the given string


I've got a little problem searching about backtracking. First of all, in the code I'll link below I found a quite strange syntax to me as a JavaScript programmer:

a[l], a[i] = a[i], a[l]

Using information in this page I figured it out it means: "assign a[i] to the a[l] variable and a[l] to the a[i] variable". I can't understand the use of this. I thought it would be the same values. If you first assign the value to a[l] and then try to get a[l], it's going to be a[i], for both variables.


It's a Python code, however, I'd like to convert it to the JavaScript using the same principle.

# Python program to print all permutations with
# duplicates allowed

def toString(List):
    return ''.join(List)

# Function to print permutations of string
# This function takes three parameters:
# 1. String
# 2. Starting index of the string
# 3. Ending index of the string.
def permute(a, l, r):
    if l==r:
        print toString(a)
    else:
        for i in xrange(l,r+1):
            a[l], a[i] = a[i], a[l]
            permute(a, l+1, r)
            a[l], a[i] = a[i], a[l] # backtrack

# Driver program to test the above function
string = "aab"
n = len(string)
a = list(string)
permute(a, 0, n-1)

# This code is contributed by Bhavya Jain

You can follow this link to the IDE: https://ide.geeksforgeeks.org/ASvO8MoGQr.

What this code does, is getting the permutation values of the string "aab".

For example, using "aab" as the first string, we should get the following result: aab aba aab aba baa baa.

I tried using "JavaScript" and came up with this:

let arr = [];

let permute = function(str, l, r) {
  if (l === r) {
    arr.push(str);
  } else {
    for (let i = l; i <= r; i++) {
      str[l] = str[i];
      str[i] = str[l];
      permute(str, l + 1, r);
      str[l] = str[i];
      str[i] = str[l];
    }
  }
};

permute('aab', 0, 'aab'.length - 1);

console.log(arr);

The result I get is ["aab", "aab", "aab", "aab", "aab", "aab"].

Link to the JSFiddle: https://jsfiddle.net/xrfkt9qj/1/.


EDIT1 I've tried the @jp_data_analysis answer, but it still returns bad results: https://jsfiddle.net/zurvm0xy/.

EDIT2 ES6 Version of the script: https://jsfiddle.net/zurvm0xy/4/.


It's not a duplicate, the variable swapping is only a first part of this problem. Please read the full article.


Solution

  • Finally, I figured everything out. The most immportant part was to convert the string to the array using split() function.

    let arr = [], y, x;
    
    let permute = function(str, l, r) {
      if (l === r) {
        arr.push(str.join(''));
      } else {
        for (let i = l; i <= r; i++) {
          [str[l], str[i]] = [str[i], str[l]];
          permute(str, l + 1, r);
          [str[l], str[i]] = [str[i], str[l]];
        }
      }
    };
    
    permute('aab'.split(''), 0, 'aab'.length - 1)
    console.log(arr);