Мне нужно создать кортежи из декартового произведения из нескольких списков по несколько десятков элементов в каждом (хотя длина списков может быть разной), а затем снова отфильтровать их, поэтому у меня останутся только кортежи, отличные друг от друга по крайней мере k мест. Это имеет время выполнения O(10^n). Я пытался в течение нескольких часов найти подход, который был бы более сложным по времени. Возможно, есть какое-то умное числовое решение.
Например, если все списки имеют ровно 10 элементов, вы можете сгенерировать возможный набор всех кортежей, которые отличаются в двух местах, сначала преобразовав кортежи индексов списка в числа и затем многократно вычитая 11. Например, если у нас есть 3 списка, наборы индексов списка варьируются от (0,0,0) до (9,9,9). С помощью этих кортежей вы можете затем индексировать свои исходные списки, чтобы получить фактические кортежи декартового произведения, которые вы хотите построить.
Таким образом, различные кортежи f(999 - 11 * 1) = (8,8,8), f(999 - 11 * 2) = (8,7,6), f(999 - 11 * 3) = (8,6,5) и так далее. Это должно работать для любой базы, если все списки имеют одинаковое количество элементов.
Но когда у нас есть списки, подобные ['a','b','c'], ['a','b'], ['a','b','c','d'], действительные числа не охватывают весь диапазон базы 4 (самый длинный список в этом примере): 223 не является допустимым номером кодировки индексов, поскольку индекс 2 находится вне диапазона для среднего списка.
Итак, кто-нибудь знает хитрый прием для этого?
Я делаю это в Python, но язык на самом деле не имеет значения.