Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

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

klaaa gravatar image

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) to check with Sage whether the big list W contains two isomorphic lists L_i and L_j?

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) bigger for larger examples) to check with Sage whether the big list W contains two isomorphic lists L_i and L_j?

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

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
about | faq | help | privacy policy | terms of service
Powered by Askbot version 0.7.59