边缘消除数

Question

在埃里希·弗里德曼的数学魔术中，(页面上的问题#2 )，您的挑战是找到连通图的边缘消除数。

一个单一的边缘消除是从一个图中删除一个边，而不断开这个图，除了创建唯一的顶点。例如，在下面的图中，两个最左的边和最右边的边可能在法律上被消除，但是中心边可能没有，因为这会导致两个断开连接的分量大于一个顶点。

边消去序列是对图中的每一条边按指定的顺序进行消去。每次消除必须是合法的点，在顺序时，它是执行。例如，在上面的图上，一个合法的边缘消除序列是删除最右边的边缘，然后是中间的边缘，然后是左上角，然后是左下角。

图的边消去数是一个图所具有的不同的消边序列的个数。例如，上面的图的消边数为14。从左上角开始的序列有4个，左下角的序列有4个，右边的序列有6个。

输入:保证输入图是连通的。该图将作为带标记顶点的边的列表给出。例如，上面的图表可以给出如下所示：

[(0,2), (1,2), (2,3), (3,4)]

在该需求范围内，任何对您的语言/代码最方便的格式都可以。别吃这个。(例如，顶点标签中没有代码。)

代码:您可以编写一个程序，输入从命令行或STDIN，或函数，或动词，或您的语言的等值。

这是代码高尔夫，赢的字节最少。

测试：

One edge:
[(0,1)]
1

Path:
[(0,1), (1,2), (2,3), (3,4)]
8

Triangle with two additional edges off one vertex:
[(0,1), (1,2), (0,2), (0,3), (0,4)]
92

Randomly generated:
[(0, 2), (0, 4), (1, 2), (1, 4), (2, 5), (3, 4), (3, 5)]
1240

[(0, 2), (0, 3), (1, 3), (1, 4), (1, 5), (2, 3), (3, 4), (3, 5)]
16560

再说一遍，这是代码高尔夫，最少字节获胜。如果我做错了什么，请问清楚问题，或者告诉我。

Answer 1

APL (77)

{0=⍴,⍵:1⋄C←0/⍨⍴V←∪∊G←⍵⋄0∊C⊣{C[V⍳⍵]:⍬⋄C[V⍳⍵]←1⋄∇¨⍵~⍨∊G/⍨⍵∊¨G}⊃V:0⋄+/∇¨⍵∘~∘⊂¨⍵}

这是一个函数，它将边的列表作为一个图，即：

      {0=⍴,⍵:1⋄C←0/⍨⍴V←∪∊G←⍵⋄0∊C⊣{C[V⍳⍵]:⍬⋄C[V⍳⍵]←1⋄∇¨⍵~⍨∊G/⍨⍵∊¨G}⊃V:0⋄+/∇¨⍵∘~∘⊂¨⍵} (0 2)(0 3)(1 3)(1 4)(1 5)(2 3)(3 4)(3 5)
16560

(顺便说一句，这在我的电脑上大约需要半秒钟。)

所以格式是[[v1,v2], [v1,v2], ...]。要传递单边图，首先需要将其括起来，否则将得到[0,1]而不是[[0,1]]：

      {0=⍴,⍵:1⋄C←0/⍨⍴V←∪∊G←⍵⋄0∊C⊣{C[V⍳⍵]:⍬⋄C[V⍳⍵]←1⋄∇¨⍵~⍨∊G/⍨⍵∊¨G}⊃V:0⋄+/∇¨⍵∘~∘⊂¨⍵} ⊂0 1
1  

解释：

• 基例1(空图)：
  • 0=⍴,⍵:1：如果图是空的，返回1：当前路径已经清空了图，同时保持了它的连接。

• 基例2(不连通图)：
  • C←0/⍨⍴V←∪∊G←⍵：存储G中的边列表，V中的顶点，C中每个顶点的0。
  • {.}⊃V：看看图是否连通。从第一个顶点开始：
    • C[V⍳⍵]:⍬：如果已经访问了顶点，什么也不做
    • C[V⍳⍵]←1：标记当前访问的顶点
    • G/⍨⍵∊¨G：找到这个顶点连接到的每一条边
    • ⍵~⍨∊：查找与这些边有关的所有顶点，但当前顶点除外
    • ∇¨：访问所有这些顶点

- `0∊C`...`:0`: afterwards, if one of the vertices is not visited, the graph is no longer connected. The current path is invalid, so return `0`.

• 递归案例：
  • ⍵∘~∘⊂¨⍵：对于每个边，创建通过从当前图中删除该边以及任何孤立顶点而形成的图形。
  • ∇¨：对于这些图中的每一个，找出它的边消除数。
  • +/：把这些加起来。

Answer 2

Python，228个字节

p=lambda l,r,d:reduce(lambda y,x:p(y[0]|set(x),[],y[1])if(x[0]in y[0]or x[1]in y[0])else(y[0],y[1]+[x]),d,(l,r))
def c(h):
  k=0
  for i in range(len(h)):g=h[:i]+h[i+1:];k+=len(g)<2 or p(set(g[0]),[],g)[1]==[]and c(g)
  return k

一种优势：

c([(0,1)])
1

路径：

c([(0,1), (1,2), (2,3), (3,4)])
8

与一个顶点有两个附加边的三角形：

c([(0,1), (1,2), (0,2), (0,3), (0,4)])
92

随机生成：

c([(0, 2), (0, 4), (1, 2), (1, 4), (2, 5), (3, 4), (3, 5)])
1240
c([(0, 2), (0, 3), (1, 3), (1, 4), (1, 5), (2, 3), (3, 4), (3, 5)])
16560

解释：

在第一个语句中，我创建了一个检查给定图d是否连接的函数。

 p=lambda l,r,d:reduce(lambda y,x:p(y[0]|set(x),[],y[1])if(x[0]in y[0]or x[1]in y[0])else(y[0],y[1]+[x]),d,(l,r))

这样做的思想是:你必须把一个具有给定边元组的图缩减为一个包含每个连接点的列表，称为connected_set，还有一个包含所有未连通的元组的列表，称为not_connected。核心是约简函数，它是一个内建函数，它调用每个给定的函数，并为列表中的每个元素设置两个参数。减少工作:减少(可调用，列表，初始)

1. callable(initial, list[0]) returns element
2. callable(element, list[1]) ...
3. callable(element, list[n])

对于给定的代码，我返回包含的元组(connected_set，未连接)。初始值是包含图的第一个发现点的connected_set。未连接的-但是初始的en空列表。

lambda y,x:p(y[0]|set(x),[],y[1])if(x[0]in y[0]or x[1]in y[0])else(y[0],y[1]+[x])

指：

def reducer((connected_set, not-connected-yet), element):
    #an edge is connected, if left or right point is in connected_set
    if element[0] in connected_set or element[1] in connected_set:
        #add both points to connected_set
        connected_set |= set([x[0], x[1])
        #resolve not-connected-yets
        check_graph(connected_set, not-connected-yet=[], list=not-connected-yet)
        return (connected_set, not-connected-yet)
    else
        return (connected_set, not-connected-yet + [element]

def check_graph(connected_set, not-connected-yet, list):
    return reduce(reducer, list, (connected_set, not-connected-yet))

当check_graph返回一个元组时，一个图是连接的，第二个元素是一个空列表。

其余的是加法：

def c(h):
  k=0
  for i in range(len(h)):g=h[:i]+h[i+1:];k+=len(g)<2 or p(set(g[0]),[],g)[1]==[]and c(g)
  return k

意思是可读的：

def count_graph(graph)
    sequences = 0
    #iterate over the possibilities to eliminate an edge on given graph
    # e.g.: graph = [1, 2, 3]
    # i=0: parted_graph = [2, 3]
    # i=1: parted_graph = [1, 3]
    # i=2: parted_graph = [2, 3]
    for i in range(len(graph)):
        parted_graph = graph[:i] + graph[i+1:]
        if len(parted_graph) < 2:
            # a graph with one edge is result of a sequence so raise num
            sequences += 1
        else:
            # continue eliminating if graph is connected
            if check_graph(set(parted_graph[0]), [], parted_graph)[0] == []:
                sequences += count_graph(parted_graph)
    return sequences