Finding isomorphic lists in a big list

list

asked 2021-03-01 13:17:03 +0100

klaaa
691 ●4 ●17 ●41

updated 2021-03-01 17:19:02 +0100

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 flag offensive close merge delete

add a comment

answered 2021-03-01 14:03:54 +0100

Max Alekseyev

6488 ●9 ●47 ●153

updated 2021-03-01 14:10:53 +0100

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

edit flag offensive delete link

Comments

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?

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

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

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

Thank you very much. I added in an edit to my answer how I made it with Sage using your suggestion.

klaaa ( 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) ?

klaaa ( 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]]

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

add a comment

Finding isomorphic lists in a big list

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Finding isomorphic lists in a big list edit

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Finding isomorphic lists in a big list