c++ - Algorithm to find isomorphic set of permutations -

i have array of set of permutations, , want remove isomorphic permutations.

we have s sets of permutations, each set contain k permutations, , each permutation represented , array of n elements. i'm saving array int pset[s][k][n], s, k , n fixed, , n larger k.

two sets of permutations, a , b, isomorphic, if there exists permutation p, converts elements a b (for example, if a element of set a, p(a) element of set b). in case can p makes a , b isomorphic.

my current algorithm is:

1. we choose pairs s1 = pset[i] , s2 = pset[j], such i < j
2. each element choosen sets (s1 , s2) numered 1 k. means each element can represented s1[i] or s2[i], 0 < < k+1
3. for every permutation t of k elements, following:
   • find permutation r, such r(s1[1]) = s2[1]
   • check if r permutation make s1 , t(s2) isomorphic, t(s2) rearrangement of elements (permutations) of set s2, check if r(s1[i]) = s2[t[i]], 0 < < k+1
   • if not, go next permutation t.

this algorithms works slow: o(s^2) first step, o(k!) loop through each permutation t, o(n^2) find r, , o(k*n) check if r permutation makes s1 , s2 isomorphic - o(s^2 * k! * n^2).

question: can make faster?

there simple solution this: transposition.

if 2 sets isomorphic, means one-to-one mapping exists, set of numbers @ index i in set s1 equals set of numbers @ index k in set s2. conjecture no 2 non-isomorphic sets have property.

(1) jean logeart's example:

0: [[1,2,3],[3,2,1]] 1: [[2,3,1],[1,3,2]] 2: [[1,2,3],[2,3,1]] 3: [[3,2,1],[1,2,3]]  perform 1 pass:  transpose, o(n): 0: [[1,3],[2,2],[3,1]]  sort both in , between groups, o(something log something): 0: [[1,3],[1,3],[2,2]]  hash: "131322" -> 0  ... "121233" -> 1 "121323" -> 2 "131322" -> hashed.  0 , 3 isomorphic. 

(2) vsoftco's counter-example in comment jean logeart's answer:

a = [ [0, 1, 2], [2, 0, 1] ] b = [ [1, 0, 2], [0, 2, 1] ]  "010212" -> "010212" -> hashed.  , b isomorphic. 

you can turn each set transposed-sorted string or hash or whatever compressed object linear-time comparison. note algorithm considers 3 sets a, b , c isomorphic if 1 p converts a b , p converts a c. clearly, in case, there ps convert 1 of these 3 sets other, since doing moving each i in 1 set specific k in other. if, stated, goal "remove isomorphic permutations," still list of sets remove.

explanation:

assume along our sorted hash, kept record of permutation each i came from. vsoftco's counter-example:

010212  // hash , b 100110  // origin permutation, set 100110  // origin permutation, set b 

in order confirm isomorphism, need show i's grouped in each index first set moved some index in second set, index not matter. sorting groups of i's not invalidate solution, rather serves confirm movement/permutation between sets.

now definition, each number in hash and each number in each group in hash represented in origin permutation 1 time each set. choose arrange numbers in each group of i's in hash, guaranteed each number in group representing different permutation in set; , moment theoretically assign number, guaranteed "reserved" permutation , index only. given number, 2, in 2 hashes, guaranteed comes 1 index , permutation in set a, , in second hash corresponds 1 index , permutation in set b. need show - number in 1 index each permutation in 1 set (a group of distinct i's) went one index only in other set (a group of distinct k's). permutation , index number belongs irrelevant.

remember set s2, isomorphic set s1, can derived s1 using 1 permutation function or various combinations of different permutation functions applied s1's members. sorting, or reordering, of our numbers , groups represents permutation choosing assign solution isomorphism rather actual assignment of number came index , permutation. here vsoftco's counter-example again, time add origin indexes of our hashes:

110022 // origin index set 001122 // origin index set b 

therefore our permutation, solution isomorphism, is:

or, in order:

(notice in jean logeart's example there more 1 solution isomorphism.)