以编程方式生成嵌套的 for 循环

Question

下划线 mixin 和下面的函数以两种不同的方式做完全相同的事情，它们获取数组的所有对。我想知道如何创建一个函数（闭包？），它允许我传入多少 "pairs" 或我想要的数组项分组，而不是每次都嵌套 for loops 或 range-maps。

getPairs: function(arr){
  return _.chain(_.range(arr.length))
  .map(function(setOne){
    return _.chain(_.range(arr.length))
    .map(function(setTwo){
      return [
        arr[setOne],
        arr[setTwo],
      ]
    })
    .value()
  })
  .value()
}

function getPairs(arr){
  var pairs = []
  for(var i = 0; i < arr.length; i++){
    for(var p = 0; p < arr.length; p++){
      var pair = [
        arr[i],
        arr[p],
      ]
      pairs.push()
    }
  }
  return pairs
}

Answer 1

因为这个问题更多的是关于算法的实现我用Swift来实现它：

// provide 2 parameters, an array and the size of one group of elements
// [[T]] means an array of an array of type T (placeholder for anything)
func getPair<T>(array: [T], pairCount: Int) -> [[T]] {
    if pairCount <= 1 {
        // puts each element of array in a separate array:
        // [3, 6, 7] -> [[3], [6], [7]]
        return array.map{ [[=10=]] }
    }
    // returns a flattened array of all possible element combinations
    // flatMap: array gets mapped to all other possible combinations of one less than pairCount and gets flattened/concatenated
    // el1: element of the array which can be used in the closure
    return array.flatMap{ el1 in
        // smaller pairs are mapped to bigger ones
        // el2: element of the smaller pairs (one small pair) which can be used in the closure
        return getPair(array, pairCount - 1).map{ el2 in
            return [el1] + el2
        }
    }
}

如您所见，此递归函数在代码行方面非常高效，但与下面更像 C 的版本相比，它慢了 2-22（平均：4-6）倍，尤其是对于大 pairCounts .

这是另一个版本：

// helper function which "creates" for loops and passes the indexes to a closure which takes an array of indexes
// indexes = [2, 3, 4] ==> for 4 times { for 3 times { for 2 times {} } }
// the corresponding passed indexes range from [0, 0, 0] to [2 - 1, 3 - 1, 4 - 1] so you can pass array.count directly
// therefore the index of the inner for loop can be accessed with passedArray[0] and so on
func forIndexes(indexes: [Int], closure: [Int] -> ()) {
    if indexes.count == 0 { return }

    // array which gets passed to the closure and modified over time
    var currentIndexes = Array(count: indexes.count, repeatedValue: 0)

    // maximum overall count of inner for loop: [2, 4, 5] => 2*4*5 = 40
    var count = 1
    for var i = 0; i < indexes.count; i++ {
        count *= indexes[i]
    }

    for var i = 0; i < count; i++ {
        // call closure with currentIndexes
        closure(currentIndexes)

        // increment first current index and check whether the other ones have to be updated
        if ++currentIndexes[0] == indexes[0] {
            // condition: j < indexes.count - 1 => prevent out of bounds exception for: currentIndexes[j+1]++
            for var j = 0; j < indexes.count - 1; j++ {
                if currentIndexes[j] >= indexes[j] {
                    currentIndexes[j] -= indexes[j]
                    currentIndexes[j+1]++
                }
            }
        }
    }
}

func getPair2<T>(array: [T], pairCount: Int) -> [[T]] {
    var result = [[T]]()
    // pair count determines the depth of the nested for loops while array.count specifies the loop count
    forIndexes(Array(count: pairCount, repeatedValue: array.count), closure: { indexes in
        // map array elements from all possible indexes
        result.append(indexes.map{ index in
            return array[index]
        })
    })
    return result
}

Answer 2

有趣的问题。为了获得一个简单的解决方案，我不得不跳出框框进行思考。实际上，整个事情可以通过两个 for 循环和一些繁重的数学运算来完成。这是代码：

function getGroupings(arr, numPerGroup){
    numPerGroup > 1 || (numPerGroup = 2);
    var groups = Math.pow(arr.length, numPerGroup);
    var groupings = [];
    for (var i = 0; i < numPerGroup; i++) {
        for (var j = 0; j < groups; j++) {
            groupings[j] || groupings.push(Array(numPerGroup));
            var index = Math.floor(j / Math.pow(arr.length, i)) % arr.length;
            groupings[j][i] = arr[index];
            if (i === numPerGroup - 1) groupings[j] = groupings[j].reverse();
        }
    }
    return groupings;
}

关于其工作原理的几点说明：

它为内部数组中的每个项目运行一次外部 `for` 循环，为外部数组中的每个项目运行一次内部 `for` 循环。向后，你可能会说。
内部 `for` 循环的工作方式有点像二进制时钟，其中 (value-of-clock) ===（我们要访问的传入数组的索引）。
其中n =（传入数组的长度），每到一个地方就会加1，一个（n[=第 55=] ^ 1) 个经常出现在 (n ^ 1) 的地方，第 (n ^ 2) 个经常出现在(n ^ 2) 的位置，依此类推直到 (n ^ num-per-group) 的位置。

在最后一次迭代中，它反转所有内部数组，实际上将 one 的位置放在最后，(n ^ 1) 的位置倒数第二，等等...不一定是必需的，但会产生更符合预期的输出。

示例：

假设您有一个数组 var arr = [3, 6, 9]，并且您想要获得 3--getGroupings(arr, 3); 的所有可能分组。实际的组数是arr.length ^ 3 = 27，所以函数会生成一个有27个数组的数组。

（忽略外部 for 循环——想象它的所有迭代同时发生）二进制时钟从 0 开始，所以第一个分组是 arr[0], arr[0], arr[0]--[3, 3, 3]。

下一次迭代，1的位前进一位--arr[0], arr[0], arr[1]--[3, 3, 6]，然后[3, 3, 9].

接下来是3位进位和1位归位的时间--arr[0], arr[1], arr[0]，所以4组是[3, 6, 3]。以此类推，直到第27个数组，[9, 9, 9].

这是一个 JSFiddle。试试吧！

以编程方式生成嵌套的 for 循环

Programmatically generate nested for loops

javascript

arrays

closures

for-loop