0

我试图从一个列表中找到所有子集的组合，其中每个元素只使用一次。

为了澄清我的意思，给出一个示例列表：

[1、2、3、4]

我可以生成以下组合：

[(1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2, 3)] （这应该是详尽的！）

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

[[(1), (2), (3)], [(1, 2), (3)], [(1, 3), (2)], [(1), (2, 3)] ,[(1, 2, 3)],... (对于许多)]

要点是我只能在给定的组合中使用每个元素一次。所以我不能拥有：

[(1), (1, 2, 3)] 因为元素 1 被使用了两次。

我一直在尝试对小 n （n < 10）进行暴力破解，并且一直在使用 python 失败。在这一点上，它甚至不是运行时问题（小 n！），但我什至没有找到所有的可能性！

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

谢谢！

编辑 1：查看此问题的另一种方法是使用子集和问题，但警告 1：不仅要找到所有可能的子集，还要找到所有子集组合集，以便使用原始列表的最多元素，其中每个单独的子集总和为 0（或 k）。

我的目标是遍历所有答案并根据最终未使用的元素数量对它们进行评分，并选择一组“最佳”子集。

编辑 2：接受的答案，但修改为接受用户创建的列表 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],)]
4

1 回答 1

2

递归！生成 1..n 的所有可能分区，然后使用这些生成 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,)]
于 2013-10-03T21:45:26.750 回答