使用递归组合字母

Question

假设，如果我给'ABC' 作为输入，那么我想要'ABC', 'ACB', 'CAB', 'CBA', 'BAC', 'BCA'。每个单词都有n的组合！其中 n 是字母的长度。我认为递归可以使它更容易。这是我用 javascript 编写的代码：

function reArrange(word)
{
    console.log(word);
    if (word.length < 0) {
        return (-1);
    }
    else if (word.length == 0) {
        return ('');
    }
    else {
        for (var _i = 0; _i < word.length; _i++) {
            var temp = word[_i];
            for (var _j = 0; _j < word.length; _j++) {
                if (_i != _j) {
                    return word[_i] + reArrange(word.slice(_i, word.length));
                }
            }
        }
    }
}

请使用详细的注释。

Answer 1

function combinations(current_string, actual_string, seen) {
    var result = [];
    if (current_string.length === actual_string.length) {
        return [current_string];
    }
    actual_string.forEach(function(currentChar, index) {
        if (seen.indexOf(index) === -1) {
            result = [].concat.apply(result, combinations(current_string
                + currentChar, actual_string, seen.concat(index)));
        }
    });
    return result;
}

console.log(combinations("", "ABC".split(""), []));

输出

[ 'ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA' ]

注意：该程序的工作假设输入字符串中的字符将是唯一的。

有三个参数传递给这个函数。第一个是使用递归构建的当前字符串，第二个是来自实际字符串的字符数组，第三个是递归树中已经看到的索引列表。

第一个 if 条件是此递归解决方案的基本条件。如果生成的当前字符串的长度等于实际字符串的长度，我们就没有剩余的字符要处理，这是组合之一。所以，我们返回那个。

如果不满足该条件，对于实际字符串中的每个字符，我们检查它是否已被使用（我们将索引与 中的索引进行比较seen）。如果它已在当前递归中使用，则忽略它。否则，将它与当前字符串连接起来，并将其包含在看到的变量中并立即递归。

递归的结果将是一个字符串数组。我们需要展平它们（连接内部数组的所有元素）。所以，我们使用[].concat.apply.

最后，我们返回收集的结果，这是递归树的样子