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

给定一个数组[1,2,3,4,5]和数字s代表splits如何生成以下序列（希望我涵盖了所有s的组合= 3）。将数组拆分为s个具有uniq元素的子集

它被排序的数组以及每个子集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时。

来源

2017-03-17 user2502761

我看到你形容为“M N个代码的”或constant weight代码的问题...

N是单词的lenght（在你的情况下5-1 = 4） m是你想要做的重量或多少分割（ - s在你的情况下）

Word：1 - + - 2 - + - 3 - + - 4 - + - 5 分割位置：1 2 3 4

然后你可以说你的splits是一个布尔数组（当你想做一个拆分时，位置分割的数组中的位是t rue或1）

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

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

如在本维基article说，是定义的可能性的数目为任何arbitary组合没有分析方法。但对于小数目，您可以使用简单程序的强力方法。用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

来源

2017-03-17 10:25:44 renzop

的一种方式实现这一目标是与递归。像这样的东西（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)));

来源

2017-03-17 17:40:28

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

回答

相关问题