algorithm - 列表集的规范形式

Question

我有两个无序集合，每个集合包含 n 个项目的 m 个列表。 m=4 和 n=3 的示例:

D1 = {[4,2,1], [3,3,1], [4,2,3], [1,2,1]}
D2 = {[3,2,3], [4,2,3], [1,1,3], [4,2,1]}

如果在各自列表中的元素之间存在一对一的对应关系，则这两个集合被认为是等价的。在上面的例子中，D1 和 D2 是等价的，因为在 D1 中有一个赋值 (1,2,3,4) ↔ (3,2,1,4) 在 D2 中。

在这个例子中，项目是数字，但这并不重要，因为我只关心两个集合之间的等价关系，而不关心项目本身。

我正在寻找一种快速方法来检查两个给定的集合是否相等。不是执行回溯搜索来查找项目之间的分配，而是可以将集合以唯一(规范)形式序列化，以便在规范形式相同的情况下可以证明两个集合是等价的？

更新:尽管这个问题一般来说似乎很难解决(请参阅下面的答案)，但事实证明，回溯搜索在实践中对我的数据效果很好。下面是我的实现的伪代码:

s = new stack(of level)
x1_x2 = new dictionary(of int, int)
bound_x2s = new set(of int)

function setsEquivalent(d1: set, d2: set) : boolean
    if d1.m <> d2.m or d1.n <> d2.n: return false        
    s.push(new level)
    do until s.size = 0
        m1 = s.size
        m2 = s.top.m2
        if m1 > m
            return true
        elseif s.top.m2 > m
            backtrack()
        else                
            s.push(new level)
            for k = 1..n
                if not try_bind(d1.m(m1)(k), d2.m(m2)(k))
                    backtrack()
                    exit for
    return false

function try_bind(x1: int, x2: int) : boolean
    if x1_x2.containskey(x1)
        return x1_x2(x1) = x2
    elseif bound_x2s.contains(x2)
        return false
    else
        x1_x2.add(x1,x2)
        bound_x2s.add(x2)
        s.top.boundx1s.add(x1)
        return true

procedure backtrack()
    for each x1 in s.top.boundx1s:
        bound_x2s.remove(x1_x2(x1))
        x1_x2.remove(x1)
    s.pop
    if s.size <> 0
      s.top.m2 += 1

record level
    m2 = 1
    boundx1s = new list(of int)

Answer 1

你的问题至少和 Graph Isomorphism Problem 一样难.有向图可以表示为一组长度为 2 的列表，这是您问题的特例。此外，已知有向图同构问题与图同构问题具有相同的复杂性。因此，您的问题的一个特例与完整的图同构问题一样难。图同构的确切复杂性尚不清楚。没有已知的多项式时间算法，但不认为它是 NP 完全的。

由于图同构问题没有简单的解决方案，我怀疑序列化能否为您的问题提供简单的解决方案。