Algorithm to find if two sets of sets of numbers are isomorphic or not (under permutation)

Question

Given two systems consisting of set of sets of numbers, I would like to know if they are isomorphic under permutation.

For example {{1,2,3,4,5},{2,4,5,6,7},{2,3,4,6,7}} is a system of 3 sets of 5 numbers. {{1,2,3,4,6},{2,3,5,6,7},{2,3,4,8,9}} is a another system of 3 sets of 5 numbers. I want to check if these systems are isomorphic.

There are not. The first system uses numbers { 1,2,3,4,5,6,7 }, the second one uses numbers { 1,2,3,4,5,6,7,8,9}.

Here is another example. {{1,2,3}, {1,2,4}, {3,4,5}} and {{1,2,4}, {1,3,5}, {2,3,5}}. Those two systems of 3 sets of 3 numbers are isomorphic.

If I use permutation (5 3 1 2 4) where 1 becomes 5, 2 becomes 3, etc. The first set becomes {5,3,1}. The second becomes {5,3,2}. The third one becomes {1,2,4}. So the transformed system by this permutation is {{5,3,1},{5,3,2},{1,2,4}} that is equivalently rewritten to {{1,2,4},{1,3,5},{2,3,5}} as I am not interested in order. This is the second system, so the answer is yes.

Currently, on the first example, I apply all 9! permutations of {1,2,3,...,9} to the first system and check if I can get the second one. It gives me an answer, but very slowly.

Is there a clever algorithm ?

(I only want the answer, yes or no. I am not interested in getting a permutation that transform the first system to the second one.)

Answer 1

As pointed out in the comments, this might correspond to graph-theoretic problems that are still under investigation regarding the complexity and the algorithms that can be employed to tackle them.

However, the complexity always refers to some input size. And here, it is not clear what your input size is. As an example: I think that the most appropriate algorithm might depend on whether you are going to scale up...

• the number of numbers (1...9 in your example) or
• the number of sets in each set (3, in your example) or
• the size of the sets in the sets (5, in your example)

Using your current approach, scaling the number of numbers would not be feasible, because you can't compute all permutations for numbers much larger than 9 due to the exponential running time. But if your intention was to check the isomorphy of sets containing 1000 sets, an algorithm that was polynomial in the number of sets (if such an algorithm existed) might still be slower in practice.

---

Here, I'd like to sketch an approach that I tried. I did not perform a detailed complexity analysis (which might be pointless if there exist no polynomial time solution at all - and to prove or disprove that can't be the subject of an answer here).

The basic idea is as follows:

Initially, you compute the valid "domains" for each input number. These are possible values that each number may be mapped to, based on the permutation. If the given numbers are 1,2 and 3, then the domains initially could be

1 -> { 1, 2, 3 }
2 -> { 1, 2, 3 }
3 -> { 1, 2, 3 }

But for the given sets, one can already derive some information that allows reducing the domains. For example: Any number that appears n times in the first sets must be mapped to a number that appears n times in the second sets.

Imagine that the given sets are

{{1,2},{1,3}}
{{3,1},{3,2}}

Then the domains would only be

1 -> { 3 }
2 -> { 1, 2 }
3 -> { 1, 2 }

because the 1 appears twice in the first sets, and the only value that appears twice in the second sets is the 3.

After the initial domains are computed, one can perform a backtracking of the possible assignments (permutations) of the numbers. The backtracking can roughly be done as

for (each number n that has no permutation value assigned) {
    assign a permutation value (from the current domain of n) to n
    update the domains of all other numbers
    if the domains are no longer valid, then backtrack
    if the solution was found, then return it
}

(The idea is somehow "inspired" by the Arc Consistency 3 Algorithm, although technically, the problems are not directly related)

During the backtracking, one can employ different pruning criteria. That is, one can think of various tricks in order to quickly check whether a certain assignment (a partial permutation) and the domains that are implied by this assignent are "valid" or not.

The obvious (necessary) criterion for an assignment to be valid is that none of the domains may be empty. More generally: Each domain may not appear more often than the number of elements that it contains. When you find out that the domains are

1 -> { 4 }
2 -> { 2,3 }
3 -> { 2,3 }
4 -> { 2,3 }

then there can no longer be a valid solution, and the algorithm may track back.

---

Of course, bactracking tends to have exponential complexity in the input size. But it might be that there simply exists no efficient algorithm for this problem. For this case, the pruning that may be employed during the backtracking may at least help to reduce the running time for certain cases (or for small input sizes in general) compared to a brute-force exhausting search.

Here is an implementation of my experiments, in Java. This is not particularly elegant, but shows that it basically works: It quickly finds a solution if there exists one, and (for the given input sizes) does not take long to detect when there is no solution.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

