查找列表的所有可能子集的所有可能组合 [英] Finding all possible combination of all possible subsets of lists

问题描述

我正在尝试从列表中查找的子集的所有组合，其中每个元素仅使用一次.

I am trying to find all combinations of subsets of from a list, where each element is used only once.

为了阐明我的意思，给出一个示例列表:

To clarify what I mean, given an example list of:

[1、2、3、4]

[1, 2, 3, 4]

我可以生成以下组合:

[((1)，(2)，(3)，(1、2)，(1、3)，(2、3)，(1、2、3)]](应该详尽无遗！)

[(1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2, 3)] (this should be exhaustive!)

然后我可以生成这些组合的组合:

Then I can generate combinations of these combinations:

[[((1)，(2)，(3)]，[(1，2)，(3)]，[(1，3)，(2)]，[(1)，(2， 3)]，[(1、2、3)]，...(很多)]

[[(1), (2), (3)], [(1, 2), (3)], [(1, 3), (2)], [(1), (2, 3)],[(1, 2, 3)],... (for many)]

主要要点是，在给定的组合中，每个元素只能使用一次.所以我不能:

The main point is that I am only allowed to use each element once, in a given combination. So I cannot have:

[(1)，(1、2、3)]，因为元素1被使用了两次.

[(1), (1, 2, 3)] because element 1 is used twice.

我一直在尝试用小n(n <10)蛮力，并且使用python失败了.在这一点上，它甚至不是运行时问题(小n！)，但我什至没有找到所有的可能性！

I have been trying to brute force for small n (n < 10), and have been failing, using python. At this point it is not even a runtime problem (small n!), but I am not even finding all the possibilities!

我不确定我是否很好地提出了我的问题，所以请问清楚问题.另外，如果有某些关键词可以帮助我阐明问题，请说出来！我对Python方法感兴趣-但是愿意接受任何MATH方法来帮助我做到这一点.运行时是我希望以后解决的问题！

I am not sure that I am formulating my question very well, so please ask clarify questions. Also, if there are certain key words to help me clarify the question, do tell! I am interested in a Python approach - but am open to any MATH approaches to help me do this. Runtime is an issue that I hope to tackle later!

谢谢！

查看此问题的另一种方法是子集和问题，但警告1:不仅找到所有可能的子集，还找到子集组合的所有集合，以使原始列表中的元素数最多使用，其中每个子集的总和为0(或k).

Edit 1: Another way of viewing this question is with the subset sum problem, but caveat 1: not just find all possible subsets, but find all sets of combination of subsets such that, the most number of elements of the original list is used, where each individual subset sums to 0 (or k).

我的目标是循环浏览所有答案，并根据最终未使用的元素数量对它们进行评分，并选择一组最佳"子集.'

My goal is to then loop through all answers and score them based on how many elements were ultimately unused and pick a "best" set of subsets.'

接受答案，但修改为接受用户创建的列表 myList = ['a'，'b'，'c'，'d']

Edit 2: accepted answer, but modified to accept a user created list myList = ['a', 'b', 'c', 'd']

def partitions(myList):
   if not myList:
       yield []
   else:
       for partial_partition in partitions(myList[:-1]):
           for i in range(len(partial_partition)):
               copy_partition = partial_partition[:]
               copy_partition[i] += (myList[-1],)
               yield copy_partition
           yield partial_partition + [(myList[-1],)]

推荐答案

递归！生成1..n的所有可能分区，然后使用它们来生成1..n + 1的所有可能分区:

Recursion! Generate all possible partitions of 1..n, then use those to generate all possible partitions of 1..n+1:

def partitions(n):
    if n == 0:
        yield []
    else:
        for partial_partition in partitions(n-1):
            for i in range(len(partial_partition)):
                copy_partition = partial_partition[:]
                copy_partition[i] += (n,)
                yield copy_partition
            yield partial_partition + [(n,)]

这篇关于查找列表的所有可能子集的所有可能组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！