Как перебрать список, чтобы получить комбинацию всех следующих значений - PullRequest
Новая
       37

Как перебрать список, чтобы получить комбинацию всех следующих значений

0 голосов
/ 03 августа 2020

Проблема: Получить комбинацию всех следующих значений массива.

Объяснение: Все значения должны быть сформированы из смежных элементов в массиве.

Возможное решение (не оптимальное): 

l_number= list("24256")
result= []
while l_number:
    n = "" 
    for x in l_number:
        n += x
        result.append(str(n))
    
    l_number.pop(0)
print(result)

Результат: 

['2', '24', '242', '2425', '24256', '4', '42', '425', '4256', '2', '25', '256', '5', '56', '6']

Я получил это, но это не очень эффективно.

Есть ли какой-нибудь оптимизированный способ сделать это?

1 Ответ

1 голос
/ 03 августа 2020

Поскольку вы будете выводить все смежные подсписки, размер вывода будет O (N ^ 2), где N - длина списка, а временная сложность будет не менее квадратичной c независимо от того, что (вы может достичь линейной пространственной сложности с помощью генератора). Вот один из способов вычислить все смежные подстроки с пониманием списка: 

s = "24256"
n = len(s)
res = [s[i:j] for i in range(n) for j in range(i+1,n+1)]
print(res)
# ['2', '24', '242', '2425', '24256', '4', '42', '425', '4256', '2', '25', '256', '5', '56', '6']

В стороне, обычно нежелательно создавать списки с str += ..., поскольку новая копия str создается на каждая итерация. Один из обходных путей - создать список компонентов и вызвать .join после того, как все компоненты будут найдены.

...