algorithm - 排列数字对，使相邻对的成员相等

Question

我想排列以下项目，形成最长的链，从 12-8 开始，并将数字首尾匹配。

我的项目是 7-4、11-8、11-11、1-0、4-2、7-5、10-8、7-3、10-5、7-2、9-8、 12-8、0-0、11-10

最长的可能链是 12-8、8-11、11-11、11-10、10-5、5-7、7-4、4-2、2-7、7-3

我尝试遍历项目数组并获取与我要查找的数字匹配的第一个值，但它不会产生最长的链。我的方法让我:12-8、8-11、11-11、11-10、10-8、8-9

如何为这个任务编写合适的排序算法？

Answer 1

你需要递归，但它可能不适用于更大的数据集:像这样的东西。

免责声明:这可能不是最优化的解决方案(复杂度为 O(N!))，但如果允许使用递归，它的实现非常简单

(这不是objective-c的代码，是算法，自己翻译，不好意思我不懂objective-c)

list function sortTupleList(list a, list b) //b is the current list
  list biggest = newlist()
  int target = b.last()[1]
  for(tuple k in a)
    if (k[0] == target)
      list n = sortTupleList(a.remove(k), b.add(k))
      if(n.size > biggest.size())
        biggest = n
      end if
    end if
  end for
  if (biggest == emptylist)
    return b
  else
    return biggest
end function


list function caller(list a)
  list b = newlist()
  b.add(12-8)
  a.remove(12-8)
  return sortTupleList(a,b)
end function

此函数将测试从 12-8 开始的每个模式并比较它们的大小