将数组拆分为具有 uniq 元素的 s 个子集

Question

给定一个数组 [1， 2， 3， 4， 5] 和代表splits的数字 s 如何生成以下序列(希望我涵盖了 s=3 的所有组合(。

对数组进行

排序的数组和每个子集s必须至少包含 1 个元素。

s = 2
{1} {2, 3, 4, 5}
{1, 2} {3, 4, 5}
{1, 2, 3}, {4, 5}
{1, 2, 3, 4}, { 5 }
{1, 2, 3, 4, 5}
s = 3
{1}, {2}, {3, 4, 5}
{1}, {2, 3}, {4, 5}
{1}, {2, 3, 4}, {5}
{1, 2}, {3, 4}, {5}
{1, 2, 3}, {4}, {5}
{1, 2}, {3}, {4, 5}
{1, 2, 3}, {4}, {5}

我可以在s=2时解决这个问题，但不知道s>2时该怎么办。

Answer 1

我看到您描述为"m out of N 代码">或恒定权重代码的问题......

N 是单词的长度(在您的情况下为 5 -1 = 4(m 是权重或您要执行的拆分次数(在您的情况下为 - s(

字数 ： 1-+-2-+-

3-+-4-+-5拆分位置 ： 1 2 3 4

然后你可以说你的拆分是一个布尔数组(当你想做一个拆分时，拆分位置数组中的位是 true 或 1(

所以你有一个代码，你有四个(N-1(个可能的位，其中总是有两个(s(必须为真。 即 N=4 和 s=2。

[0011],
[0101],
[1001], etc.

正如这篇维基百科文章所说，没有分析方法来定义任何任意组合的可能性数量。但是对于少量，您只需使用带有简单程序的蛮力方法即可。用python编写，它不是最pythonic的，但更容易阅读。

法典：

def check(m,N):
    candidates = range(0, 2**(N-1))
    valid_candidates = []
    for candidate in candidates:
        binary_representation = [int(x) for x in list(('{:0%sb}' % (N-1)).format(candidate))]
        if sum(binary_representation) == m:
            #found candidate
            print(binary_representation)
            valid_candidates.append(binary_representation)
    return valid_candidates

if __name__ == "__main__":
    N = 5
    s = 2
    print("Number of valid combinations with N=%s and s=%s is: %s " %(N, s, len(check(s, N))))

输出：

[0, 0, 1, 1]
[0, 1, 0, 1]
[0, 1, 1, 0]
[1, 0, 0, 1]
[1, 0, 1, 0]
[1, 1, 0, 0]
Number of valid combinations with N=5 and s=2 is: 6

Answer 2

实现此目的的一种方法是使用递归。像这样的东西(JavaScript代码(：

function f(arr,k){
  if (k === 1)
    return [[arr]];
      
  var result = [];
  for (var i=1; i<=arr.length-k+1; i++){
    var head = arr.slice(0,i),
        tail = arr.slice(i),
        rest = f(tail,k - 1);
    rest.map(x => result.push([head].concat(x)));
  }
  return result;
}
console.log(JSON.stringify(f([1,2,3,4,5],3)));