4

我有一个长度为 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 编写。

4

2 回答 2

0

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

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

您可以轻松地以迭代方式做到这一点。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]]
   ]           ]

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

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函数方面，但它是一种非常通用的方法，即使使用更大的数组也可以解决您描述的问题。

希望能帮助到你 ;）

于 2013-04-05T11:58:48.097 回答
-1

下面是我的一个项目的复制粘贴。不知道它是否仍然有效；）

var choose = function choose_func(elems, len) {
  var result = [];
  for (var i=0; i<elems.length; i++) {
    if (len == 1) {
      result.push([elems[i]]);
    } else {
      var remainingItems = choose_func(elems.slice(i+1, elems.length), len - 1);
      for (var j=0; j<remainingItems.length; j++) 
        result.push([elems[i]].concat(remainingItems[j])); 
    }
  }
  return result;
};

var result = choose([1,2,3,4,5], 3)

/*result  = [[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]] */
于 2013-04-05T11:33:23.557 回答