Скажем, у меня есть следующий список
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]
Я хочу найти все возможные подсписчики определенной длины, где они не содержат одного определенного номера и не теряют порядок чисел.
Например, все возможные подписи с длиной 6 без 12:
[1,2,3,4,5,6]
[2,3,4,5,6,7]
[3,4,5,6,7,8]
[4,5,6,7,8,9]
[5,6,7,8,9,10]
[6,7,8,9,10,11]
[13,14,15,16,17,18]
Проблема в том, что я хочу сделать это в очень большом списке, и мне нужен самый быстрый способ.
Обновить с помощью моего метода:
oldlist = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]
newlist = []
length = 6
exclude = 12
for i in oldlist:
if length+i>len(oldlist):
break
else:
mylist.append(oldlist[i:(i+length)]
for i in newlist:
if exclude in i:
newlist.remove(i)
Я знаю, что это не лучший метод, поэтому мне нужен лучший.
Простое, не оптимизированное решение было бы
result = [sublist for sublist in
(lst[x:x+size] for x in range(len(lst) - size + 1))
if item not in sublist
]
Оптимизированная версия:
result = []
start = 0
while start < len(lst):
try:
end = lst.index(item, start + 1)
except ValueError:
end = len(lst)
result.extend(lst[x+start:x+start+size] for x in range(end - start - size + 1))
start = end + 1
Используйте itertools.combinations:
import itertools
mylist = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]
def contains_sublist(lst, sublst):
n = len(sublst)
return any((sublst == lst[i:i+n]) for i in xrange(len(lst)-n+1))
print [i for i in itertools.combinations(mylist,6) if 12 not in i and contains_sublist(mylist, list(i))]
Печать
[(1, 2, 3, 4, 5, 6), (2, 3, 4, 5, 6, 7), (3, 4, 5, 6, 7, 8), (4, 5, 6, 7, 8, 9), (5, 6, 7, 8, 9, 10), (6, 7, 8, 9, 10, 11), (13, 14, 15, 16, 17, 18)]
Самый простой способ, который я могу представить, - удалить исключенный номер из списка, а затем использовать itertools.combinations() для генерации желаемых подписок, это имеет дополнительное преимущество, что оно будет производить подсписки итеративно.
from itertools import combinations
def combos_with_exclusion(lst, exclude, length):
for combo in combinations((e for e in lst if e != exclude), length):
yield list(combo)
mylist = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]
for sublist in combos_with_exclusion(mylist, 12, 6):
print sublist
Вывод:
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 7]
[1, 2, 3, 4, 5, 8]
[1, 2, 3, 4, 5, 9]
[1, 2, 3, 4, 5, 10]
[1, 2, 3, 4, 5, 11]
[1, 2, 3, 4, 5, 13]
...
[11, 14, 15, 16, 17, 18]
[13, 14, 15, 16, 17, 18]
Мне нравится создавать решения из небольших составных частей. Несколько лет написания Haskell делает это с вами. Поэтому я бы сделал это так...
Во-первых, это вернет итератор по всем подспискам в порядке возрастания длины, начиная с пустого списка:
from itertools import chain, combinations
def all_sublists(l):
return chain(*(combinations(l, i) for i in range(len(l) + 1)))
В целом нам не рекомендуется использовать однобуквенные имена переменных, но я думаю, что в коротких очередях с очень абстрактным кодом это вполне разумная вещь.
(BTW, чтобы опустить пустой список, используйте range(1, len(l) + 1)).
Затем мы можем решить вашу проблему в целом, добавив ваши критерии:
def filtered_sublists(input_list, length, exclude):
return (
l for l in all_sublists(input_list)
if len(l) == length and exclude not in l
)
Итак, например:
oldlist = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]
length = 6
exclude = 12
newlist = filtered_sublists(old_list, length, exclude)
Моя попытка рекурсивного создания всех возможных списков. Параметр depth просто берет количество элементов для удаления из каждого списка. Это не скользящее окно.
код:
def sublists(input, depth): output= [] if depth > 0: for i in range(0, len(input)): sub= input[0:i] + input[i+1:] output += [sub] output.extend(sublists(sub, depth-1)) return output
Примеры (введенные интерактивно в python3):
sublists([1,2,3,4],1)
[[2, 3, 4], [1, 3, 4], [1, 2, 4], [1, 2, 3]]
sublists([1,2,3,4],2)
[[2, 3, 4], [3, 4], [2, 4], [2, 3], [1, 3, 4], [3, 4], [1, 4] [1, 3], [1, 2, 4], [2, 4], [1, 4], [1, 2], [1, 2, 3], [2, 3], [1, 3 ], [1, 2]]
sublists([1,2,3,4],3)
[[2, 3, 4], [3, 4], [4], [3], [2, 4], [4], [2], [2, 3], [3] [2], [1, 3, 4], [3, 4], [4], [3], [1, 4], [4], [1], [1, 3], [3] [1], [1, 2, 4], [2, 4], [4], [2], [1, 4], [4], [1], [1, 2], [2] 1, 2, 3, 3, 3, [1]]
Некоторые краевые случаи:
sublists([1,2,3,4],100)
[[2, 3, 4], [3, 4], [4], [3], [2, 4], [4], [2], [2, 3], [3] [2], [1, 3, 4], [3, 4], [4], [3], [1, 4], [4], [1], [1, 3], [3] [1], [1, 2, 4], [2, 4], [4], [2], [1, 4], [4], [1], [1, 2], [2] 1, 2, 3, 3, 3, [1]]
sublists([], 1)
[]
ПРИМЕЧАНИЕ: список результатов списка включает дубликаты.
У меня есть ответ, но я думаю, что это не самое лучшее:
oldlist = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]
result = []
def sub_list(lst):
if len(lst) <= 1:
result.append(tuple(lst))
return
else:
result.append(tuple(lst))
for i in lst:
new_lst = lst[:]
new_lst.remove(i)
sub_list(new_lst)
sub_list(oldlist)
newlist = set(result) # because it have very very very many the same
# sublist so we need use set to remove these also
# use tuple above is also the reason
print newlist
Он получит результат, но приведет к тому, что у него будет такой же подсписк, чтобы он нуждался в большой памяти и много времени. Я думаю, что это не очень хорошо.