CODEWITHSUNDEEP
pythondata-structuresset
zangw
zangw

Reputation: 48366

Data structure to represent multiple equivalent keys in set in Python?

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

There are multiple arrays with disordered element, for example,

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

After processing those data, the result is,

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

With sorted element in each array and filter the duplicate arrays.

Here are my thoughts:

Upvotes: 6

Views: 322

Answers (5)

PM 2Ring
PM 2Ring

Reputation: 55469

No Python, doesn't have a built-in multiset; the closest equivalent in the standard modules is collections.Counter, which is a type of dictionary. A Counter may be suitable for your needs, but it's hard to tell without more context.


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

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 fairly small you don't need the set (and the list<->tuple conversions), just test membership in outlist. However, that's not efficient for larger input lists since it performs a linear search on the list.

Upvotes: 2

wim
wim

Reputation: 362557

Some of the solutions currently here are destroying ordering. I'm not sure if that's important to you or not, but here is a version which preserves original ordering:

>>> 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]]

Upvotes: 2

sam
sam

Reputation: 2033

Try this:

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

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

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

Thanks again to @PM2RING: one liner

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

Demo

Upvotes: 2

emvee
emvee

Reputation: 4449

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]]

Upvotes: 4

luoluo
luoluo

Reputation: 5533

Transform your list to tuple(thus can be a item of set), then back to list.

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

Upvotes: 5

Related Questions