# Finding isomorphic lists in a big list

I have a big list W of lists L_i obtained in GAP that looks as follows for example:

[ [ [ 0, [ 6 ] ], [ 2, [ 0, 4 ] ], [ 2, [ 0, 4 ] ], [ 2, [ 0, 4 ] ],
[ 2, [ 0, 4 ] ], [ 2, [ 0, 0, 11 ] ] ],
[ [ 0, [ 6 ] ], [ 2, [ 0, 3 ] ], [ 2, [ 0, 3 ] ], [ 2, [ 0, 3 ] ],
[ 2, [ 0, 0, 5 ] ], [ 1, [ 0, 1 ] ] ],
[ [ 0, [ 6 ] ], [ 2, [ 0, 3 ] ], [ 2, [ 0, 3 ] ], [ 2, [ 0, 0, 2 ] ],
[ 1, [ 0, 4 ] ], [ 2, [ 0, 0, 3 ] ] ],
[ [ 0, [ 6 ] ], [ 1, [ 0, 3 ] ], [ 1, [ 0, 3 ] ], [ 2, [ 0, 1 ] ],
[ 2, [ 0, 1 ] ], [ 2, [ 0, 0, 3 ] ] ],
[ [ 0, [ 6 ] ], [ 2, [ 0, 4 ] ], [ 1, [ 0, 2 ] ], [ 2, [ 0, 2 ] ],
[ 2, [ 0, 2 ] ], [ 2, [ 0, 0, 5 ] ] ],
[ [ 0, [ 6 ] ], [ 1, [ 0, 1 ] ], [ 2, [ 0, 3 ] ], [ 2, [ 0, 3 ] ],
[ 2, [ 0, 3 ] ], [ 2, [ 0, 0, 5 ] ] ],
[ [ 0, [ 6 ] ], [ 2, [ 0, 4 ] ], [ 2, [ 0, 4 ] ], [ 2, [ 0, 3 ] ],
[ 2, [ 0, 1 ] ], [ 2, [ 0, 0, 7 ] ] ],
[ [ 0, [ 6 ] ], [ 1, [ 0, 2 ] ], [ 1, [ 0, 2 ] ], [ 1, [ 0, 3 ] ],
[ 2, [ 0, 0, 1 ] ], [ 2, [ 0, 0, 1 ] ] ],
[ [ 0, [ 6 ] ], [ 1, [ 0, 3 ] ], [ 1, [ 0, 2 ] ], [ 2, [ 0, 1 ] ],
[ 2, [ 0, 0, 2 ] ], [ 1, [ 0, 1 ] ] ],
[ [ 0, [ 6 ] ], [ 1, [ 0, 4 ] ], [ 1, [ 0, 2 ] ], [ 2, [ 0, 1 ] ],
[ 2, [ 0, 1 ] ], [ 2, [ 0, 0, 3 ] ] ],
[ [ 0, [ 6 ] ], [ 1, [ 0, 2 ] ], [ 1, [ 0, 2 ] ], [ 2, [ 0, 0, 1 ] ],
[ 1, [ 0, 1 ] ], [ 1, [ 0, 1 ] ] ],
[ [ 0, [ 6 ] ], [ 1, [ 0, 1 ] ], [ 1, [ 0, 2 ] ], [ 1, [ 0, 2 ] ],
[ 2, [ 0, 0, 1 ] ], [ 1, [ 0, 1 ] ] ],
[ [ 0, [ 6 ] ], [ 1, [ 0, 1 ] ], [ 1, [ 0, 1 ] ], [ 1, [ 0, 1 ] ],
[ 1, [ 0, 1 ] ], [ 1, [ 0, 1 ] ] ],
[ [ 0, [ 6 ] ], [ 1, [ 0, 1 ] ], [ 1, [ 0, 1 ] ], [ 1, [ 0, 2 ] ],
[ 1, [ 0, 2 ] ], [ 2, [ 0, 0, 1 ] ] ],
[ [ 0, [ 6 ] ], [ 1, [ 0, 1 ] ], [ 1, [ 0, 3 ] ], [ 1, [ 0, 2 ] ],
[ 2, [ 0, 1 ] ], [ 2, [ 0, 0, 2 ] ] ] ]


So an entry L_i of this list W is a list that looks for example as follows:

[ [ 0, [ 6 ] ], [ 1, [ 0, 1 ] ], [ 1, [ 0, 3 ] ], [ 1, [ 0, 2 ] ],
[ 2, [ 0, 1 ] ], [ 2, [ 0, 0, 2 ] ] ]


An element of this list L_i is again a list that looks like [ 1, [ 0, 3 ] ] for example.

Now two lists L_i and L_j are said to be isomorphic if they contain the same elements up to a permutation of entries.

My question is whether there is a quick method (the big list W might be alot bigger for larger examples) to check with Sage whether the big list W contains two isomorphic lists L_i and L_j?

edit: Using the suggestion of Max Alekseyev, here is the code how to do it with Sage in that example:

