javascript - 二项式子数组

Question

我有一个长度为 n 的 A 数组。我想采取所有可能的 k (0

例如，如果我有 A 的长度是五:

[1,2,3,4,5]

如果 k = 3，算法必须给我 B 数组。

[1,2,3    ]
[1,2,  4  ]
[1,2,    5]
[1,  3,4  ]
[1,  3,  5]
[1,    4,5]
[  2,3,4  ]
[  2,3,  5]
[  2,  4,5]
[    3,4,5]

B 的长度等于 n!/k!(n-k)!('!' 表示阶乘，牛顿法)

我使用的是 javascript，所以在我的标签中包含了它，但这只是算法，不需要用 javascript 编写。

Answer 1

您可以通过过滤方法来做到这一点。

在您的示例中，您希望接收数组的所有排列，并获取该数组的特定数量的元素。

您可以轻松地以迭代方式做到这一点。首先对数组的 n - 1 元素进行所有排列:

// return all (n - 1) element permutations of an array
var permutations = function(arr) {
  return arr.reduce(function(re, value, i) {
    // add an array for each element in the original array
    return re.concat([arr.filter(function(v, index) {
      // drop each element with the same index
      return index !== i 
    })])
  }, [])
}

现在 permutations([1,2,3]) 将返回 [[1,2], [1,3], [2,3]]这始终是一个不相交的集合，假设您在源数组中只有唯一值。

要接收 5 元素数组的所有 3 元素数组，您首先要计算 4 元素数组的列表，并将它们中的每一个转换为 3 元素数组。

permutations([1,2,3,4]).map(permutations)
=> [[1,2,3] => [[[1,2], [1,3], [2,3]]
   ,[1,2,4]    ,[[1,2], [1,4], [2,4]]
   ,[1,3,4]    ,[[1,3], [1,4], [3,4]]
   ,[2,3,4]    ,[[2,3], [2,4], [3,4]]
   ]           ]

显然这里的问题是有 double 。这可以通过删除所有非唯一值来解决。

var unique = function(arr) {
  var s = arr.map(function(v) { return "" + v })
  return arr.filter(function(v, i) { return s.indexOf("" + v) == i })
}

将它们全部打包到一个函数中可以像这样完成:

var permutationsWithLength = function(arr, length) {
  var re = [arr]
  for (var i = arr.length; i >= length; i--) {
    re = re.reduce(function(tmp, perms) {
      return unique(temp.concat(permutations(perms)))
    }, [])
  }
  return re
}

我承认这可能不是最快的方法，尤其是关于 unique 函数，但它是一种非常通用的方法，即使使用更大的数组也能解决您描述的问题。

希望对你有帮助;)