Сравнить все списки в списке списков на основе условий и сгруппировать их по разнице

Question

У меня есть следующий список списков:

a = [[1,2,3,4,5], [4,5,6,7,8], [1,2,3,4], [4,5,6,7,8,9], [2,3,4,5,6,7,8], [6,7,8,9], [5,6,7,8,9], [2,3,4,5,6], [3,4,5,6], [11,12,13,14,15], [13,14,15]]

Представление их с индексом для простоты понимания:

0 [1, 2, 3, 4, 5]
1 [4, 5, 6, 7, 8]
2 [1, 2, 3, 4]
3 [4, 5, 6, 7, 8, 9]
4 [2, 3, 4, 5, 6, 7, 8]
5 [6, 7, 8, 9]
6 [5, 6, 7, 8, 9]
7 [2, 3, 4, 5, 6]
8 [3, 4, 5, 6]
9 [11, 12, 13, 14, 15]
10 [13, 14, 15]

Я ожидаю вывод, который будет списоккортежи, подобные приведенным ниже:

output = [(0,2,1), (3,1,1), (4,7,2), (4,1,2), (6,5,1), (3,5,2), (3,6,1), (7,8,1), (9,10,2)]

For example to explain first item of output i.e, (0,2,1):

0 ---> index of list under comparison with highest length 
2 ---> index of list under comparison with lowest length
1 ---> difference in length of the two lists 0 & 2

Теперь перейдем к проблеме:

У меня есть списки, в которых есть похожие элементы, которые различаются по длине на один и два (или три) в начале или в концесписки.

Я хочу отсортировать, сгруппировать, идентифицировать индекс списков и их различия в виде кортежа.

Я прошел через несколько вопросов, связанных со стековым потоком, но не смог найти аналогичный вопрос.

Я новичок в python, начал с битами следующих кодов и застрял:

a = sorted(a, key = len)

incr = [list(g) for k, g in groupby(a, key=len)]

decr = list(reversed(incr))

ndecr = [i for j in decr for i in j]

for i in range(len(ndecr)-1):
    if len(ndecr[i]) - len(ndecr[i+1]) == 1:
        print(ndecr[i])

for i in range(len(ndecr)-2):
    if len(ndecr[i]) - len(ndecr[i+2]) == 2:
        print(ndecr[i])

for i in ndecr:
    ele = i
    ndecr.remove(i)
    for j in ndecr:
        if ele[:-1] == j:
            print(j)   

for i in ndecr:
    ele = i
    ndecr.remove(i)
    for j in ndecr:
        if ele[:-2] == j:
            print(i)

Пожалуйста, помогите мне с подходом, который я должен использовать для достижения результата.

Answer 1

IIUC, предполагая, что общее количество списков мало, поэтому len (lists) ^ 2 все еще мало, что-то вроде

from itertools import combinations

# sort by length but preserve the index
ax = sorted(enumerate(a), key=lambda x: len(x[1]))

done = []

for (i0, seq0), (i1, seq1) in combinations(ax, 2):
    if seq1[:len(seq0)] == seq0 or seq1[-len(seq0):] == seq0:
       done.append((i1, i0, len(seq1)-len(seq0)))

дает мне

In [117]: sorted(done)
Out[117]: 
[(0, 2, 1),
 (3, 1, 1),
 (3, 5, 2),
 (3, 6, 1),
 (4, 1, 2),
 (4, 7, 2),
 (6, 5, 1),
 (7, 8, 1),
 (9, 10, 2)]

, что соответствуетваш вывод, но для порядка, и для факта, что вы (4, 7, 2) указаны в списке дважды.

seq1[:len(seq0)] == seq0 

является "seq1 начинается с seq0?"условие, и

seq1[-len(seq0):] == seq0

означает "заканчивается ли seq1 на seq0?"состояние.

Answer 2

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

l1 = a[:]

tups = []
for idx, item in enumerate(l1):
    for x, i in enumerate(a):
        if sorted(item[:-1]) == sorted(i):
            tups.append((idx, x, 1))
        elif sorted(item[:-2]) == sorted(i):
            tups.append((idx, x, 2))
        elif sorted(item[1:]) == sorted(i):
            tups.append((idx, x, 1))
        elif sorted(item[2:]) == sorted(i):
            tups.append((idx, x, 2))

print(tups)

