Check if two nested lists are equivalent upon substitution

Question

For some context, I'm trying to enumerate the number of unique situations that can occur when calculating the Banzhaf power indices for four players, when there is no dictator and there are either four or five winning coalitions.

I am using the following code to generate a set of lists that I want to iterate over.

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

However, two lists in this set shouldn't be considered unique if they are equivalent under remapping.

Using the following list as an example:

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

If each element 2 is renamed to 3 and vice-versa, we would get:

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

The order in each sub-list is unimportant, and the order of the sub-lists is also un-important. Thus, the swapped list can be rewritten as:

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

There are 4 values, so there are P(4,4)=24 possible remappings that could occur (including the trivial mapping).

Is there any way to check this easily? Or, even better, is there are way to avoid generating these lists to begin with?

I'm not even sure how I would go about transforming the first list into the second list (but could brute force it from there). Also, I'm not restricted to data type (to a certain extent) and using frozenset would be fine.

Edit: The solution offered by tobias_k answers the "checking" question but, as noted in the comments, I think I have the wrong approach to this problem.

Answer 1

This is probably no complete solution yet, but it might show you a direction to investigate further.

You could map each element to some characteristics concerning the "topology", how it is "connected" with other elements. You have to be careful not to take the ordering in the sets into account, or -- obviously -- the element itself. You could, for example, consider how often the element appears, in what sized groups it appears, and something like this. Combine those metrics to a key function, sort the elements by that key, and assign them new names in that order.

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

This maps your two example lists to the same "normalized" list:

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

When applied to all the lists, it gets the count down from 330 to 36. I don't know if this is minimal, but it looks like a good start.

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