Как эффективнее найти пары элементов разных списков с одинаковыми значениями и индексами (т.е. a[n][e] == a[m][e]) в списке?
Дополнительные условия
- Важен порядок, либо возможность получить то самое
[e]и его значение (см. Заголовок) - Возможны повторения значений в одном списке
- Вложенные списки не повторяются
- Вложенные списки одной длины, но интересует общий случай, но если для моего случая есть решение эффективнее общего, то тоже интересует
Как я это реализовал
Первый вариант
for lin in range(len(spisok)):
for lin2 in range(len(spisok[(lin+1):])): #<- тот самый срез
for let in range(len(spisok[lin])):
if spisok[lin][let] == spisok[lin2][let]:
#вывод типа spisok[lin],let,spisok[lin2]
Второй вариант
for lin in range(len(spisok)):
for lin2 in range(len(spisok)):
for let in range(len(spisok[lin])):
if spisok[lin][let] == spisok[lin2][let] and lin2 > lin:
#вывод типа spisok[lin],let,spisok[lin2]
Модификация второго для любителей List Comprehension
[[spisok[lin],let,spisok[lin2]] for lin in range(len(spisok)) for lin2 in range(len(spisok)) for let in range(len(spisok[lin])) if (spisok[lin][let] == spisok[lin2][let] and lin2 > lin)]
Результаты
При spisok=[[1,2,3],[2,2,4],[1,3,4]] и выводе через print()
1-ый:
[1, 2, 3] 0 [1, 2, 3]
[1, 2, 3] 1 [1, 2, 3]
[1, 2, 3] 2 [1, 2, 3]
[1, 2, 3] 1 [2, 2, 4]
[2, 2, 4] 1 [1, 2, 3]
2-ый:
[1, 2, 3] 1 [2, 2, 4]
[1, 2, 3] 0 [1, 3, 4]
[2, 2, 4] 2 [1, 3, 4]
Мод. 2:
[[[1, 2, 3], 1, [2, 2, 4]], [[1, 2, 3], 0, [1, 3, 4]], [[2, 2, 4], 2, [1, 3, 4]]]
Возникшие проблемы и саб-вопросы
- Первый делает не понятные мне вещи. Опытным путём я пришёл к выводу, что это из-за среза, который я беру, чтобы не было повтора в рассчётах и в выводе.
- Почему такой вывод у первого варианта и как его привести к моей идее? (см. предыдущий пункт)
- В свою очередь второй и его мод. дают ожидаемый результат, но делают перерасчёты.
- Изначально
spisokчитается из файла, затем над ним проводятся манипуляции, которые его приводят к виду, который подобен тому, который я привёл. Вопрос, как меняется ответ на Заголовок при таком условии?
P.S.
Поначитавшись схожих вопросов у меня возник вопрос оптимизации и эффективности алгоритмов (напоминаю о заголовке), но то что я нашёл либо уже здесь упомянуто, либо не согласуется с условиями, либо сложно в интеграции/понимании.
P.P.S.
Это мой первый вопрос здесь. Простите за структуру или недочёты текста.
UPD1
Дальше то к чему вопрос имеет мало отношения
Я хотел добиться сам результата, но видимо не суждено, поэтому по просьбе раскрываю всю суть задачи.
Есть вот такая схема:
Я хотел сделать программу, которая принимает список ФИО (.txt) и выдаёт людей у которых совпадает задание, типа: 'ФИО1', Номер_задания, 'ФИО2'.
Вольный краткий пересказ кода
Назначаем на чтение файла и преобразование в список пару переменных. Приводим полученное к виду готовому к оцифровке (удаление пробелов, замена больших букв на малые). Оцифровка по правилам с картинки. И теперь идёт поиск ради, которого этот вопрос.
UPD2
Примеры входа, выходов, по просьбе всё того же. (см. комментарии)
Вход файлом .txt:
Романов Ефим Романович
Костин Вячеслав Созонович
Копылов Пантелеймон Анатольевич
Выход 1-го:
Романов Ефим Романович 6 Романов Ефим Романович
Романов Ефим Романович 15 Романов Ефим Романович
Романов Ефим Романович 25 Романов Ефим Романович
Романов Ефим Романович 31 Романов Ефим Романович
Романов Ефим Романович 45 Романов Ефим Романович
Романов Ефим Романович 55 Романов Ефим Романович
Романов Ефим Романович 69 Романов Ефим Романович
Романов Ефим Романович 73 Романов Ефим Романович
Романов Ефим Романович 87 Романов Ефим Романович
Романов Ефим Романович 94 Романов Ефим Романович
Романов Ефим Романович 15 Костин Вячеслав Созонович
Романов Ефим Романович 55 Костин Вячеслав Созонович
Романов Ефим Романович 69 Костин Вячеслав Созонович
Романов Ефим Романович 87 Костин Вячеслав Созонович
Костин Вячеслав Созонович 15 Романов Ефим Романович
Костин Вячеслав Созонович 55 Романов Ефим Романович
Костин Вячеслав Созонович 69 Романов Ефим Романович
Костин Вячеслав Созонович 87 Романов Ефим Романович
Вывод 2-го, т.е. ожидаемый:
Романов Ефим Романович 15 Костин Вячеслав Созонович
Романов Ефим Романович 55 Костин Вячеслав Созонович
Романов Ефим Романович 69 Костин Вячеслав Созонович
Романов Ефим Романович 87 Костин Вячеслав Созонович
Романов Ефим Романович 15 Копылов Пантелеймон Анатольевич
Романов Ефим Романович 55 Копылов Пантелеймон Анатольевич
Романов Ефим Романович 69 Копылов Пантелеймон Анатольевич
Костин Вячеслав Созонович 4 Копылов Пантелеймон Анатольевич
Костин Вячеслав Созонович 15 Копылов Пантелеймон Анатольевич
Костин Вячеслав Созонович 44 Копылов Пантелеймон Анатольевич
Костин Вячеслав Созонович 55 Копылов Пантелеймон Анатольевич
Костин Вячеслав Созонович 69 Копылов Пантелеймон Анатольевич
P.S. вывод основан на готовой программе по задаче из UPD1
Ответы (2 шт):
Отвечу на ту часть вопроса, которую я понял:
как имея указанную в вопросе таблицу получать номера заданий для указанных ФИО?
Я бы использовал модули Numpy & Pandas:
import pandas as pd # pip install pandas
import numpy as np # pip install numpy
Сначала надо создать таблицу поиска - для максимально эффективного и быстрого поиска я бы переделел эту таблицу таким образом, чтобы в первом столбце была только одна буква алфавита, а строки бы повторялись.
Пример для первых двух строк оригинальной таблицы - мы получим 6 строк в модифицированной таблице:
1 2 3 4 5 6 7 8 9 10
а 1 11 21 31 41 51 61 71 81 91
б 1 11 21 31 41 51 61 71 81 91
й 1 11 21 31 41 51 61 71 81 91
д 2 12 22 32 42 52 62 72 82 92
ж 2 12 22 32 42 52 62 72 82 92
ы 2 12 22 32 42 52 62 72 82 92
Создаем таблицу поиска:
idx_letters = ["абй", "джы", "зеъ", "икьл", "мно", "прт", "уфчс", "хцг", "шщв", "эюя"]
first_row = np.arange(1, 101, 10)
data = []
for ii, idx in enumerate(idx_letters):
for j in range(len(idx)):
data.append(first_row + ii)
cols = np.arange(1, 11)
df = pd.DataFrame(data, columns=cols, index=list("".join(idx_letters)))
Получилось:
In [71]: df
Out[71]:
1 2 3 4 5 6 7 8 9 10
а 1 11 21 31 41 51 61 71 81 91
б 1 11 21 31 41 51 61 71 81 91
й 1 11 21 31 41 51 61 71 81 91
д 2 12 22 32 42 52 62 72 82 92
ж 2 12 22 32 42 52 62 72 82 92
ы 2 12 22 32 42 52 62 72 82 92
з 3 13 23 33 43 53 63 73 83 93
е 3 13 23 33 43 53 63 73 83 93
ъ 3 13 23 33 43 53 63 73 83 93
и 4 14 24 34 44 54 64 74 84 94
к 4 14 24 34 44 54 64 74 84 94
ь 4 14 24 34 44 54 64 74 84 94
л 4 14 24 34 44 54 64 74 84 94
м 5 15 25 35 45 55 65 75 85 95
н 5 15 25 35 45 55 65 75 85 95
о 5 15 25 35 45 55 65 75 85 95
п 6 16 26 36 46 56 66 76 86 96
р 6 16 26 36 46 56 66 76 86 96
т 6 16 26 36 46 56 66 76 86 96
у 7 17 27 37 47 57 67 77 87 97
ф 7 17 27 37 47 57 67 77 87 97
ч 7 17 27 37 47 57 67 77 87 97
с 7 17 27 37 47 57 67 77 87 97
х 8 18 28 38 48 58 68 78 88 98
ц 8 18 28 38 48 58 68 78 88 98
г 8 18 28 38 48 58 68 78 88 98
ш 9 19 29 39 49 59 69 79 89 99
щ 9 19 29 39 49 59 69 79 89 99
в 9 19 29 39 49 59 69 79 89 99
э 10 20 30 40 50 60 70 80 90 100
ю 10 20 30 40 50 60 70 80 90 100
я 10 20 30 40 50 60 70 80 90 100
Теперь напишем вспомогательную функцию для преобразования ФИО в список букв:
def name_to_index(name, max_len=10):
return list(name.lower().replace(" ", "")[:max_len])
Тестируем:
res = {}
name = "Панин Иван Сергеевич"
res[name] = df.lookup(name_to_index(name), cols)
name = "Иванов Петр Сидорович"
res[name] = df.lookup(name_to_index(name), cols)
Результат:
In [79]: res
Out[79]:
{'Панин Иван Сергеевич': array([ 6, 11, 25, 34, 45, 54, 69, 71, 85, 97], dtype=int64),
'Иванов Петр Сидорович': array([ 4, 19, 21, 35, 45, 59, 66, 73, 86, 96], dtype=int64)}
Для дальнейшей обработки можно собрать результаты в один DataFrame:
r = pd.DataFrame(res, index=cols).T
In [92]: r
Out[92]:
1 2 3 4 5 6 7 8 9 10
Панин Иван Сергеевич 6 11 25 34 45 54 69 71 85 97
Иванов Петр Сидорович 4 19 21 35 45 59 66 73 86 96
Чтобы не перегружать первый ответ, показываю в этом ответе как эффективно искать дубликаты, используя Pandas:
сначала создаем DataFrame с выпавшими номерами заданий, используя наработки из другого ответа:
names = ["Романов Ефим Романович", "Костин Вячеслав Созонович", "Копылов Пантелеймон Анатольевич"]
res = {name: df.lookup(name_to_index(name), cols) for name in names}
r = pd.DataFrame(res, index=cols).T.rename_axis("name").rename_axis("col", axis=1)
получили:
In [123]: r
Out[123]:
col 1 2 3 4 5 6 7 8 9 10
name
Романов Ефим Романович 6 15 25 31 45 55 69 73 87 94
Костин Вячеслав Созонович 4 15 27 36 44 55 69 80 87 93
Копылов Пантелеймон Анатольевич 4 15 26 32 44 55 69 76 81 95
поиск дубликатов (одной строкой):
dupes = (r
.stack()
.reset_index(name="task_no")
.groupby(["col", "task_no"])
["name"]
.apply(list)
.reset_index())
результат:
In [132]: dupes.loc[dupes["name"].str.len() > 1]
Out[132]:
col task_no name
0 1 4 [Костин Вячеслав Созонович, Копылов Пантелеймон Анатольевич]
2 2 15 [Романов Ефим Романович, Костин Вячеслав Созонович, Копылов Пантелеймон Анатольевич]
9 5 44 [Костин Вячеслав Созонович, Копылов Пантелеймон Анатольевич]
11 6 55 [Романов Ефим Романович, Костин Вячеслав Созонович, Копылов Пантелеймон Анатольевич]
12 7 69 [Романов Ефим Романович, Костин Вячеслав Созонович, Копылов Пантелеймон Анатольевич]
17 9 87 [Романов Ефим Романович, Костин Вячеслав Созонович]