How can I remove nested list items from a python list if they have the same order, but start at a different index

Question

How to remove 'circularly-similar' lists from a nested list. Two lists are 'circularly-similar' if they are the same after some circular rotation. For example [1,2,3,4] is circularly-similar to [3,4,1,2] because [1,2,3,4] rotated by 2 is [3,4,1,2]

Let's say I have the following list:

list = [[1, 1, 0], [0, 1, 1], [1, 1, 1]]

I would like to have [0, 1, 1] removed, because it is circularly-similar to [1, 1, 0] after rotation by 2. How should I approach this problem?

Does this answer your question? [How to remove an element from a list by index](https://stackoverflow.com/questions/627435/how-to-remove-an-element-from-a-list-by-index) — Countour-Integral, Jan 21 '21 at 20:59
@ChayimFriedman see it as a sort of modulo, if you shift the index by 1, you will have the same list. — Hidde van Esch, Jan 21 '21 at 21:01
Take a look at https://stackoverflow.com/questions/2150108/efficient-way-to-rotate-a-list-in-python and see if you can solve this yourself — Chayim Friedman, Jan 21 '21 at 21:06
@ChayimFriedman shifting can be done to both the right and left? No need to be smart here, please let me know how you would approach this problem. — Hidde van Esch, Jan 21 '21 at 21:07
You can shift a list `l` i to the right by doing `l[i:] + l[:i]`. — L3viathan, Jan 21 '21 at 21:08
Are you asking how to determine where *duplicates* exist or which one of a pair to remove? — wwii, Jan 21 '21 at 21:11
Ok, would you have to remove the item `[2,1,3]` if the item `[1,2,3]` preceded it? — quamrana, Jan 21 '21 at 21:13

Aven Desta · Accepted Answer · 2021-01-21T21:20:32.903

1

You first need to check if two lists are the same under rotation

# not very efficient algorithm but it works
# you can also import deque from collections for rotation operation

def is_circular_equal(a,b):
   if len(a) != len(b):
      return False  # if they are not of equal length
   for i in range(len(a)):
      if b == a[i:]+a[:i]:
         return True
   return False

Here is another post on how to do it.

Then loop through the list of lists to check if each is is_circular_equal as the other

edited Jan 21 '21 at 21:20

answered Jan 21 '21 at 21:09

Aven Desta

2,114
12
27

1

Could be considered out of scope, but I would at least make sure that they have the same length. – L3viathan Jan 21 '21 at 21:11
Using `collections.deque` is better, esp. if there are multiple lists with many elements. See https://stackoverflow.com/q/2150108/7884305 – Chayim Friedman Jan 21 '21 at 21:14
@L3viathan ya, I don't wanna make the code longer. But its necessary to check that they have the same length, and return False otherwise – Aven Desta Jan 21 '21 at 21:18

score 1 · Answer 2 · answered Jan 21 '21 at 21:13

1

Here's a bad solution (quadratic complexity):

def rotated_eq(a, b):
    return len(a) == len(b) and any(a == b[i:]+b[:i] for i in range(len(a)))


def prune_rotated_dupes(ls):
    result = []
    for element in ls:
        for existing in result:
            if rotated_eq(element, existing):
                break
        else:
            result.append(element)
    return result


list_in = [[1, 1, 0], [0, 1, 1], [1, 1, 1]]

assert prune_rotated_dupes(list_in) == [[1, 1, 0], [1, 1, 1]]

For a good solution, I would think about whether you can somehow generate a unique value for each rotated-identical list, and then use that value as an element of a set to test for existence.

answered Jan 21 '21 at 21:13

L3viathan

26,748
2
58
81

Would it help to make the sub-lists colection.deques? – wwii Jan 21 '21 at 21:14
I guess it would help with the cost of the rotation, but it wouldn't solve the issue of the nested for-loops. It's quadratic even if you assume `rotated_eq` is O(1). – L3viathan Jan 21 '21 at 21:15
It would be better if you would divide into groups by list length – Chayim Friedman Jan 21 '21 at 21:18
The best for complexity is using tuples and sets. The conversion (list->tuple->back to list) can be more expensive, but if there are many lists this can still be better – Chayim Friedman Jan 21 '21 at 21:19
@ChayimFriedman Sure. But all this doesn't change the asymptotic complexity, which is why I consider it premature optimization. Once the main problem is solved (generating a key value for each list) this probably won't even be necessary. – L3viathan Jan 21 '21 at 21:19
itertools.product/combinations would push the complexity to C. – wwii Jan 21 '21 at 21:19
@L3viathan a) Asymptotic complexity isn't all in life. b) Grouping by length does change the average complexity – Chayim Friedman Jan 21 '21 at 21:20
@ChayimFriedman In general I agree with that, but when it seems so tangible to make it linear I don't see the point in improving average complexity (yet). Same comment wrt. wwii's remark. – L3viathan Jan 21 '21 at 21:22

score 0 · Answer 3 · answered Jan 21 '21 at 21:11

0

I'd do something like:

xs = [[1, 1, 0], [0, 1, 1], [1, 1, 1]]                                                                                                                                                              

sorted_list = list(map(lambda x: sorted(x), xs))

final_list = []

for x in sorted_list:

    if x in final_list:
        continue
    final_list.append(x)

answered Jan 21 '21 at 21:11

Giovanni Rescia

605
5
15

This does not solve the above but compares unordered list (which is already covered at https://stackoverflow.com/q/7828867/7884305) – Chayim Friedman Jan 21 '21 at 21:12

How can I remove nested list items from a python list if they have the same order, but start at a different index

3 Answers3