Compruebe si dos listas anidadas son equivalentes en la sustitución

En algún contexto, estoy tratando de enumerar la cantidad de situaciones únicas que pueden ocurrir al calcular los índices de poder de Banzhaf para cuatro jugadores, cuando no hay un dictador y hay cuatro o cinco coaliciones ganadoras.

Estoy usando el siguiente código para generar un conjunto de listas sobre las que quiero iterar.

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]) 

Sin embargo, dos listas en este conjunto no deben considerarse únicas si son equivalentes en la reasignación.

Usando la siguiente lista como ejemplo:

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

Si cada elemento 2 cambia su nombre a 3 y viceversa, obtendríamos:

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

El orden en cada sub-lista no es importante, y el orden de las sub-listas tampoco es importante. Por lo tanto, la lista intercambiada se puede reescribir como:

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

Hay 4 valores, por lo que hay P (4,4) = 24 posibles remoces que podrían ocurrir (incluyendo el mapeo trivial).

¿Hay alguna manera de comprobar esto fácilmente? O, mejor aún, ¿hay alguna forma de evitar generar estas listas para empezar?

Ni siquiera estoy seguro de cómo haría para transformar la primera lista en la segunda lista (pero podría forzarla a partir de ahí). Además, no estoy restringido al tipo de datos (hasta cierto punto) y el uso de frozenset estaría bien.

Edit: La solución ofrecida por tobias_k responde a la pregunta de “comprobación” pero, como se señaló en los comentarios, creo que tengo un enfoque incorrecto para este problema.

Probablemente esta no sea una solución completa todavía, pero podría mostrarle una dirección para investigar más a fondo.

Puede asignar cada elemento a algunas características relacionadas con la “topología”, cómo se “conecta” con otros elementos. Debe tener cuidado de no tener en cuenta el orden en los conjuntos o, obviamente, el elemento en sí. Por ejemplo, podría considerar la frecuencia con la que aparece el elemento, en qué grupos de tamaño aparece y algo así. Combine esas métricas con una función clave, ordene los elementos por esa clave y asígnele nuevos nombres en ese orden.

 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)) 

Esto asigna sus dos listas de ejemplo a la misma lista “normalizada”:

 >>> 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)) 

Cuando se aplica a todas las listas, la cuenta regresiva se reduce de 330 a 36. No sé si esto es mínimo, pero parece un buen comienzo.

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