組合，允許重疊

Question

語境

• 我有項目的列表
• 我還具有這樣的結構以s級
• 級的級的數目可以更大，等於或小於項目數
• 每一級可以有n個時隙
• 項目可以按觀測同一階段通過採取2個時隙在該階段
• 槽'順序無關緊要
• 時隙的數量小於或等於所述數目項
• 每個時隙可以包含一個項目
• 的槽可以是空的
• 任何給定的結構可以只包含每個項目
一次

問題：

我要生成的項目在結構上分佈的所有組合，使得：

• 每個項目一次且僅一次出現在結構
• 所有的項目都是存在於每個組合
• 我想使用Java實施

例子：

/* Inputs */ 
items = {1, 2} 
structure = [ {}, {}, {}] // with 3 stages 

/* Outputs */ 
comb1 = [ {1,2}, {}, {} ] 
comb2 = [ {1}, {2}, {} ] 
comb3 = [ {1}, {}, {2} ] 
comb4 = [ {}, {1,2}, {} ] 
comb5 = [ {}, {1}, {2} ] 
comb6 = [ {}, {}, {1,2}] 
comb7 = [ {}, {2}, {1} ] 
comb8 = [ {2}, {1}, {} ] 
comb9 = [ {2}, {}, {1} ] 

想法是非常受歡迎的。

Answer 1

這裏是解決方案：

import time 


def get_stages(size): 
    stages = [] 
    for i in range(0, size): 
     stages.append([]) 
    return stages 

def get_combos(combo_size, stage_size): 
    combos = [] 
    for i in range(0, combo_size): 
     combos.append(get_stages(stage_size)) 
    return combos 


def insert_item_in_stage(stages, position, item): 
    stages[position].append(item) 

def copy_stages(stages): 
    #print 'copying', stages 
    copies = [] 
    for i in range(0, len(stages)): 
     copy = [] 
     for stage in stages: 
     stage_copy = [] 
     for slot in stage: 
      stage_copy.append(slot) 
     copy.append(stage_copy) 
     copies.append(copy) 
    return copies 

def combine(items, stages, all_combos): 
    #print items, 'with', stages 
    if len(items) == 1: 
     item = items[0] 
     combos = copy_stages(stages) 
     for combo in combos: 
     combo[combos.index(combo)].append(item) 
     all_combos.append(combo) 
    elif len(items) > 1: 
     item = items[0] 
     items.remove(item) 
     combos = copy_stages(stages) 

     for combo in combos: 
     combo[combos.index(combo)].append(item) 
     combine(list(items), combo, all_combos) 
    else: 
     print 'oops' 


def test (items, size): 
    print 'test', items, 'with', size, "stages" 
    stages = get_stages(size) 
    all_combos = [] 
    combine(items, stages, all_combos) 
    for combo in all_combos: 
     print combo 
    print len(all_combos) 
    print '' 

#run tests 
test([1,2], 3) 
test([1,2,3], 3) 
start = time.clock() 
test([1,2,3,4,5, 6], 8) 
end = time.clock() 
print end-start