Формирование вложенных в список списков из других списков по определенным правилам?

Рейтинг: 3Ответов: 1Опубликовано: 06.04.2015

Добрый день, есть три списка

allIndex_A = [1, 2, 8, 12, 17, 21, 23, 29]
allIndex_B = [3, 5, 7, 9, 11, 13, 15, 18, 20, 22, 24, 26, 28, 30]
allIndex_C = [4, 6, 10, 14, 16, 19, 25, 27]

нужно из них сделать список со вложенными списками, вот такой:

newList = [[1,3,4], [2,3,4], [8,9,10], [12,13,14], ...]

Первый элемент вложенного списка это первый это первый элемент списка allIndex_A. Второй элемент это первый элемент из списка allIndex_В, значение которого больше значения первого элемента из вложенного списка. Третий элемент это также первый найденный элемент из списка allIndex_С, значение которого больше первого элемента во вложенном списке.

Первый элемент второго вложенного списка это второй элемент из списка allIndex_A. Второй и третий элемент второго вложенного списка находятся по таким же условиям как и в первом вложенном списке. То есть это должен быть первый найденный элемент из списков allIndex_В и allIndex_С, значение которого больше значения первого элемента.

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

python алгоритм список списки
Источник: Stack Overflow на русском

Ответы

▲ 2Принят

Вот решение, основанное на использовании zip(), чтобы транспонировать элементы трёх списков:

#!/usr/bin/env python
from itertools import tee

def gt_first(first, iterable):
    """Yield items from iterable that are greater than corresponding items from
       first.

    first, iterable are sorted.
    """
    it = iter(iterable)
    x = next(it) #NOTE: wrap with try/except StopIteration for pep-479
    for item in first:
        while not (x > item):
            x = next(it)
        yield x

allIndex_A = [1, 2, 8, 12, 17, 21, 23, 29]
allIndex_B = [3, 5, 7, 9, 11, 13, 15, 18, 20, 22, 24, 26, 28, 30]
allIndex_C = [4, 6, 10, 14, 16, 19, 25, 27]

a, ab, ac = tee(allIndex_A, 3)
L = list(map(list, zip(a, gt_first(ab, allIndex_B), gt_first(ac, allIndex_C))))
print(L)

Результат

[[1, 3, 4], [2, 3, 4], [8, 9, 10], [12, 13, 14], [17, 18, 19], [21, 22, 25],
 [23, 24, 25]]

В ответе нет вложенного списка [29, 30, None], так как allIndex_C не имеет элемента большего 29 (можно itertools.zip_longest() вместо zip() использовать, чтобы подставить какое-нибудь значение, вместо игнорирования вложенного списка целиком).

Время исполнения линейное (O(n)). Если входные списки не отсортированы, то их надо отсортировать, тогда время исполнения O(n*log n) (на сортировку).