查找两组数字是否同构的算法(在排列下)

Question

给定两个由一组数字组成的系统，我想知道它们在排列下是否同构。

例如{{1,2,3,4,5},{2,4,5,6,7},{2,3,4,6,7}} 是 3 组 5 个数字的系统。{{1,2,3,4,6},{2,3,5,6,7},{2,3,4,8,9}} 是另一个由 3 组 5 个数字组成的系统。我想检查这些系统是否同构。

没有。第一个系统使用数字 { 1,2,3,4,5,6,7 }，第二个系统使用数字 { 1,2,3,4,5,6,7,8,9}。

这是另一个例子。{{1,2,3}, {1,2,4}, {3,4,5}} 和 {{1,2,4}, {1,3,5}, {2,3,5} }.这两个由 3 组 3 个数字组成的系统是同构的。

如果我使用排列 (5 3 1 2 4)，其中 1 变为 5，2 变为 3，等等。第一组变为 {5,3,1}。第二个变为 {5,3,2}。第三个变成{1,2,4}。因此，通过此排列转换后的系统是 {{5,3,1},{5,3,2},{1,2,4}} 等效地重写为 {{1,2,4},{1, 3,5},{2,3,5}} 因为我对顺序不感兴趣。这是第二个系统，所以答案是肯定的。

目前，在第一个示例中，我应用了全部 9 个! {1,2,3,...,9} 的排列到第一个系统并检查我是否可以获得第二个系统。它给了我答案，但速度非常慢。

是否有一个聪明的算法？

(我只想要答案，是或否。我对获得将第一个系统转换为第二个系统的排列不感兴趣。)

Answer 1

正如评论中所指出的，这可能对应于关于复杂性和可用于解决这些问题的算法仍在调查中的图论问题。

然而，复杂性总是指一些输入大小。在这里，不清楚您的输入大小是多少。举个例子:我认为最合适的算法可能取决于你是否要扩大规模......

• 数字的数量(在您的示例中为 1...9)或
• 每组中的组数(在您的示例中为 3)或
• 集合中集合的大小(在您的示例中为 5)

使用您当前的方法，缩放数字的数量是不可行的，因为由于指数运行时间，您无法计算远大于 9 的数字的所有排列。但是，如果您的目的是检查包含 1000 个集合的集合的同构性，则集合数量多项式的算法(如果存在这样的算法)在实践中可能仍然较慢。

---

在这里，我想概述一下我尝试过的方法。我没有执行详细的复杂性分析(如果根本不存在多项式时间解决方案，这可能毫无意义 - 并且证明或反驳不能成为此处答案的主题)。 p>

基本思路如下:

最初，您计算每个输入数字的有效“域”。根据排列，这些是每个数字可以映射到的可能值。如果给定的数字是 1,2 和 3，那么域最初可能是

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

但对于给定的集合，人们已经可以推导出一些允许减少域的信息。例如:任何在第一个 集合中出现n 次的数字必须映射到在第二个集合中出现n 次的数字 套。

假设给定的集合是

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

那么域名就只有

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

因为 1 在第一组中出现了两次，而在第二组中出现两次的唯一值是 3。

计算出初始域后，可以对数字的可能分配(排列)执行回溯。回溯大致可以这样完成

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
}

(这个想法在某种程度上受到了 Arc Consistency 3 Algorithm 的“启发”，尽管从技术上讲，这些问题并不直接相关)

在回溯过程中，可以采用不同的修剪标准。也就是说，人们可以想出各种技巧来快速检查某个赋值(部分排列)和该赋值所隐含的域是否“有效”。

有效分配的明显(必要)标准是没有域可能是空的。更一般地说:每个域的出现频率可能不会超过它包含的元素数量。当您发现域是

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

那么就不可能再有有效的解，算法可能会回溯。

---

当然，回溯往往在输入大小上具有指数级的复杂性。但可能根本不存在这个问题没有有效的算法。对于这种情况，与蛮力耗尽搜索相比，在回溯期间可能采用的修剪可能至少有助于减少某些情况(或一般的小输入大小)的运行时间。

这是我用 Java 实现的实验。这不是特别优雅，但表明它基本上有效:如果存在解决方案，它会快速找到解决方案，并且(对于给定的输入大小)不需要很长时间就能检测到没有解决方案。

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());
        }
    }

}