Как найти все возможные последовательные и не перекрывающиеся списки с минимальной длиной 3 - PullRequest
Новая
       19

Как найти все возможные последовательные и не перекрывающиеся списки с минимальной длиной 3

3 голосов
/ 26 мая 2019

Что я на самом деле хочу сделать, так это уместить все возможные прямые в некоторые данные и найти лучшую группу подобранных линий, измерив их средний квадрат R *. 1001 *

Шаг, который я застрял, состоит в том, как получить достаточным методом все эти возможные подсписки, чтобы потом можно было подгонять. Это также причина, почему я хочу минимальную длину 3, потому что каждая линия, которая проходит через две точки, идеально подходит, и я не хочу этого.

Например, моя первая попытка была примерно такой: 

def sub_lists(lst):
    lr = [lst[:i] for i in range(3,len(lst)-2)]
    rl = [lst[i:] for i in range(len(lst)-3,2,-1)]
    return [[lr[i], rl[-i-1]] for i in range(len(lr))]

>>> tst = [489, 495, 501, 506, 508, 514, 520, 522]
>>> sub_lists(tst)
[[[489, 495, 501], [506, 508, 514, 520, 522]],
[[489, 495, 501, 506], [508, 514, 520, 522]],
[[489, 495, 501, 506, 508], [514, 520, 522]]]

но потом я наткнулся на приведенный ниже список длиной 5, и он не сработал. Таким образом, ожидаемый результат будет просто списком: 

>>> tst = [489, 495, 501, 506, 508]
>>> sub_lists_revised(tst)
[489, 495, 501, 506, 508]

и следуя той же логике, когда у меня большая длина данных, например, 10: 

>>> tst = [489, 495, 501, 506, 508, 514, 520, 525, 527, 529]
>>> sub_lists_revised(tst)
# the whole list
[489, 495, 501, 506, 508, 514, 520, 525, 527, 529]
# all possible pairs
[[[489, 495, 501], [506, 508, 514, 520, 525, 527, 529]],
[[489, 495, 501, 506], [508, 514, 520, 525, 527, 529]],
[[489, 495, 501, 506, 508], [514, 520, 525, 527, 529]],
[[489, 495, 501, 506, 508, 514], [520, 525, 527, 529]],
[[489, 495, 501, 506, 508, 514, 520], [525, 527, 529]]]
# and finally, all possible triplets which i couldn't figure out
[[[489, 495, 501], [506, 508, 514], [520, 525, 527, 529]],
[[489, 495, 501], [506, 508, 514, 520], [525, 527, 529]],
[[489, 495, 501, 506], [508, 514, 520], [525, 527, 529]]]

Итак, в заключение я хочу сказать, что мне нужен общий подход, который будет работать для получения еще большего количества данных, хотя я не думаю, что в настоящий момент мне действительно понадобится больше, чем триплеты.

Я также добавляю цифры из первого примера после подгонки: fig1 , fig2 , fig3

1 Ответ

2 голосов
/ 26 мая 2019

Вот способ сделать это рекурсивно.

Первая функция генерирует возможные точки вырезки для списка длиной n, создавая подсписки длиной не менее 3.

Второй просто дает подсписки, вырезанные в соответствии с точками вырезания.

Оба являются генераторами, поэтому списки создаются на лету, по одному, если вы используете их в цикле. Это может быть полезно, так как число возможных подсписков может очень сильно возрасти, когда ваши данные станут длиннее. 

def cut_points(n, already_cut=None):
    # The first cut point is at 0 
    if already_cut is None:
        already_cut = [0]

    # We can cut at all places between the last cut plus 3 
    # and the length minus 3, and yield recursively the solutions for each choice
    for i in range(already_cut[-1]+3, n-2):
        cuts = already_cut[:] + [i]
        yield from cut_points(n, cuts)

    # When we tried all cut points and reached the total length, we yield the cut points list 
    yield already_cut[:] + [n]


def all_possible_sublists(data):
    n = len(data)
    for cut in cut_points(n):
        yield [data[cut[i]:cut[i+1]] for i in range(len(cut)-1)]

Некоторые тесты: 

list(all_possible_sublists([0, 1, 2, 3]))
# [[[0, 1, 2, 3]]]

list(all_possible_sublists([0, 1, 2, 3, 4, 5, 6]))
# [[[0, 1, 2], [3, 4, 5, 6]],
#  [[0, 1, 2, 3], [4, 5, 6]],
#  [[0, 1, 2, 3, 4, 5, 6]]]

for sublist in all_possible_sublists([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]):
    print(sublist)
# [[0, 1, 2], [3, 4, 5], [6, 7, 8, 9]]
# [[0, 1, 2], [3, 4, 5, 6], [7, 8, 9]]
# [[0, 1, 2], [3, 4, 5, 6, 7, 8, 9]]
# [[0, 1, 2, 3], [4, 5, 6], [7, 8, 9]]
# [[0, 1, 2, 3], [4, 5, 6, 7, 8, 9]]
# [[0, 1, 2, 3, 4], [5, 6, 7, 8, 9]]
# [[0, 1, 2, 3, 4, 5], [6, 7, 8, 9]]
# [[0, 1, 2, 3, 4, 5, 6], [7, 8, 9]]
# [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]]
...