生成数组中字符的排列 - JavaScript

Question

我正在开发一个 JavaScript 函数，它将生成嵌套数组的排列（我们称之为输入）。我想以某种方式做到这一点，排列的长度将是 input.length。所以，给定

var input = [["0", "5", "9"], ["2", "3"], ["0", "5", "4"]];

我希望生成长度为 3 的排列，包含 ["0"、"5"、"9"] 中的任何一个作为第一个字符，["2"、"3"] 中的任何一个作为第一个字符第二个字符等

我的主要挑战是我对递归的理解不够好，无法将其应用于手头的问题。我理解一般原理并且可以逐步执行给定的函数以了解它的行为方式（显然，函数越复杂，我理解它所花费的时间就越长。当我无法全神贯注于一个函数时，我使用便利贴并在我的墙上使用单独的便条映射每个呼叫。这样我可以更容易地想象模式并且通常在逐步完成几个呼叫后我的理解会变得更好）。但是，如果我要编写我能够以这种方式理解的相同函数，我可能会遇到困难。

所以我找到了一个函数，它生成一个简单字符串的排列，目的是通过某种方式修改它，以便它处理嵌套数组并生成所需的输出。

var permutations = [];
function doPerm(str, arr) {
    if (typeof (str) == 'string') str = str.split('');
    if (str.length == 0) permutations.push(arr.join(''));
    for (var i = 0; i < str.length; i++) {
        var x = str.splice(i, 1);
        arr.push(x);
        doPerm(str, arr);
        arr.pop();
        str.splice(i, 0, x);
    }
}

修改会在现有函数之上添加另一个级别（根据我的想象 "rest" 变量本身必须是一个排列）。

不过，我确信有一种方法可以简化问题。对此的任何指导或可能的解决方案将不胜感激。

Answer 1

这是JavaScript中的递归解。我尝试将您的话与函数中的适当步骤相匹配，请参阅评论。

function f(input, index, result) {

      // "...the length of permutations will be of input.length"

      if (index == input.length) {
        $("#output").append(JSON.stringify(result) + "<br>"); // output
        return; // terminate this particular thread
      }

      // "containing any of ["0", "5", "9"] as a first character"

      for (var i = 0; i < input[index].length; i++) {

        var copyOfResult = result.slice();
        copyOfResult.push(input[index][i]);

        // "any of ["2", "3"] as the second character etc."

        f(input, index + 1, copyOfResult);

      }
    }

     // start the recursion;

    f([["0", "5", "9"],["2", "3"],["0", "5", "4"]], 0, []);

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div id="output"></div>

Answer 2

让我们试试天真的方法，

foreach input1 in input[1]
    foreach input2 in input[2]
        foreach input3 in input[3]
            print input1*100 + input2*10 + input3*1

应该很容易实现和替换上面的代码段来得到你想要的:)

生成数组中字符的排列 - JavaScript

Generate permutations of characters in arrays - JavaScript

javascript

algorithm

recursion

permutation