How can I remove a tuple from a list if the tuple contains two "1" next to each other in Python?

Question

I have a list of tuples from this:

from itertools import product
l1 = list((product((0,1), repeat = n)))

For n=4, output is the following:

 [(0, 0, 0, 0),
 (0, 0, 0, 1),
 (0, 0, 1, 0),
 (0, 0, 1, 1),
 (0, 1, 0, 0),
 (0, 1, 0, 1),
 (0, 1, 1, 0),
 (0, 1, 1, 1),
 (1, 0, 0, 0),
 (1, 0, 0, 1),
 (1, 0, 1, 0),
 (1, 0, 1, 1),
 (1, 1, 0, 0),
 (1, 1, 0, 1),
 (1, 1, 1, 0),
 (1, 1, 1, 1)]

I want to remove the tuples where at least two "1" are next to each other, for example the (0,1,1,0).

I tried this:

for i in l1:
    for j in i:
         if j==1 and j+1 == 1:
                l1.remove(i)

I guess this is not working because it takes j+1 as the actual number + 1, like if j=1 it takes as 2 and etc.

What should I do differently?

`l2 = [v for v in l1 if '11' not in ''.join(list(map(str, v)))]` As long as there's no `11` value in the list — ChatterOne, Mar 05 '20 at 13:44
Related: [Permutations with repetition without two consecutive equal elements](https://stackoverflow.com/q/44923505/7851470) — Georgy, Mar 09 '20 at 09:07

score 9 · Answer 1 · answered Mar 05 '20 at 13:28

You could build neighbor pairs with zip(i, i[1:]) and check whether they contain (1, 1):

>>> [i for i in l1 if (1, 1) not in zip(i, i[1:])]
[(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 1, 0, 0),
 (0, 1, 0, 1), (1, 0, 0, 0), (1, 0, 0, 1), (1, 0, 1, 0)]

score 5 · Accepted Answer · answered Mar 05 '20 at 13:36

Your approach makes logical sense but unfortunately won't work in Python (or most other languages), and the implementation isn't correct because j==1 and j+1 == 1 is never true; if j is equal to 1 then j+1 is equal to 2, period. But the bigger issue is that you are trying to remove things from a list while iterating over it, which is a no-no.

First let's solve the problem of how to check if two 1s are next to each other. Instead of looking at j and j+1, we need to look at t[j] and t[j+1] where t is one of the tuples. Also, j needs to iterate up to the length minus 1, otherwise t[j+1] will give an IndexError at the end of the tuple. The any function is a convenient way to do this:

any(t[j] == t[j+1] == 1 for j in range(n - 1))

Note that t[j] == t[j+1] == 1 works in Python because of chained comparisons.

Now let's solve the problem of how to remove such elements from the list. It is much more convenient to simply build a new list with just the elements you want, rather than remove the ones you don't want. A list comprehension is a convenient way to do this:

result = [
    t for t in product((0, 1), repeat=n)
    if not any(t[j] == t[j+1] == 1 for j in range(n - 1))
]

Result:

[(0, 0, 0, 0),
 (0, 0, 0, 1),
 (0, 0, 1, 0),
 (0, 1, 0, 0),
 (0, 1, 0, 1),
 (1, 0, 0, 0),
 (1, 0, 0, 1),
 (1, 0, 1, 0)]

All of that said, for larger n it would be more efficient to use an algorithm which generates only the elements you do want, rather than loop over the whole cartesian product (of size 2ⁿ) and reject the ones you don't want.

You're right, of course, although the number of remaining tuples is still [exponential](https://repl.it/repls/PinkLoyalCoderesource), so presumably they can't go very high anyway. — Kelly Bundy, Mar 05 '20 at 14:01
A non-rejection-based algorithm should still be exponential, but with a lower base (in this case, 1.618 instead of 2), so the improvement is also an exponential factor. — kaya3, Mar 05 '20 at 14:04
Yeah, true. I mostly found it funny that yet another famous thing popped up non-obviously :-) — Kelly Bundy, Mar 05 '20 at 14:06

blacksite · Answer 3 · 2020-03-05T14:02:14.857

This ought to do the trick:

>>> n = 4
>>> from itertools import product
>>> l1 = list((product((0,1), repeat = n))) 
>>> l1
[(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 1, 1), (0, 1, 0, 0), (0, 1, 0, 1), (0, 1, 1, 0), (0, 1, 1, 1), (1, 0, 0, 0), (1, 0, 0, 1), (1, 0, 1, 0), (1, 0, 1, 1), (1, 1, 0, 0), (1, 1, 0, 1), (1, 1, 1, 0), (1, 1, 1, 1)]
>>> [t for t in l1 if not any(t[i] == 1 and t[i+1] == 1 for i in range(n-1))]
[(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 1, 0, 0), (0, 1, 0, 1), (1, 0, 0, 0), (1, 0, 0, 1), (1, 0, 1, 0)]

The not any(t[i] == 1 and t[i+1] == 1 for i in range(n-1)) condition basically checks whether consecutive elements are equal to one. Note the range(n-1) index iterator - we don't want to check the nth element against the n+1th element since there isn't a fifth element in any of the tuples above.

Timing

Note my function is about twice as slow as that of Heap Overflow.

>>> from time import time as t
>>> def f1():
...     t0 = t()
...     result = [i for i in l1 if (1, 1) not in zip(i, i[1:])]
...     t1 = t()
...     print(t1-t0)
... 
>>> def f2():
...     t0 = t()
...     result = [t for t in l1 if not any(t[i] == 1 and t[i+1] == 1 for i in range(n-1))]
...     t1 = t()
...     print(t1-t0)
... 
>>> l1 = list((product((0,1), repeat = n))) * 1000000
>>> len(l1)
16000000
>>> f1()
8.146391868591309
>>> f2()
18.645386934280396

Milan Velebit · Answer 4 · 2020-03-05T14:09:34.737

2

Adding a less "pythonic" but more readable example for consideration:

def filter_helper(t):
  for i, val in enumerate(t):
    if i != 0 and (t[i-1]) == val and val == 1:
      return False  
  return True

print(list(filter(filter_helper, a)))

Where a is the original list of tuples.

edited Mar 05 '20 at 14:09

answered Mar 05 '20 at 13:34

Milan Velebit

1,933
2
15
32

@kaya3 Great catch, thanks, added the missing cond. – Milan Velebit Mar 05 '20 at 14:09

score 0 · Answer 5 · answered Mar 05 '20 at 14:30

0

Can be done with forloop and use of python's any() method too

for x in l1:
    if any([(x[i]==x[i+1]==1) for i in x]) == True:
        l1.remove(x)

answered Mar 05 '20 at 14:30

spontaneous_coder

117
1
2
13

How can I remove a tuple from a list if the tuple contains two "1" next to each other in Python?

5 Answers5