Проверьте, являются ли два вложенных списка эквивалентными при подстановке

Question

В каком-то контексте я пытаюсь перечислить число уникальных ситуаций, которые могут возникнуть при вычислении Banzhaf power indices для четырех игроков, когда нет диктатора, и есть четыре или пять коалиций.

Я использую следующий код для создания набора списков, которые я хочу перебрать.

from itertools import chain, combinations 

def powerset(iterable): 
    s = list(iterable) 
    return chain.from_iterable(map(list, combinations(s, r)) for r in range(2, len(s)+1)) 

def superpowerset(iterable): 
    s = powerset(iterable) 
    return chain.from_iterable(map(list, combinations(s, r)) for r in range(4, 6)) 

set_of_lists = superpowerset([1,2,3,4]) 

Однако два списка в этом наборе не должны считаться уникальными, если они эквивалентны при переназначении.

Используя следующий список в качестве примера:

[[1, 2], [1, 3], [2, 3], [1, 2, 4]] 

Если каждый элемент 2 переименовывается в 3 и наоборот, мы получим:

[[1, 3], [1, 2], [3, 2], [1, 3, 4]] 

порядок, в каждом подсписком не имеет значения, а порядок подписок также не важен. Таким образом, места список может быть переписан как:

[[1, 2], [1, 3], [2, 3], [1, 3, 4]] 

Есть 4 значения, так что есть P (4,4) = 24 возможных remappings, которые могут возникнуть (в том числе тривиального отображения).

Есть ли способ проверить это легко? Или, что еще лучше, есть ли способ избежать создания этих списков?

Я даже не уверен, как бы я преобразовал первый список во второй список (но мог бы грубо заставить его оттуда). Кроме того, я не ограничен типом данных (в определенной степени), и использование frozenset будет в порядке.

Редактировать: Решение, предлагаемое tobias_k, отвечает на вопрос «проверка», но, как отмечается в комментариях, я думаю, что у меня неправильный подход к этой проблеме.

Answer 1

Возможно, это еще не окончательное решение, но оно может показать вам направление дальнейшего расследования.

Вы можете сопоставить каждый элемент с некоторыми характеристиками относительно «топологии», как он «связан» с другими элементами. Вы должны быть осторожны, чтобы не учитывать порядок в наборах, или, очевидно, сам элемент. Вы могли бы, например, рассмотреть, как часто появляется элемент, в каких размерах групп он появляется, и что-то вроде этого. Объедините эти показатели с ключевой функцией, отсортируйте элементы по этому ключу и назначьте им новые имена в этом порядке.

def normalize(lists): 
    items = set(x for y in lists for x in y) 
    counter = itertools.count() 
    sorter = lambda x: sorted(len(y) for y in lists if x in y) 
    mapping = {k: next(counter) for k in sorted(items, key=sorter)} 
    return tuple(sorted(tuple(sorted(mapping[x] for x in y)) for y in lists)) 

Это отображает ваши два примера списки к тому же «нормализованной» список:

>>> normalize([[1, 2], [1, 3], [2, 3], [1, 2, 4]]) 
((0, 1), (0, 2), (1, 2), (1, 2, 3)) 
>>> normalize([[1, 3], [1, 2], [3, 2], [1, 3, 4]]) 
((0, 1), (0, 2), (1, 2), (1, 2, 3)) 

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

>>> normalized = set(map(normalize, set_of_lists)) 
>>> len(normalized) 
36