3

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

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 выше. Начал изучать программирование недавно, многих вещей еще не знаю. Буду благодарен, если кто-то объяснит как сделать то, что мне нужно или хотя-бы даст ссылку где можно почитать на тему вопроса.

1
  • А списки гарантировано отсортированные?
    – atwice
    6 апр 2015 в 17:09

3 ответа 3

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) (на сортировку).

0

Пример алгоритма для двух списков. Его можно расширить и до трёх:

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]

def mylist(il1, il2):
    for i in il1:
        for j in il2:
            if j>i:
                yield [i,j]
                break

print list(mylist(allIndex_A, allIndex_B))
# [[1, 3], [2, 3], [8, 9], [12, 13], [17, 18], [21, 22], [23, 24], [29, 30]]

Проблемы в примере:

  1. Используется два списка вместо трёх;
  2. Трудоёмкость квадратичная вместо линейной или псевдолинейной.

В случае расширения для трёх списков, break должен выходить из двух вложенных циклов. Для этого, возможно, придётся использовать флаговую переменную.

0

Вот что удалось набросать:

def merge_lists(l1, l2):
    for item in l1:
        for item2 in l2:
            if type(item) is int:
                if item < item2:
                    yield [item, item2]
                    break
            else:
                if item[-1] < item2:
                    x = list(item)
                    x.append(item2)
                    yield x
                    break

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


list(merge_lists(l1, l2))

Вывод:
[[1, 3], [2, 3], [8, 9], [12, 13], [17, 18], [21, 22], [23, 24], [29, 30]]

list(merge_lists(merge_lists(l1, l2), l3))

Вывод:
[[1, 3, 4],
 [2, 3, 4],
 [8, 9, 10],
 [12, 13, 14],
 [17, 18, 19],
 [21, 22, 25],
 [23, 24, 25]]

Вариант 2, на 3 списка:

def merge_lists(l1, l2, l3):
    for item1 in l1:
        for item2 in l2:
            if item2 > item1:
                for item3 in l3:
                    if item3 > item2:
                        yield [item1, item2, item3]
                        break
                break

list(merge_lists(l1, l2, l3))

Вывод:

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.