Algorithm to find isomorphic set of permutations

Question

I have an array of set of permutations, and I want to remove isomorphic permutations.

We have S sets of permutations, where each set contain K permutations, and each permutation is represented as and array of N elements. I'm currently saving it as an array int pset[S][K][N], where S, K and N are fixed, and N is larger than K.

Two sets of permutations, A and B, are isomorphic, if there exists a permutation P, that converts elements from A to B (for example, if a is an element of set A, then P(a) is an element of set B). In this case we can say that P makes A and B isomorphic.

My current algorithm is:

1. We choose all pairs s1 = pset[i] and s2 = pset[j], such that i < j
2. Each element from choosen sets (s1 and s2) are numered from 1 to K. That means that each element can be represented as s1[i] or s2[i], where 0 < i < K+1
3. For every permutation T of K elements, we do the following:
   • Find the permutation R, such that R(s1[1]) = s2[1]
   • Check if R is a permutation that make s1 and T(s2) isomorphic, where T(s2) is a rearrangement of the elements (permutations) of the set s2, so basically we just check if R(s1[i]) = s2[T[i]], where 0 < i < K+1
   • If not, then we go to the next permutation T.

This algorithms works really slow: O(S^2) for the first step, O(K!) to loop through each permutation T, O(N^2) to find the R, and O(K*N) to check if the R is the permutation that makes s1 and s2 isomorphic - so it is O(S^2 * K! * N^2).

Question: Can we make it faster?

Answer 1

You can sort and compare:

// 1 - sort each set of permutation
for i = 0 to S-1
    sort(pset[i])
// 2 - sort the array of permutations itself
sort(pset)
// 3 - compare
for i = 1 to S-1 {
    if(areEqual(pset[i], pset[i-1]))
        // pset[i] and pset[i-1] are isomorphic
}

A concrete 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]]

After 1:

0: [[1,2,3],[3,2,1]]
1: [[1,3,2],[2,3,1]] // order changed
2: [[1,2,3],[2,3,1]]
3: [[1,2,3],[3,2,1]] // order changed

After 2:

2: [[1,2,3],[2,3,1]]
0: [[1,2,3],[3,2,1]]
3: [[1,2,3],[3,2,1]] 
1: [[1,3,2],[2,3,1]]

After 3:

(2, 0) not isomorphic 
(0, 3) isomorphic
(3, 1) not isomorphic

What about the complexity?

• 1 is O(S * (K * N) * log(K * N))
• 2 is O(S * K * N * log(S * K * N))
• 3 is O(S * K * N)

So the overall complexity is O(S * K * N log(S * K * N))

Answer 2

There is a very simple solution for this: transposition.

If two sets are isomorphic, it means a one-to-one mapping exists, where the set of all the numbers at index i in set S1 equals the set of all the numbers at some index k in set S2. My conjecture is that no two non-isomorphic sets have this 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 ONE pass:

Transpose, O(n):
0: [[1,3],[2,2],[3,1]]

Sort both in and between groups, O(something log something):
0: [[1,3],[1,3],[2,2]]

Hash:
"131322" -> 0

...
"121233" -> 1
"121323" -> 2
"131322" -> already hashed.

0 and 3 are isomorphic.

(2) vsoftco's counter-example in his comment to Jean Logeart's answer:

A = [ [0, 1, 2], [2, 0, 1] ]
B = [ [1, 0, 2], [0, 2, 1] ]

"010212" -> A
"010212" -> already hashed.

A and B are isomorphic.

You can turn each set into a transposed-sorted string or hash or whatever compressed object for linear-time comparison. Note that this algorithm considers all three sets A, B and C as isomorphic even if one p converts A to B and another p converts A to C. Clearly, in this case, there are ps to convert any one of these three sets to the other, since all we are doing is moving each i in one set to a specific k in the other. If, as you stated, your goal is to "remove isomorphic permutations," you will still get a list of sets to remove.

Explanation:

Assume that along with our sorted hash, we kept a record of which permutation each i came from. vsoftco's counter-example:

010212  // hash for A and B
100110  // origin permutation, set A
100110  // origin permutation, set B

In order to confirm isomorphism, we need to show that the i's grouped in each index from the first set moved to some index in the second set, which index does not matter. Sorting the groups of i's does not invalidate the solution, rather it serves to confirm movement/permutation between sets.

Now by definition, each number in a hash and each number in each group in the hash is represented in an origin permutation exactly one time for each set. However we choose to arrange the numbers in each group of i's in the hash, we are guaranteed that each number in that group is representing a different permutation in the set; and the moment we theoretically assign that number, we are guaranteed it is "reserved" for that permutation and index only. For a given number, say 2, in the two hashes, we are guaranteed that it comes from one index and permutation in set A, and in the second hash corresponds to one index and permutation in set B. That is all we really need to show - that the number in one index for each permutation in one set (a group of distinct i's) went to one index only in the other set (a group of distinct k's). Which permutation and index the number belongs to is irrelevant.

Remember that any set S2, isomorphic to set S1, can be derived from S1 using one permutation function or various combinations of different permutation functions applied to S1's members. What the sorting, or reordering, of our numbers and groups actually represents is the permutation we are choosing to assign as the solution to the isomorphism rather than an actual assignment of which number came from which index and permutation. Here is vsoftco's counter-example again, this time we will add the origin indexes of our hashes:

110022 // origin index set A
001122 // origin index set B

Therefore our permutation, a solution to the isomorphism, is:

Or, in order:

(Notice that in Jean Logeart's example there is more than one solution to the isomorphism.)