Как найти все возможные подгруппы в группе

Question

Допустим, мы имеем группу 1,2,3 Таким образом, возможные подгруппы:

{1,2,3} 
    {1} {2,3} 
    {1,2} {3} 
    {1,3} {2} 
    {1} {2} {3} 

Вы получаете идею.

Я должен сделать это, используя рекурсию. То, что я до сих пор (не работает), и это немного другое. Идея состоит в том, что у вас есть список ints, который представляет кубы (для создания башни), и вы хотите построить столько вышек, сколько сможете, с определенной высоты. Итак, скажем, вы получите список кубов [5,2,6,6,1,1,4], а высота, которую вы хотите, - 7, тогда лучшим вариантом будет [5,2] [6,1] [6,1] [4].

код:

def find_tower(blocks, height): 

    def solve(groups, cur_group, index): 
     if index == len(blocks): 
      return groups 
     if sum(cur_group) == height: 
      new_group = list(groups) 
      new_group.append(cur_group) 
      return solve(new_group, [], index) 
     elif sum(cur_group) > height: 
      return solve(groups, [], index) 

     r1 = solve(groups, cur_group + [blocks[index]], index+1) 
     r2 = solve(groups, cur_group, index+1) 
     return max(r1, r2, key=lambda x: len(x)) 
    return solve([], [], 0) 

, но я просто получить [5,2] [6,1]. Есть идеи?

Answer 1

Ваша главная проблема заключалась в том, что вы не повторяли на значения, которые вы не использовали, например: Сначала вы берете 5,2 , чем 6,6, но его не хорошо, так что вы пропустите и не принимать 6,1 , но вы никогда не возьмете первые 6 и получите еще одно комбо из 6,1. Вот почему вам нужно повторить все значения после того, как вы выберете одну комбинацию.

код (вероятно, может быть лучше, Использовали ли вы логика):

def find_tower(blocks, height): 

def solve(groups, cur_group, index): 
    if sum(cur_group) == height: 
     new_group = list(groups)# if tower is on right height 
     new_group.append(cur_group)# add to groups of towers 
     return solve(new_group, [], 0) 
    if index == len(blocks):# if index max 
     return groups 
    elif sum(cur_group) > height:# if its higher than height 
     return groups 
    elif blocks[index] is None:# if its a None index skip 
     return solve(groups, cur_group, index+1) 

    temp = blocks[index] 
    blocks[index] = None# changing used value to none 
    r1 = solve(groups, cur_group + [temp], index+1) 
    blocks[index] = temp# puttin back used value 
    r2 = solve(groups, cur_group, index+1) 
    return max(r1, r2, key=lambda x: len(x))# return longer group 
return solve([], [], 0) 

Answer 2

Я не говорю следующее эффективным, но это дает вам представление о том, как построить результат рекурсивно:

import itertools 

def partitions(items, n): 
    if n == 1: 
     return [set([e]) for e in items] 
    results = partitions(items, n - 1) 
    for i, j in itertools.combinations(range(len(results)), 2): 
     newresult = results[i] | results[j] 
     if newresult not in results: 
      results.append(newresult) 
    return results 


items = [1,2,3] 
print partitions(items, len(items)) 
# [set([1]), set([2]), set([3]), set([1, 2]), set([1, 3]), set([2, 3]), set([1, 2, 3])] 

Answer 3

Это то, что я придумал

def find_tower(blocks,height): 

    groups = [] 
    blocks = sorted(blocks,reverse=True) 

    while sum(blocks) > height: 
     curgroup = [] 
     running_total = height 
     while sum(curgroup) < height: 
      possibilities = [block for block in blocks if 
          block <= running_total] 
      if possibilities: 
       selected_block = blocks.index(max(possibilities)) 
      else: 
       break 
      running_total -= blocks[selected_block] 
      curgroup.append(blocks.pop(selected_block)) 
     groups.append(curgroup) 
    groups = groups+[blocks] 
    return groups 

Выход:

IN: print(find_tower([13,12,11,10,9,8,1,1,1,1,1,1],13)) 


OUT: [[13], [12, 1], [11, 1, 1], [10, 1, 1, 1], [9], [8]] 

EDIT: D'oh! Когда я посмотрел на эту проблему, я не видел требования, чтобы это было сделано путем рекурсии. Я ненавижу рекурсию ... Позвольте мне посмотреть, смогу ли я заставить ее работать, но дайте мне немного времени.

Answer 4

Вот простой подход с использованием рекурсии. Идея состоит в том, что для списка, состоящего из x и некоторых других элементов xs, множество подмножеств - это все подмножества xs, плюс подмножества xs с добавленным x.

from copy import * 

def all_subsets(xs): 
    if not xs: 
    return [[]] 
    else: 
    x = xs.pop() 
    subsets = all_subsets(xs) 
    subsets_copy = deepcopy(subsets) # NB you need to use a deep copy here! 
    for s in subsets_copy: 
     s.append(x) 
    subsets.extend(subsets_copy) 
    return subsets