Removing duplicate content from a list of lists while not preserving any order

Question

I was writing a code in python to find factor pairs for an integer. But making pairs resulted in reverse pairs as well. I want to eliminate those reverse pairs using a simple method without importing any modules. for eg.

[[1, 200], [2, 100], [4, 50], [5, 40], [8, 25], [10, 20], [20, 10], [25, 8], [40, 5], [50, 4], [100, 2], [200, 1]]

the output should be:

[[1, 200], [2, 100], [4, 50], [5, 40], [8, 25], [10, 20]]

This is what I've got so far:

N = []
J = []
F = []
Z = []
S = []
num = input("Enter no. of elements in list")
print ('Enter numbers')
prod = 1
for i in range(int(num)):
    n = input("num :")
    N.append(int(n))
for x in N:
    prod = prod*x
print (prod)
k = input("Enter no. of splits:")
for o in range(1,prod+1):
    if prod%o == 0:
        J.append(o)
        F.append(o)
print (J)

Z = [[a, b] for a in J for b in F if a*b == prod]
print (Z)

Answer 1

It's actually quite tricky to get that right in a general way.

It essentially boils down to two basic problems:

• Checking if two lists contain the same elements
• Remove all lists that contain the same elements

I'll tackle these separately.

Check if two lists contain the same elements

I best to refer to Raymond Hettingers answer from here:

O(n): The Counter() method is best (if your objects are hashable):

from collections import Counter
def compare(s, t):
    return Counter(s) == Counter(t)

O(n log n): The sorted() method is next best (if your objects are orderable):

def compare(s, t):
    return sorted(s) == sorted(t)

O(n * n): If the objects are neither hashable, nor orderable, you can use equality:

def compare(s, t):
    t = list(t)   # make a mutable copy
    try:
        for elem in s:
            t.remove(elem)
    except ValueError:
        return False
    return not t

In your case you don't want any imports so you could replace collections.Counter with:

def count(it):
    d = {}
    for item in it:
        try:
            d[item] += 1
        except KeyError:
            d[item] = 1
    return d

Just in case the items are hashable and you don't care about the count of the items (for example [1,1,2] should be interpreted as equal to [1,2,2]) or they will always be unique then you could also use sets:

def compare(s, t):
    return set(s) == set(t)

So that way you can check if two sublists contain the same elements. There are possible optimizations in case you might have lists of different lengths, then it could be worthwhile to add a:

if len(s) != len(t):
    return False

At the beginning of each of these functions.

Removing duplicates from the list

That also depends on assumptions about the result (should the non-duplicates keep their relative order or not) and the contents (again, can you hash the contents or can they be ordered).

If the items are hashable (or could be converted to something hashable) you could use a set call to remove duplicates. If you care about the order you can still use a set but only for lookups, for example the recipe from the itertools documentation unique_everseen:

from itertools import filterfalse

def unique_everseen(iterable, key=None):
    "List unique elements, preserving order. Remember all elements ever seen."
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D
    # unique_everseen('ABBCcAD', str.lower) --> A B C D
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in filterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element

You mentioned no imports but fortunately we don't need the key is None part anyway (see below) so you can simple use:

def unique_everseen(iterable, key):
    seen = set()
    seen_add = seen.add
    for element in iterable:
        k = key(element)
        if k not in seen:
            seen_add(k)
            yield element

Note that the approaches to compare the inner lists use sets, dictionaries and lists which are unhashable. But all of them can be converted to a hashable collections, like frozensets or tuples:

# for sets
frozenset(s)

# for dictionaries
frozenset(d.items())

# for lists
tuple(l)

However the last approach (if the items are unhashable and cannot be ordered) can't be used with this approach so let's ignore it for now.

Basically you could then use unique_everseen like this:

list(unique_everseen(your_list, key=lambda sublist: frozenset(count(sublist).items())))
# Or with collections.Counter instead of count

Or if you don't care about the duplicates (or there will be no duplicates) inside your sublists:

