递归分组问题求解（疑似相似客户分组）

〇〇

难道是np完全问题？

lugionline

开什么玩笑，这个不就是 union find么， 近似于 O(N)， SQL搞不定么就写代码

http://zh.wikipedia.org/wiki/并查集

lastwinner

newkid 发表于 2014-3-21 02:25
其实是一样的，你把第二张表变换一下：

SELECT t1.id id2,t2.id id2

等楼主试验吧
在楼主的表里A联系B，是按单向去看的

newkid

lastwinner 发表于 2014-3-22 01:25
等楼主试验吧
在楼主的表里A联系B，是按单向去看的

哪里体现出单向？比如用户1和2拥有共同号码4, 所以1,2并入一组，1和2之间并没有方向性。

newkid

lugionline 发表于 2014-3-21 08:29
开什么玩笑，这个不就是 union find么， 近似于 O(N)， SQL搞不定么就写代码

http://zh.wikipedia.org/w ...

你来写一个如何？我负责翻译成ORACLE。

ocpdba591

现在数据是这样的：

1.递归没有层级关系，所以就没有方向可言
2.号码没有做限制，所以用户可以随意填写，这样就大大增加了不相干的人成为疑似客户的可能性（这也是我写的那个方法的硬伤所在，随着递归深度的增加，cost也成指数级增长）

期待lugionline给出方法。

lugionline

oracle支持数组耶，你说一个集合语言提供数组，这还有没有下限

T-SQL不支持数组所以我只好用字符串模拟，不过这样比直接查表记录还要慢，转成oracle的数组应当会好点

给客户从1 到N标号，然后用两个数组记录parents 和 rank，然后根据phone表应用union-find，我照着代码转的，看看有没有转错

BTW，如果把里面的stack也翻成数组那就更好了

ocpdba591

lugionline 发表于 2014-3-22 13:35
oracle支持数组耶，你说一个集合语言提供数组，这还有没有下限

T-SQL不支持数组所以我只好用字符串模拟， ...

oracle一直没下限的节奏啊。。。

ocpdba591

能力有限，lugionline兄给的代码表示没看懂，3Q any way...

〇〇

越来越有意思了