时间戳

首页 > 解决方案 > 带有重复项的子集，仅返回空列表的问题

python - 带有重复项的子集，仅返回空列表的问题

问题描述

我正在研究以下问题：

给定一组可能包含重复的数字，找到其所有不同的子集。

您可以使用以下示例：

示例 1：
输入：[1, 3, 3]
输出：[], [1], [3], [1,3], [3,3], [1,3,3]

示例 2：
输入：[1, 5, 3, 3]
输出：[], [1], [5], [3], [1,5], [1,3], [5,3], [ 1,5,3], [3,3], [1,3,3], [3,3,5], [1,5,3,3]

我的方法是

class Solution:
    def distinct_subset(self, nums):
        n = len(nums)
        previousEnd = 0
        output = []
        for i in range(n):
            # judge if the current element is equal to the previous element 
            # if so, only update the elements generated in the previous iteration
            if i > 0 and nums[i] == nums[i-1]:
                previousStart = previousEnd + 1
            else:
                previousStart = 0
            perviousEnd = len(output)
            # create a temp array to store the output from the previous iteration
            temp = list(output[previousStart:previousEnd])
            # add current element to all the array generated by the previous iteration
            output += [j + [nums[i]] for j in temp]
        return output



def main():

  print("Here is the list of subsets: " + str(Solution().distinct_subset([1, 3, 3])))
  print("Here is the list of subsets: " + str(Solution().distinct_subset([1, 5, 3, 3])))


main()

但是，我的方法只会返回 []：

Here is the list of subsets: []
Here is the list of subsets: []

Process finished with exit code 0

我不知道为什么我出错了。该算法假设在每次迭代中更新输出。但现在它失败了。

请随时分享您的想法。感谢您在高级方面的帮助。

标签： pythonlistappendcascade

解决方案

You're looking for distinct combinations of the powerset of your list.

Using itertools to generate the combinations and a set to eliminate duplicates, you could write the function like this:

from itertools import combinations
def uniqueSubsets(A):
    A = sorted(A)
    return [*map(list,{subset for size in range(len(A)+1) 
                              for subset in combinations(A,size)})]

print(uniqueSubsets([1,3,3]))
# [[1, 3], [3, 3], [1], [3], [], [1, 3, 3]]

print(uniqueSubsets([1,5,3,3]))
# [1, 3] [3, 3] [1] [3] [3, 3, 5] [1, 3, 5] [1, 5] [5] [] [1, 3, 3, 5] [1, 3, 3] [3, 5]

If you have a lot of duplicates, it may be more efficient to filter them out as you go. Here is a recursive generator function that short-circuits the expansion when a combination has already been seen. It generates combinations by removing one element at a time (starting from the full size) and recursing to get shorter combinations.

def uniqueSubsets(A,seen=None):
    if seen is None: seen,A = set(),sorted(A)  
    for i in range(len(A)):         # for each position in the list
        subset = (*A[:i],*A[i+1:])  # combination without that position
        if subset in seen: continue # that has not been seen before
        seen.add(subset)
        yield from uniqueSubsets(subset,seen) # get shorter combinations
    yield list(A)

print(*uniqueSubsets([1,3,3]))
# [] [3] [3, 3] [1] [1, 3] [1, 3, 3]

print(*uniqueSubsets([1,5,3,3]))
# [] [3] [3, 3] [5] [5, 3] [5, 3, 3] [1] [1, 3] [1, 3, 3] [1, 5] [1, 5, 3] [1, 5, 3, 3]

In both cases we are sorting the list in order to ensure that the combinations will always present the values in the same order for the set() to recognize them. (otherwise lists such as [3,3,1,3] could still produce duplicates)

推荐阅读