將數組拆分爲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元素的子集

回答

相關問題