L=[ [ [ 0, [ 6 ] ], [ 2, [ 0, 4 ] ], [ 2, [ 0, 4 ] ], [ 2, [ 0, 4 ] ],
[ 2, [ 0, 4 ] ], [ 2, [ 0, 0, 11 ] ] ],
[ [ 0, [ 6 ] ], [ 2, [ 0, 3 ] ], [ 2, [ 0, 3 ] ], [ 2, [ 0, 3 ] ],
[ 2, [ 0, 0, 5 ] ], [ 1, [ 0, 1 ] ] ],
[ [ 0, [ 6 ] ], [ 2, [ 0, 3 ] ], [ 2, [ 0, 3 ] ], [ 2, [ 0, 0, 2 ] ],
[ 1, [ 0, 4 ] ], [ 2, [ 0, 0, 3 ] ] ],
[ [ 0, [ 6 ] ], [ 1, [ 0, 3 ] ], [ 1, [ 0, 3 ] ], [ 2, [ 0, 1 ] ],
[ 2, [ 0, 1 ] ], [ 2, [ 0, 0, 3 ] ] ],
[ [ 0, [ 6 ] ], [ 2, [ 0, 4 ] ], [ 1, [ 0, 2 ] ], [ 2, [ 0, 2 ] ],
[ 2, [ 0, 2 ] ], [ 2, [ 0, 0, 5 ] ] ],
[ [ 0, [ 6 ] ], [ 1, [ 0, 1 ] ], [ 2, [ 0, 3 ] ], [ 2, [ 0, 3 ] ],
[ 2, [ 0, 3 ] ], [ 2, [ 0, 0, 5 ] ] ],
[ [ 0, [ 6 ] ], [ 2, [ 0, 4 ] ], [ 2, [ 0, 4 ] ], [ 2, [ 0, 3 ] ],
[ 2, [ 0, 1 ] ], [ 2, [ 0, 0, 7 ] ] ],
[ [ 0, [ 6 ] ], [ 1, [ 0, 2 ] ], [ 1, [ 0, 2 ] ], [ 1, [ 0, 3 ] ],
[ 2, [ 0, 0, 1 ] ], [ 2, [ 0, 0, 1 ] ] ],
[ [ 0, [ 6 ] ], [ 1, [ 0, 3 ] ], [ 1, [ 0, 2 ] ], [ 2, [ 0, 1 ] ],
[ 2, [ 0, 0, 2 ] ], [ 1, [ 0, 1 ] ] ],
[ [ 0, [ 6 ] ], [ 1, [ 0, 4 ] ], [ 1, [ 0, 2 ] ], [ 2, [ 0, 1 ] ],
[ 2, [ 0, 1 ] ], [ 2, [ 0, 0, 3 ] ] ],
[ [ 0, [ 6 ] ], [ 1, [ 0, 2 ] ], [ 1, [ 0, 2 ] ], [ 2, [ 0, 0, 1 ] ],
[ 1, [ 0, 1 ] ], [ 1, [ 0, 1 ] ] ],
[ [ 0, [ 6 ] ], [ 1, [ 0, 1 ] ], [ 1, [ 0, 2 ] ], [ 1, [ 0, 2 ] ],
[ 2, [ 0, 0, 1 ] ], [ 1, [ 0, 1 ] ] ],
[ [ 0, [ 6 ] ], [ 1, [ 0, 1 ] ], [ 1, [ 0, 1 ] ], [ 1, [ 0, 1 ] ],
[ 1, [ 0, 1 ] ], [ 1, [ 0, 1 ] ] ],
[ [ 0, [ 6 ] ], [ 1, [ 0, 1 ] ], [ 1, [ 0, 1 ] ], [ 1, [ 0, 2 ] ],
[ 1, [ 0, 2 ] ], [ 2, [ 0, 0, 1 ] ] ],
[ [ 0, [ 6 ] ], [ 1, [ 0, 1 ] ], [ 1, [ 0, 3 ] ], [ 1, [ 0, 2 ] ],
[ 2, [ 0, 1 ] ], [ 2, [ 0, 0, 2 ] ] ] ]
n=len(L)
U=[]
for i in [0..n-1]:
for j in [0..n-1]:
U.append([[i,j],sorted(L[i])==sorted(L[j])])


display(U) display(L[1]) display(L[5])

edit retag close merge delete

Sort by » oldest newest most voted

You can compare sorted(L_i) == sorted(L_j) to check if two lisrs are isomorphic.

Or, convert lists to tuples, like in this answer, and compare set(L_i) == set(L_j).

more

Thank you, I will try that. But the lists L_i might have the same elements several times, so one should have equality of multisets rather than just set, right?

( 2021-03-01 14:06:27 +0100 )edit

Yes, use multisets or compare sorted lists -- see updated answer.

( 2021-03-01 14:17:25 +0100 )edit

( 2021-03-01 17:16:05 +0100 )edit

Another question: Is there a command to obtain all the lists L_i in W up to equivalence (and their number up to equivalence) where we define L_i and L_j to be equivalent if sorted(L_i) == sorted(L_j) ?

( 2021-03-01 17:36:11 +0100 )edit

You can create a list uW of unique lists from W like this:

sW = sorted([sorted(L) for L in W])
uW = [sW[0]] + [sW[i] for i in range(1,len(sW)) if sW[i]!=sW[i-1]]

( 2021-03-01 18:51:04 +0100 )edit