This website requires Javascript to function properly. Please go to the setting of your web browser and enable Javascript for this website.

Ad by

推荐 OXIO 加拿大高速网络，最低月费仅$40. 使用推荐码 RCR37MB 可获得一个月的免费服务

Ad by

推荐 OXIO 加拿大高速网络，最低月费仅$40. 使用推荐码 RCR37MB 可获得一个月的免费服务

So, from my understanding, any nodes with same root and same degree can be group together and the order between them is not important. The simplest algorithm in my mind will be, see if it works :

goes(goes)

Create a empty hashtable H which stores degree of nodes, kind of dynamic programming.

Say your Arraylist is A, the result Arraylist will be B, the sub-result will be B1, B2,...Bn

1. Pick up any element a1 from A, remove it from A and put it into B1.
scan A get the a1's parent(remove it and put it to B1) until it reaches the root a1Root,
at same time, store every nodes with it's degree in this path into H.

You get a partial tree B1, any nodes in B1 should be removed from A

2. repeat step 1 to get B2, scan B1 to see if B2's parent is in B1, if it is, combine B1 and B2.

3. repeat step 1 and step2 until A is empty.

4. sort B1,B2,...Bn based on the degree of each nodes(COMPARATOR, get degree from H)

5. group B1,B2,...Bn to B

remember:
orphaned node is a tree as well, if you want the orphan to be the end of the list, check the size when grouping.

(#1787075@0)
Last Updated: 2004-7-2
This post has been archived. It cannot be replied.

Report

Replies, comments and Discussions:

工作学习 / IT技术讨论 / 请问如何这样SORT一个ARRAYLIST -tongcd(Rock Your Body); 2004-7-1 {685} (#1786302@0)
这个ARRAYLIST 里的OBJECT都有两个ID，一个是FROMID，一个是TOID，基本上来说就是一个父ID，一个子ID，一个父结点可能有多
个子节点，一个子节点也可能有多个父结点，也可能有ORPHAN NODE，但不会有环形。我希望SORT以后的ARRAY是：
1）如果O1的FROMID是O2的TOID，那么O1派在O2前边；
2）如果O1的FROMID和O2的FROMID相等，那么O1等于O2；
3）如果O1的TOID和O2的TOID相等，那么O1等于O2；
4）如果是ORPHAN NODE的话，就放在最后，当然如果存在多个树的话，两个基本点树的相待位置不要紧，就是说谁放谁前面都没关系
5）当然，如果O1的子孙是O2的父亲，那么O1要排在O2前面；

如果用COMPARATOR的话，前面1，2，3都容易解决，但是4，5我就不知道怎么有效的解决，哪位给个提示？我已经有点一脑子浆糊了，写的东西总有问题。
多谢了。

Don't stick to COMPARATOR any more. Using only COMPARATOR will not solve your problem for sure. It's used for single 1-ary tree, but you are trying to apply it to multi non-1-ary trees. -goes(goes); 2004-7-1 {86} (#1786508@0)
It should not be too hard to write your own algorithm and the complexity is about n*n.

thanks for reply. I know it has something to do with tree, but it is not exactly same as tree. Can you say more about the algorithm, please? -tongcd(Rock Your Body); 2004-7-1 (#1786534@0)

Did your requirement cover this case? O1 and O2 are sibling. O3 is child of O1, O4 is child of O2. O3 and O4 do not have common children. what's the order of O3 and O4? -goes(goes); 2004-7-1 (#1786638@0)

if o1 is sibling of o2, then it doesn't matter if o1 is listed before/after o2. if O3 is child of O1, O4 is child of O2. O3 and O4 do not have common children, then the order could be o1->o2->o3_o4 or o1->o2->o4->o3. -tongcd(Rock Your Body); 2004-7-2 {182} (#1786926@0)
In this case, the relative order of o1 and o2 doesn't matter, as long as they are all listed before o3,o4. Same, the relative order of o3,o4 is not import important as well.
Thanks

So, from my understanding, any nodes with same root and same degree can be group together and the order between them is not important. The simplest algorithm in my mind will be, see if it works : -goes(goes); 2004-7-2 {898} (#1787075@0)
Create a empty hashtable H which stores degree of nodes, kind of dynamic programming.

Say your Arraylist is A, the result Arraylist will be B, the sub-result will be B1, B2,...Bn

1. Pick up any element a1 from A, remove it from A and put it into B1.
scan A get the a1's parent(remove it and put it to B1) until it reaches the root a1Root,
at same time, store every nodes with it's degree in this path into H.

You get a partial tree B1, any nodes in B1 should be removed from A

2. repeat step 1 to get B2, scan B1 to see if B2's parent is in B1, if it is, combine B1 and B2.

3. repeat step 1 and step2 until A is empty.

4. sort B1,B2,...Bn based on the degree of each nodes(COMPARATOR, get degree from H)

5. group B1,B2,...Bn to B

remember:
orphaned node is a tree as well, if you want the orphan to be the end of the list, check the size when grouping.

This is something I was thinking about. It looks ok except its compelxity. please read #1787443, thank you -tongcd(Rock Your Body); 2004-7-2 (#1787446@0)

It is tree not array. so, use tree instead of array. -ra_95(小人-生命换来的金钱); 2004-7-2 (#1786834@0)

yes, I know it looks quite like a tree instead of a 1-dimention array, but -tongcd(Rock Your Body); 2004-7-2 {316} (#1786927@0)
there are may be more than 1 tree.
there could have orphaned node.
same child could have more than 1 parent and there are NO circular, which means the root node chould be more than 1.
Finally, to change everything into a tree would impact the existing code a lots, which is something I can't afford now.
thanks

still use comparator la. 4 should be simple. 5 use a hui2shuo4; if we do not care performance -ra_95(小人-生命换来的金钱); 2004-7-2 {101} (#1787215@0)
a=o1
loop
a = a's dad
if it is o1 --> circle assert fails.
if it is o2; return o1<o2
end loop

I re-visit my post, I didn't say it clearly. Please read #1787443, thank you. -tongcd(Rock Your Body); 2004-7-2 (#1787449@0)

thanks goes and ra_95 for spending time help me solve this problem. I found solution from net.The sorting I am looking for is called topological sort or dag sorting. The attached reading says all. -tongcd(Rock Your Body); 2004-7-2 (#1787443@0)

@Florida

So, from my understanding, any nodes with same root and same degree can be group together and the order between them is not important. The simplest algorithm in my mind will be, see if it works :

Replies, comments and Discussions:

More Topics