在2D数组中删除无序重复项的最省时的方法是什么？

Question

我已经使用itertools生成了一个组合列表，并且得到的结果看起来像这样：

nums = [-5,5,4,-3,0,0,4,-2]
x = [x for x in set(itertools.combinations(nums, 4)) if sum(x)==target]
>>> x = [(-5, 5, 0, 4), (-5, 5, 4, 0), (5, 4, -3, -2), (5, -3, 4, -2)]

删除无序重复项（例如x[0]和x[1]）最有效的时间复杂度方法是重复项。有内置的东西可以处理吗？

我一般的方法是在一个元素中创建所有元素的计数器，然后与下一个元素进行比较。这是最好的方法吗？

谢谢您的指导。

Answer 1

由于您要查找无序重复项，所以最好的方法是通过类型转换。 Typecast作为set。由于set仅包含immutable元素。因此，我制作了一组[tuples。

---

注意：

消除重复项的最佳方法是对给定元素进行[set。

>>> set(map(tuple,map(sorted,x)))
{(-3, -2, 4, 5), (-5, 0, 4, 5)}

Answer 2

最好的方法是首先不要生成重复项。

想法是首先创建出现多次的所有可能值组合，其中每个出现0、1，...次。然后，我们使用唯一元素的所有可能组合来完成它们。

from itertools import combinations, product, chain
from collections import Counter

nums = [-5,5,4,-3,0,0,4,-2]

def combinations_without_duplicates(nums, k):
    counts = Counter(nums)
    multiples = {val: count for val, count in counts.items() if count >= 2 }
    uniques = set(counts) - set(multiples)              
    possible_multiples = [[[val]*i for i in range(count+1)] for val, count in multiples.items()]
    multiples_part = (list(chain(*x)) for x in product(*possible_multiples))
    # omit the ones that are too long
    multiples_part = (lst for lst in multiples_part if len(lst) <= k)
    # Would be at this point:
    # [[], [0], [0, 0], [4], [4, 0], [4, 0, 0], [4, 4], [4, 4, 0], [4, 4, 0, 0]]
    for m_part in multiples_part:
        missing = k - len(m_part)
        for c in combinations(uniques, missing):
            yield m_part + list(c)


list(combinations_without_duplicates(nums, 4))

输出：

[[-3, -5, 5, -2],
 [0, -3, -5, 5],
 [0, -3, -5, -2],
 [0, -3, 5, -2],
 [0, -5, 5, -2],
 [0, 0, -3, -5],
 [0, 0, -3, 5],
 [0, 0, -3, -2],
 [0, 0, -5, 5],
 [0, 0, -5, -2],
 [0, 0, 5, -2],
 [4, -3, -5, 5],
 [4, -3, -5, -2],
 [4, -3, 5, -2],
 [4, -5, 5, -2],
 [4, 0, -3, -5],
 [4, 0, -3, 5],
 [4, 0, -3, -2],
 [4, 0, -5, 5],
 [4, 0, -5, -2],
 [4, 0, 5, -2],
 [4, 0, 0, -3],
 [4, 0, 0, -5],
 [4, 0, 0, 5],
 [4, 0, 0, -2],
 [4, 4, -3, -5],
 [4, 4, -3, 5],
 [4, 4, -3, -2],
 [4, 4, -5, 5],
 [4, 4, -5, -2],
 [4, 4, 5, -2],
 [4, 4, 0, -3],
 [4, 4, 0, -5],
 [4, 4, 0, 5],
 [4, 4, 0, -2],
 [4, 4, 0, 0]]