[(0, 2, 1), (3, 1, 1), (4, 7, 2), (3, 6, 1), (6, 5, 1), (7, 8, 1), (3, 5, 2), (4, 1, 2), (9, 10, 2)]

Answer 3

РЕДАКТИРОВАТЬ (оригинал ниже):

Теперь, возможно, я вас лучше понимаю (спасибо @ vash_the_stampede за разъясняющий комментарий).Этот подход вкладывает пару циклов, чтобы сравнить каждый список в вашем списке списков и определить, является ли один подмножеством другого.Затем, если сравниваемые списки являются надмножеством / подмножеством, он создает выходной список кортежей, каждый из которых содержит индексы двух сравниваемых списков, упорядоченных по длине в первую очередь вместе с разницей в длине этих сравниваемых списков.

ВАЖНО: этоПодход не сравнивает порядок списка, поэтому он может обеспечить вывод, который вам может не понадобиться, например, [1,2,4,5] является подмножеством [1,2,3,4,5] с разницей длины 1. Или, в зависимости от вашего примера, этот подход выводит дополнительный кортеж при сравнениик вашему примеру вывода, потому что [3,4,5,6], в индексе 8, является подмножеством [2,3,4,5,6,7,8], в индексе 4, с разницей длины 3. Я думаю, что ответ от @ DSM решает эту проблему,так что это, вероятно, ближе к тому, что вам нужно.

Пример вывода из вашего текущего набора данных:

a = [[1,2,3,4,5], [4,5,6,7,8], [1,2,3,4], [4,5,6,7,8,9], [2,3,4,5,6,7,8], [6,7,8,9], [5,6,7,8,9], [2,3,4,5,6], [3,4,5,6], [11,12,13,14,15], [13,14,15]]

output = []
for i in range(len(a)):
    for j in range(i + 1, len(a)):
       if set(a[i]).issubset(a[j]) or set(a[i]).issuperset(a[j]):
           diff = abs(len(a[i]) - len(a[j]))
           if len(a[i]) > len(a[j]):
               output.append((i, j, diff))
           else:
               output.append((j, i, diff))

print(output)

# OUTPUT
# [(0, 2, 1), (3, 1, 1), (4, 1, 2), (3, 5, 2), (3, 6, 1), (4, 7, 2), (4, 8, 3), (6, 5, 1), (7, 8, 1), (9, 10, 2)]

ОРИГИНАЛ:

Если я вас правильно понимаю, вы можете просто вложить пару циклов для сравнения каждого спискав вашем списке списков.Затем создайте выходной список кортежей, каждый из которых содержит индексы двух сравниваемых списков вместе с разницей в длине этих сравниваемых списков.Например:

a = [[1,2,3,4,5], [4,5,6,7,8], [1,2,3,4], [4,5,6,7,8,9], [2,3,4,5,6,7,8], [6,7,8,9], [5,6,7,8,9], [2,3,4,5,6], [3,4,5,6], [11,12,13,14,15], [13,14,15]]

output = []
for i in range(len(a)):
    for j in range(i + 1, len(a)):
       diff = abs(len(a[i]) - len(a[j]))
       output.append((i, j, diff))

print(output)

# OUTPUT
# [(0, 1, 0), (0, 2, 1), (0, 3, 1), (0, 4, 2), (0, 5, 1), (0, 6, 0), (0, 7, 0), (0, 8, 1), (0, 9, 0), (0, 10, 2), (1, 2, 1), (1, 3, 1), (1, 4, 2), (1, 5, 1), (1, 6, 0), (1, 7, 0), (1, 8, 1), (1, 9, 0), (1, 10, 2), (2, 3, 2), (2, 4, 3), (2, 5, 0), (2, 6, 1), (2, 7, 1), (2, 8, 0), (2, 9, 1), (2, 10, 1), (3, 4, 1), (3, 5, 2), (3, 6, 1), (3, 7, 1), (3, 8, 2), (3, 9, 1), (3, 10, 3), (4, 5, 3), (4, 6, 2), (4, 7, 2), (4, 8, 3), (4, 9, 2), (4, 10, 4), (5, 6, 1), (5, 7, 1), (5, 8, 0), (5, 9, 1), (5, 10, 1), (6, 7, 0), (6, 8, 1), (6, 9, 0), (6, 10, 2), (7, 8, 1), (7, 9, 0), (7, 10, 2), (8, 9, 1), (8, 10, 1), (9, 10, 2)]