0

バックトラックについて検索するのに少し問題があります。まず第一に、以下にリンクするコードで、JavaScript プログラマーとしては非常に奇妙な構文を見つけました。

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

このページの情報を使用してa[i]、 「a[l]変数と変数に割り当てる」という意味であることがわかりました。これの使い方が理解できません。同じ価値観だと思っていました。最初に値を に代入して取得しようとすると、両方の変数で になります。a[l]a[i]a[l]a[l]a[i]

これは Python コードですが、同じ原理を使用して JavaScript に変換したいと考えています。

# 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

次のリンクから IDE にアクセスできます: https://ide.geeksforgeeks.org/ASvO8MoGQr。

このコードが行うことは、文字列「aab」の順列値を取得することです。

たとえば、最初の文字列として「aab」を使用すると、次の結果が得られます: aab aba aab aba baa baa .

「JavaScript」を使ってみたところ、次のようになりました。

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

私が得る結果はです["aab", "aab", "aab", "aab", "aab", "aab"]。

JSFiddle へのリンク: https://jsfiddle.net/xrfkt9qj/1/。

EDIT1 @jp_data_analysis の回答を試しましたが、まだ悪い結果が返されます: https://jsfiddle.net/zurvm0xy/。

スクリプトのEDIT2 ES6 バージョン: https://jsfiddle.net/zurvm0xy/4/。

重複ではありません。変数のスワッピングは、この問題の最初の部分にすぎません。記事全文をお読みください。

4

2 に答える 2

0

最後に、私はすべてを理解しました。最も重要な部分は、split()関数を使用して文字列を配列に変換することでした。

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);
于 2018-02-15T14:02:14.317 に答える