python - 如何从图中计算不同排列的最小排除项？

Question

这是 codechef 中的练习题。完整 question

到目前为止我所做的是，从元组列表创建了一个图

(例如:input_list = [(1,2),(2,3)])

然后对 input_list 集合进行所有排列，并将每个排列传递给 process()。在 process() 中，迭代每个元素并计算其 MEX。

MEX 的定义:

Minimum Excludant(MEX) is the smallest non-negative integer not included in given set of numbers.

代码:

from collections import defaultdict
from itertools import permutations


class Graph:
    """ Graph is data structure(directed). """


    def __init__(self, connections):
        """ Initializing graph with set as default value. """
        self._graph = defaultdict(set)
        self.add_connections(connections)

    def add_connections(self, connections):
        """ Add connections(list of tupules) to graph. """
        for node1, node2 in connections:
            self.add(node1,node2)

    def add(self, node1, node2):
        """ Add node1 and node2 to graph which is initialized with set by default. """
        self._graph[node1].add(node2)
        self._graph[node2].add(node1)

    def get_graph(self):
        return dict(self._graph)


def mex(arr_set):
    mex = 0
    while mex in arr_set:
        mex+=1
    return mex


def process(graph, order):
    a_p = [0] * len(order)
    for i, el in zip(range(len(order)), order):
        a_p[i] = mex(graph[el])
    return a_p


t = int(input())
for _ in range(t):
    v = int(input())
    e = []
    for i in range(v-1):
        e.append(tuple(map(int, input().split())))

    g = Graph(e)
    print(g.get_graph())
    all_vertices = {s for i in e for s in i}
    result = []
    for p in permutations(all_vertices, v):
        out = process(g.get_graph(), p)
        print("{} --> {}".format(p, out))
        result.append(out) if out not in result else None

    print(len(result))

我对用 MEX 进行计算感到震惊。

我不明白为什么我没有得到正确的结果。

请解释我的代码哪里出错以获得所需的输出？

欢迎提出任何改进我的代码的建议。

问题规则:

你有一棵树 T 有 n 个顶点。考虑对 T 的顶点进行排序 P=(v_1,…,vn)。我们使用以下过程构建序列 A(P)=(a1,…,an):

• 设置所有ai=−1。
• 按 v1,…,vn 顺序处理顶点。对于当前顶点vi集合ai=MEX(au1,…,auk)，其中 u1,…,uk 是 vi 的邻居集。

意外结果:

1
3
1 2
2 3
{1: {2}, 2: {1, 3}, 3: {2}}
(1, 2, 3) --> [0, 0, 0] # should be (0, 1, 0)
(1, 3, 2) --> [0, 0, 0]
(2, 1, 3) --> [0, 0, 0]
(2, 3, 1) --> [0, 0, 0] # should be (1, 0, 1)
(3, 1, 2) --> [0, 0, 0]
(3, 2, 1) --> [0, 0, 0]
1

结果说明:

(我取了(2,3,1)组合来解释)

按照(2,3,1)的顺序，我们首先处理v2。所以

• 设置i=2，我们首先观察到v2有邻居v1并且v3。由于 a1 和 a3 都处于初始化状态 (=−1)，我们设置

  a2=mex{−1,−1}=0。

• 然后我们设置i=3。顶点 v3 有一个 v2 作为它唯一的邻居。由于 a2=0 算法告诉我们设置

  a3=mex{0}=1。

• 要处理的最后一个节点是a1。 v1 的唯一邻居是v2，目前 a2=0。所以算法告诉我们设置

  a1=mex{0}=1。

所以，输出是 P(2, 3, 1) ==> A(P)= (a1, a2, a3) = (1, 0, 1) 但我得到(0, 0, 0) 所有值。

Answer 1

您的“处理”功能未执行应有的操作。您应该在 -1 处初始化 a_p 并将对应于邻居而不是它们的索引的 a_p 的 mex 分配给 a_i。 (就像你对规则的解释一样)

像那样:

def process(graph, order):
    a_p = [-1] * len(order)
    for el in order:
        a_p[el-1] = mex([a_p[u-1] for u in graph[el]])
    return a_p

PS:您可以(应该？)使用 enumerate(L) 而不是 zip(range(len(L)), L)。