public class SetSetIsomorphisms
{
    public static void main(String[] args)
    {
        Map<Integer, Integer> p = new LinkedHashMap<Integer, Integer>();
        p.put(0, 3);
        p.put(1, 4);
        p.put(2, 8);
        p.put(3, 2);
        p.put(4, 1);
        p.put(5, 5);
        p.put(6, 0);
        p.put(7, 9);
        p.put(8, 7);
        p.put(9, 6);

        Set<Set<Integer>> sets0 = new LinkedHashSet<Set<Integer>>();
        sets0.add(new LinkedHashSet<Integer>(Arrays.asList(1,2,3,4,5)));
        sets0.add(new LinkedHashSet<Integer>(Arrays.asList(2,4,5,6,7)));
        sets0.add(new LinkedHashSet<Integer>(Arrays.asList(0,8,3,9,7)));

        Set<Set<Integer>> sets1 = new LinkedHashSet<Set<Integer>>();
        for (Set<Integer> set0 : sets0)
        {
            sets1.add(applyMapping(set0, p));
        }

        // Uncomment these lines for a case where NO permutation is found
        //sets1.remove(sets1.iterator().next());
        //sets1.add(new LinkedHashSet<Integer>(Arrays.asList(4,8,2,3,5)));


        System.out.println("Initially valid? "+
            areIsomorphic(sets0, sets1, p));


        boolean areIsomorphic = areIsomorphic(sets0, sets1);
        System.out.println("Result: "+areIsomorphic);
    }

    private static <T> boolean areIsomorphic(
        Set<Set<T>> sets0, Set<Set<T>> sets1)
    {
        System.out.println("sets0:");
        for (Set<T> set0 : sets0)
        {
            System.out.println("    "+set0);
        }
        System.out.println("sets1:");
        for (Set<T> set1 : sets1)
        {
            System.out.println("    "+set1);
        }

        Set<T> all0 = flatten(sets0);
        Set<T> all1 = flatten(sets1);

        System.out.println("All elements");
        System.out.println("    "+all0);
        System.out.println("    "+all1);

        if (all0.size() != all1.size())
        {
            System.out.println("Different number of elements");
            return false;
        }

        Map<T, Set<T>> domains = computeInitialDomains(sets0, sets1);

        System.out.println("Domains initially:");
        print(domains, "");

        Map<T, T> assignment = new LinkedHashMap<T, T>();
        return compute(assignment, domains, sets0, sets1, "");
    }

    private static <T> Map<T, Set<T>> computeInitialDomains(
        Set<Set<T>> sets0, Set<Set<T>> sets1)
    {
        Set<T> all0 = flatten(sets0);
        Set<T> all1 = flatten(sets1);
        Map<T, Set<T>> domains = new LinkedHashMap<T, Set<T>>();
        for (T e0 : all0)
        {
            Set<T> domain0 = new LinkedHashSet<T>();
            for (T e1 : all1)
            {
                if (isFeasible(e0, sets0, e1, sets1))
                {
                    domain0.add(e1);
                }
            }
            domains.put(e0, domain0);
        }
        return domains; 
    }

    private static <T> boolean isFeasible(
        T e0, Set<Set<T>> sets0,
        T e1, Set<Set<T>> sets1)
    {
        int c0 = countContaining(sets0, e0);
        int c1 = countContaining(sets1, e1);
        return c0 == c1;
    }

    private static <T> int countContaining(Set<Set<T>> sets, T value)
    {
        int count = 0;
        for (Set<T> set : sets)
        {
            if (set.contains(value))
            {
                count++;
            }
        }
        return count;
    }


    private static <T> boolean compute(
        Map<T, T> assignment, Map<T, Set<T>> domains, 
        Set<Set<T>> sets0, Set<Set<T>> sets1, String indent)
    {
        if (!validCounts(domains.values()))
        {
            System.out.println(indent+"There are too many domains "
                + "with too few elements");
            print(domains, indent);
            return false;
        }
        if (assignment.keySet().equals(domains.keySet()))
        {
            System.out.println(indent+"Found assignment: "+assignment);
            return true;
        }

        List<Entry<T, Set<T>>> entryList = 
            new ArrayList<Map.Entry<T,Set<T>>>(domains.entrySet());
        Collections.sort(entryList, new Comparator<Map.Entry<T,Set<T>>>()
        {
            @Override
            public int compare(Entry<T, Set<T>> e0, Entry<T, Set<T>> e1)
            {
                return Integer.compare(
                    e0.getValue().size(), 
                    e1.getValue().size());
            }
        });
        for (Entry<T, Set<T>> entry : entryList)
        {
            T key = entry.getKey();
            if (assignment.containsKey(key))
            {
                continue;
            }
            Set<T> domain = entry.getValue();
            for (T value : domain)
            {
                Map<T, Set<T>> newDomains = copy(domains);
                removeFromOthers(newDomains, key, value);
                assignment.put(key, value);
                newDomains.get(key).clear();
                newDomains.get(key).add(value);

                System.out.println(indent+"Using "+assignment);

                Set<Set<T>> setsContainingKey = 
                    computeSetsContainingValue(sets0, key);
                Set<Set<T>> setsContainingValue = 
                    computeSetsContainingValue(sets1, value);
                Set<T> keyElements = flatten(setsContainingKey);
                Set<T> valueElements = flatten(setsContainingValue);

                for (T otherKey : keyElements)
                {
                    Set<T> otherValues = newDomains.get(otherKey);
                    otherValues.retainAll(valueElements);
                }

                System.out.println(indent+"Domains when "+assignment);
                print(newDomains, indent);

                boolean done = compute(assignment, newDomains, 
                    sets0, sets1, indent+"  ");
                if (done)
                {
                    return true;
                }
                assignment.remove(key);
            }
        }
        return false;
    }


