Как я могу удалить кортеж из списка, если кортеж содержит два «1» рядом друг с другом в Python? - PullRequest
1 голос
/ 05 марта 2020

У меня есть список кортежей из этого:

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

Для n = 4 вывод будет следующим:

 [(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)]

Я хочу удалить кортежи, где хотя бы два «1» находятся рядом друг с другом, например, (0,1,1,0).

Я пробовал это:

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

Я думаю, это не работает, потому что это принимает j + 1 в качестве фактического число + 1, например, если j = 1, оно принимает значение 2 и т. д. c.

Что мне делать по-другому?

Ответы [ 5 ]

8 голосов
/ 05 марта 2020

Вы можете создать соседние пары с zip(i, i[1:]) и проверить, содержат ли они (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)]
5 голосов
/ 05 марта 2020

Ваш подход логичен, но, к сожалению, не будет работать в Python (или в большинстве других языков), и реализация не верна, потому что j==1 and j+1 == 1 никогда не верна; если j равно 1, то j+1 равно 2, точка. Но большая проблема заключается в том, что вы пытаетесь удалить элементы из списка, перебирая его, , что является нет-нет .

Сначала давайте решим вопрос о том, как проверить, если два 1 рядом друг с другом. Вместо того, чтобы смотреть на j и j+1, нам нужно взглянуть на t[j] и t[j+1], где t является одним из кортежей. Кроме того, j необходимо выполнить итерацию до длины минус 1, в противном случае t[j+1] даст IndexError в конце кортежа. Функция any является удобным способом сделать это:

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

Обратите внимание, что t[j] == t[j+1] == 1 работает в Python из-за цепных сравнений .

Сейчас Давайте решим проблему, как удалить такие элементы из списка. Гораздо удобнее просто создать новый список только с теми элементами, которые вы хотите, а не удалять те, которые вам не нужны. Понимание списка - это удобный способ сделать это:

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

Результат:

[(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)]

Все это говорит, что для больших n было бы более эффективно использовать алгоритм, который генерирует только те элементы, которые вам нужны, а не l oop по всему декартовому произведению (размером 2 n ) и отклонение тех, которые вам не нужны.

3 голосов
/ 05 марта 2020

Это должно помочь:

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

Условие not any(t[i] == 1 and t[i+1] == 1 for i in range(n-1)) в основном проверяет, равны ли последовательные элементы единице. Обратите внимание на итератор индекса range(n-1) - мы не хотим проверять элемент n th на элемент n + 1, поскольку ни в одном из кортежей нет пятого элемента выше.

Время

Обратите внимание, что моя функция примерно в два раза медленнее, чем , чем функция переполнения кучи .

>>> 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
2 голосов
/ 05 марта 2020

Добавление менее «pythoni c», но более удобочитаемого примера для рассмотрения:

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

Где a - исходный список кортежей.

0 голосов
/ 05 марта 2020

Можно сделать с помощью forl oop и использовать метод python any () тоже

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