Каноническая форма для набора списков - PullRequest
Новая
       26

Каноническая форма для набора списков

1 голос
/ 13 апреля 2019

Мне даны два неупорядоченных набора, каждый из которых содержит m списков из n элементов.Пример для 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 эквивалентны, поскольку в D2 имеется присвоение (1,2,3,4) в D1 ↔ (3,2,1,4).

В этом примереэлементы являются числами, но это не имеет большого значения, потому что меня интересует только отношение эквивалентности между двумя наборами, а не сами элементы.

Я ищу быстрый способ проверить, эквивалентны ли два заданных набора,Вместо того, чтобы выполнять поиск в обратном порядке, чтобы найти назначения между элементами, можно ли сериализовать наборы в уникальной (канонической) форме, чтобы можно было показать, что два набора эквивалентны, если их канонические формы идентичны?

Обновление: Несмотря на то, что эта проблема в целом кажется неразрешимой (см. Ответ ниже), оказывается, что поиск с обратным отслеживанием хорошо работает на моих данных.Ниже приведен псевдокод для моей реализации: 

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)

1 Ответ

1 голос
/ 13 апреля 2019

Ваша проблема, по крайней мере, так же сложна, как и проблема изоморфизма графов .Направленный граф можно представить в виде набора списков длиной 2, что является частным случаем вашей проблемы.Кроме того, известно, что проблема изоморфизма ориентированных графов имеет ту же сложность, что и проблема изоморфизма графов.Таким образом, частный случай вашей задачи так же сложен, как и проблема полного изоморфизма графов.Точная сложность изоморфизма графов не известна.Для него нет известных алгоритмов полиномиального времени, хотя предполагается, что он не является NP-полным.

Поскольку не существует простого решения проблемы изоморфизма графов, я сомневаюсь, что сериализация обеспечит простое решение вашей проблемы.

...