对数组进行排序以获得最大的成对匹配

Question

我有一个数组:

array([[ 4, 10],
       [ 4,  2],
       [ 0,  7],
       [ 5, 11],
       [ 6,  8],
       [ 3,  6],
       [ 9,  7],
       [ 2, 11],
       [ 9,  5],
       [ 8,  1]])

我想要一种方法来对值对进行排序,以便尽可能多的成对2元素集具有公共值.这是所需有序数组的示例:

array([[ 4, 10],
       [ 4,  2],
       [ 2, 11],
       [ 5, 11],
       [ 9,  5],
       [ 9,  7],
       [ 0,  7],  #note the gap here:
       [ 8,  1],
       [ 6,  8],
       [ 3,  6]])

关于这些阵列有几个条件.没有重复对(即:[1,0]或[0,1]将出现在数组的其他位置,如果[0,1]已经存在).没有对具有相同的值(即:[1,1]将不存在).没有对将有两个以上的匹配(喵:在整个数组中没有值超过两次.)但是一对可以有零匹配(注意在上面的数组中没有匹配的间隙).

显然,我可以创建数组的每个排列,但这似乎是野蛮的.我认为可能有某种方法可以切割平台并以合理的方式重新堆叠,以便按照少量切割进行分类.但在我走这条路之前,我想:1)确保没有numpy或collections功能已经做到了这一点.2)知道没有棘手的天才方式来使用numpy .sort()(或类似的)来做到这一点.3)确定这是否是一项常见任务,并且有算法可以执行此操作.("哦,这是Blumen-Funke算法!")

以下是一些生成混洗测试数组并检查已排序数组的代码:

def shuffled(N=12, ans=1):
    '''returns is now the unsorted test array'''
    r = range(N)
    random.shuffle(r)
    l = []
    for i in range(N):
        l.append((r[i-1], r[i]))
    random.shuffle(l)
    return np.array(l)[ans+1:]

# step 2: ???

def test_ordered(a):
    '''checks if generated array has been sorted'''
    c0 = a[1:,0]==a[:-1,0]
    c1 = a[1:,0]==a[:-1,1]
    c2 = a[1:,1]==a[:-1,0]
    c3 = a[1:,1]==a[:-1,1]
    cond = c0+c1+c2+c3
    ans = sum(numpy.logical_not(cond))
    # when sorted this should return the same number input into
    # shuffled() as 'ans':
    return ans

(这是一个主观问题吗？我被警告说是.)

结果:

非常感谢您的帮助.Sven的解决方案比Paul的解决速度快20%,并且很高兴,他们都在线性时间运行,Doug的答案并没有解决问题.在输入数据中,性能​​对"中断"或"间隙"的数量存在很高但也很大程度上线性的依赖性.见下图.10,000幅度轴是N. 0.5轴是断裂的百分比.z轴是以秒为单位的性能.

再次感谢!

Answer 1

您已经描述了一个图形,其中顶点是数字,边缘是您的对.

您的条件指定每个数字在列表中显示一次或两次.这意味着图表中的连接组件是线(或循环).您可以使用此算法找到它们:

• [存在行]如果可能,选择一个1度的数字(也就是说,它只在列表中出现一次).尽可能地跟随对的链,将它们添加到输出并从图中移除遍历的顶点.
• [循环存在]如果没有度数为1的数字,则表示所有组件都是循环.选择任何顶点(它将具有2级).像以前一样跟踪对,将它们添加到输出并删除遍历的顶点,但是这次在达到原始数字时停止.
• 重复,直到你用完了图中的所有顶点.

您可以有效地运行此算法:维护一组1度的顶点和2度的另一个顶点.当您使用边缘(原始列表中的一对)时,适当地修改集合:从第一个集合中删除1级的端点,并将端点从2级设置移动到1级.或者,使用优先级队列.

您还需要对配对进行有效查找:从顶点到相邻顶点列表构建一个dict.

使用这些想法,您可以在线性时间内找到最佳排序(假设O(1)set和dict实现).

这是一个有点笨重的实现.

import collections

def handle_vertex(v, vs):
  if v in vs[0]:
    vs[0].remove(v)
  elif v in vs[1]:
    vs[0].add(v)
    vs[1].remove(v)

def follow(edgemap, start, vs):
  """Follow a path in the graph, yielding the edges."""
  v0 = start
  last = None
  while True:
    # All vertices that we can go to next.
    next_v = [v for v in edgemap[v0] if v != last]
    if not next_v:
      # We've reached the end (we must have been a line).
      return
    assert len(next_v) == 1 or (v0 == start and len(next_v) == 2)
    next_v = next_v[0]
    # Remove the endpoints from the vertex-degree sets.
    handle_vertex(v0, vs)
    handle_vertex(next_v, vs)
    yield v0, next_v
    if next_v == start:
      # We've got back to the start (we must have been a cycle).
      return
    v0, last = next_v, v0

def pairsort(edges):
  edgemap = collections.defaultdict(list)
  original_edges = {}
  for a, b in edges:
    # Build the adjacency table.
    edgemap[a].append(b)
    edgemap[b].append(a)
    # Keep a map to remember the original order pairs appeared in
    # so we can output edges correctly no matter which way round
    # we store them.
    original_edges[a, b] = [a, b]
    original_edges[b, a] = [a, b]
  # Build sets of degree 1 and degree 2 vertices.
  vs = [set(), set()]
  for k, v in edgemap.iteritems():
    vs[len(v) - 1].add(k)
  # Find all components that are lines.
  while vs[0]:
    v0 = vs[0].pop()
    for e in follow(edgemap, v0, vs):
      yield original_edges[e]
  # Find all components that are cycles.
  while vs[1]:
    v0 = vs[1].pop()
    for e in follow(edgemap, v0, vs):
      yield original_edges[e]

input = [
    [ 4, 10],
    [ 4,  2],
    [ 0,  7],
    [ 5, 11],
    [ 6,  8],
    [ 3,  6],
    [ 9,  7],
    [ 2, 11],
    [ 9,  5],
    [ 8,  1]]

print list(pairsort(input))