    private static boolean validCounts(
        Collection<? extends Collection<?>> collections)
    {
        Map<Collection<?>, Integer> counts = 
            new LinkedHashMap<Collection<?>, Integer>();
        for (Collection<?> c : collections)
        {
            Integer count = counts.get(c);
            if (count == null)
            {
                count = 0;
            }
            counts.put(c, count+1);
        }
        for (Entry<Collection<?>, Integer> entry : counts.entrySet())
        {
            Collection<?> c = entry.getKey();
            Integer count = entry.getValue();
            if (count > c.size())
            {
                return false;
            }
        }
        return true;
    }


    private static <K, V> Map<K, Set<V>> copy(Map<K, Set<V>> map)
    {
        Map<K, Set<V>> copy = new LinkedHashMap<K, Set<V>>();
        for (Entry<K, Set<V>> entry : map.entrySet())
        {
            K k = entry.getKey();
            Set<V> values = entry.getValue();
            copy.put(k, new LinkedHashSet<V>(values));
        }
        return copy;
    }

    private static <T> Set<Set<T>> computeSetsContainingValue(
        Iterable<? extends Set<T>> sets, T value)
    {
        Set<Set<T>> containing = new LinkedHashSet<Set<T>>();
        for (Set<T> set : sets)
        {
            if (set.contains(value))
            {
                containing.add(set);
            }
        }
        return containing;
    }

    private static <T> void removeFromOthers(
        Map<T, Set<T>> map, T key, T value)
    {
        for (Entry<T, Set<T>> entry : map.entrySet())
        {
            if (!entry.getKey().equals(key))
            {
                Set<T> values = entry.getValue();
                values.remove(value);
            }
        }
    }

    private static <T> Set<T> flatten(
        Iterable<? extends Collection<? extends T>> collections)
    {
        Set<T> set = new LinkedHashSet<T>();
        for (Collection<? extends T> c : collections)
        {
            set.addAll(c);
        }
        return set;
    }




    private static <T> Set<T> applyMapping(
        Set<T> set, Map<T, T> map)
    {
        Set<T> result = new LinkedHashSet<T>();
        for (T e : set)
        {
            result.add(map.get(e));
        }
        return result;
    }

    private static <T> boolean areIsomorphic(
        Set<Set<T>> sets0, Set<Set<T>> sets1, Map<T, T> p)
    {
        for (Set<T> set0 : sets0)
        {
            Set<T> set1 = applyMapping(set0, p);
            if (!sets1.contains(set1))
            {
                return false;
            }
        }
        return true;
    }

    private static void print(Map<?, ?> map, String indent)
    {
        for (Entry<?, ?> entry : map.entrySet())
        {
            System.out.println(indent+entry.getKey()+": "+entry.getValue());
        }
    }

}

Answer 2

I believe your problem is equivalent to the Graph Isomorphism problem (GI). Your set of sets can be modelled as a (bipartite) graph, with nodes representing the base values of your set (e.g., 1, 2, 3, ... 7), while nodes on the right represent sets (e.g., {1,2,3,4,6} or {2,3,5,6,7}). Draw an edge connecting a node on the left with a node on the right if the number is an element of the set; in my example, 1 is connected only to {1,2,3,4,6} while 2 is connected to both {1,2,3,4,6} and to {2,3,5,6,7}. 1 is connected to all sets which contain it; {1,2,3,4,6} is connected to all numbers contained in it.

Any bipartite graph can be realized in this manner. Conversely, GI can be reduced to solving GI on bipartite graphs. (Any graph can be made into a bipartite graph by replacing each edge with two new edges and a new vertex. Isomorphism in the resulting bipartite graphs is equivalent to isomorphism in the original graphs.)

GI is in NP, but it is not known whether it is NP complete. In practice, GI can be solved quickly for hundreds of vertices with e.g., NAUTY.