Data structure for representing multiple equivalent keys in a set in Python?

Question

Currently, I want to find the right data structure to meet the following requirement.

There are several arrays with an unordered element, for example

[1, 2], [2, 1], [3, 2, 2], [2], [2, 1, 3], [2, 2, 3]

After processing this data, the result:

[1, 2], [2, 2, 3], [2], [1, 2, 3]

With a sorted element in each array and a filter of repeating arrays.

Here are my thoughts:

• Set(Arrays) data structure? - Failed. Seems in assembly set

  there is only one array.

  set([])

• Array(Sets) data structure? - Failed. However, in the built-in set there is no duplicate element. I want to know if there is one data structure like multiset in C ++ in Python?

Answer 1

Convert the list into a tuple (so it can be a collection item), then go back to the list.

 >>> [list(i) for i in set([tuple(sorted(i)) for i in a])] [[1, 2], [2], [2, 2, 3], [1, 2, 3]] 

Answer 2

 lst = [[1, 2], [2, 1], [3, 2, 2], [2], [2, 1, 3], [2, 2, 3]] map(list, set(map(tuple, map(sorted, lst))) 

Output:

 [[1, 2], [2], [2, 2, 3], [1, 2, 3]] 

Answer 3

Try the following:

 [list(i) for i in set(map(tuple, a))] 

EDIT: Assuming list already sorted. Thanks @ PM2RING to remind me. If not, add this line above

 a = [sorted(i) for i in a] 

Thanks again @ PM2RING: one liner

 [list(i) for i in set(map(tuple, (sorted(i) for i in a)))] 

Demo

Answer 4

No Python, no built-in multiset; the closest equivalent in standard collections.Counter modules, which is a dictionary type. A counter may be appropriate for your needs, but it is hard to say without additional context.

Note that sets do not preserve the order of addition. If you need to keep the initial order of the lists, you can do what you want:

 data = [[1, 2], [2, 1], [3, 2, 2], [2], [2, 1, 3], [2, 2, 3]] a = set() outlist = [] for s in data: t = tuple(sorted(s)) if t not in a: a.add(t) outlist.append(list(t)) print(outlist) 

Output

 [[1, 2], [2, 2, 3], [2], [1, 2, 3]] 

If the number of input lists is rather small, you do not need a set (and transformations of the list ↔ tuples), just check outlist membership. However, this is inefficient for large input lists because it performs a linear search on the list.

Answer 5

Some of the solutions currently disrupt order. I'm not sure if this is important to you or not, but here is a version that keeps the original order:

 >>> from collections import OrderedDict >>> A = [[1, 2], [2, 1], [3, 2, 2], [2], [2, 1, 3], [2, 2, 3]] >>> [list(k) for k in OrderedDict.fromkeys(tuple(sorted(a)) for a in A)] [[1, 2], [2, 2, 3], [2], [1, 2, 3]]