list(unique_everseen(your_list, key=frozenset))

Or if they are not hashable but can be ordered:

list(unique_everseen(your_list, key=lambda sublist: tuple(sorted(sublist))))

Just the approach in case the items in your sublist are not hashable and not orderable cannot be done using that fast unique_everseen approach. You'll have to use a slower variant:

def compare(s, t):
    t = list(t)   # make a mutable copy
    try:
        for elem in s:
            t.remove(elem)
    except ValueError:
        return False
    return not t

def unique_everseen_slow(iterable):
    seen = []
    for element in iterable:
        for already_seen_item in seen:
            if compare(element, already_seen_item):
                break  # We found a match, so stop looking
        else:
            seen.append(element)
            yield element

list(unique_everseen_slow(your_list))

The else clause belongs to the for loop and is only entered when there was no break. You could instead also check for any to avoid this for-else:

def unique_everseen_slow(iterable):
    seen = []
    for element in iterable:
        if not any(compare(element, seen_element) for seen_element in seen):
            seen.append(element)
            yield element

---

In your case it's actually very easy because the integers in the sublists are hashable and orderable. But this can become very complex for more general cases.

However in your case you could even avoid creating duplicate factors by simply checking that the factors are sorted (and if not stop):

def factors(number):
    for candidate in range(1, number + 1):
        if number % candidate == 0:
            other_factor = number // candidate
            if candidate > other_factor:
                return
            yield [candidate, other_factor]

For example:

>>> list(factors(200))
[[1, 200], [2, 100], [4, 50], [5, 40], [8, 25], [10, 20]]

Answer 2

Using set to remove duplicates.

Ex:

lst = [[1, 200], [2, 100], [4, 50], [5, 40], [8, 25], [10, 20], [20, 10], [25, 8], [40, 5], [50, 4], [100, 2], [200, 1]]
lst = set([tuple(sorted(i)) for i in lst])      #Sort inner list and then use set
lst = list(map(list, lst))                      #Converting back to list
print(lst)

Output:

[[8, 25], [4, 50], [1, 200], [10, 20], [2, 100], [5, 40]]

Answer 3

If the input is large, there is a significant performance advantage by using sets instead of lists.

>>> unique = set(map(frozenset, pairs))
>>> unique
{frozenset({1, 200}),
 frozenset({10, 20}),
 frozenset({5, 40}),
 frozenset({2, 100}),
 frozenset({8, 25}),
 frozenset({4, 50})}

The inner sets must be frozenset because regular sets are mutable, and sets can only contain immutable children.

To convert back to a list of lists.

>>> list(map(list, unique))
[[200, 1], [10, 20], [40, 5], [2, 100], [8, 25], [50, 4]]

Sets are iterable, so depending on your usage, this step might not be needed.

Here's a function that does both steps and returns the result as a nested list.

def unique_pairs(pairs): 
    return list(map(list,set(map(frozenset, pairs))))

Note that converting a list into a set will convert a list containing an identical pairs (for example [20,20]) to a single element set ({20}). So if your input can contain identical pairs, you might want to do an extra final step to expand singletons back to pairs.

def unique_pairs(pairs):
    return [(2*[*p])[:2] for p in set(map(frozenset,pairs))]

This will work with bot twin pairs and mixed pairs.

>>> pairs = [[10, 2], [2, 10], [10, 10], [2, 2]]
>>> unique_pairs(pairs)
[[10, 10], [2, 2], [10, 2]]

Answer 4

>>> l = [[1, 200], [2, 100], [4, 50], [5, 40], [8, 25], [10, 20], [20, 10], [25, 8], [40, 5], [50, 4], [100, 2], [200, 1]]
>>> new_l = []
>>> for e in l:
...     if e not in new_l and sorted(e) not in new_l:
...         new_l.append(e)
... 
>>> new_l
[[1, 200], [2, 100], [4, 50], [5, 40], [8, 25], [10, 20]]
>>>