排列成对的数字，使相邻成对的成员相等
排列成对的数字，使相邻成对的成员相等
提问于 2016-09-05 01:33:07
我想安排以下项目，形成最长的链，从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
我如何为这个任务写一个合适的排序算法？
回答 4
Stack Overflow用户
发布于 2016-09-05 02:09:39
您需要递归，但它可能不适用于更大的数据集:如下所示。
免责声明:这可能不是最优化的解决方案(复杂度为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开始的每个单独的模式，并比较它们的大小
Stack Overflow用户
发布于 2016-09-05 18:30:16
根据问题的大小(平铺的数量)，您可以选择以下方法之一：
1- Bruteforce:你可以使用回溯检查所有可能的瓦片配置，这会导致O(n!)复杂度的算法。
2- Bitmask Dynamic Programming：你可以在位掩码的帮助下使用动态编程来减少搜索空间。这种方法将导致O(2^n * n)算法的产生。
Stack Overflow用户
发布于 2016-09-10 02:12:43
把数字看作是图的顶点，把对看作是图的边(所以可能有一些多边)。现在，您的问题简化为在图中寻找顶点(而不是边)可能重复的最长路径。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/39319661
复制相关文章
相似问题
腾讯云开发者
