Блог

У меня есть список списков, где каждый подсписок состоит из четырех элементов, в таком формате:

 ll = [["dog", "cat", "mouse", "pig"],
      ["pidgeon", "goose", "rat", "frog"],
      ["bird", "dog", "mouse", "pig"]
      ["wolf", "cat", "whale", "rhino"]
      ...
      ["chameleon", "bat", "zebra", "lion"]
 

Мне нужно найти самую большую комбинацию внутренних списков, в которых ни одна строка никогда не повторяется. Мой выходной список списков должен быть в том же формате, ll что и , поэтому это должен быть список списков, где каждый подсписок состоит из четырех строк. Таким образом, мой желаемый результат исключил ["dog", "cat", "mouse", "pig"] бы (первый подсписок), поскольку он разделяет элементы «собака», «мышь» и «свинья» с ["bird", "dog", "mouse", "pig"] (третий подсписок) и элемент «кошка» с ["wolf", "cat", "whale", "rhino"] (четвертый подсписок). Важно отметить, что мой желаемый результат не исключал бы третий и четвертый подсписок, хотя это была бы комбинация внутренних списков, в которых строка не повторяется, потому что это была бы не самая большая комбинация.

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

Вариант 1

 output = []
for comb in itertools.combinations(ll, 40):
    merged = set(itertools.chain.from_iterable(comb)) # flatten nested list
    if len(merged) == 160: # 40*4 = 160 --> no item is repeated
        output.append(comb)
 

Недостатками этого параметра являются то, что (а) он вообще не эффективен с точки зрения вычислений, и (б) я бы априори указывал количество внутренних списков, к которым я стремлюсь, вместо того, чтобы максимизировать его.

Вариант 2

 items = set()
unique = []
for quartet in ll:
    if set(quartet).isdisjoint(items):
        unique.append(quartet)
        for word in quartet:
            items.add(word)
print(unique)
 

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

Вы можете использовать свой 2-й метод с небольшой предварительной обработкой и жадным подходом.

• Сначала вы можете просмотреть все элементы ll и сохранить все уникальные элементы и их количество в dict.

 {
  "dog": 1,
  "cat": 2,
  ...
}
 

• Затем для каждого списка в ll вы можете узнать, сколько элементов перекрывается (вы можете проверить, больше ли значение этого элемента в dict, чем 1) и сохранить это количество.
• Теперь вы можете сортировать ll на основе количества перекрытий с помощью sorted() функции.
• И теперь вы можете запустить свой 2-й метод для отсортированного ll