[出题]如何输出这个关系？

ivhb

数据文件如下

AA|01|AAAA|k1|AA|01|BBBB|
AA|01|AAAA|k1|AB|01|AAAA|
AA|01|AAAA|k1|AA|02|AAAA|
AA|01|AAAA|k1|AC|01|AAAA|
AA|01|BBBB|k2|AA|01|AAAA|
AB|01|AAAA|k3|AA|01|AAAA|
AB|01|AAAA|k3|AB|02|AAAA|
AB|01|AAAA|k3|AC|01|AAAA|
AA|02|AAAA|k4|AA|01|AAAA|
AA|02|AAAA|k4|AB|02|AAAA|
AB|02|AAAA|k5|AB|01|AAAA|
AB|02|AAAA|k5|AA|02|AAAA|
AB|02|AAAA|k5|AB|02|BBBB|
AB|02|BBBB|k6|AB|02|AAAA|
AB|02|BBBB|k6|AC|02|BBBB|
AC|02|BBBB|k7|AB|02|BBBB|
AC|01|AAAA|kk|AA|01|AAAA|
AC|01|AAAA|kk|AB|01|AAAA|
another|test|ok|?||||

要求

# 1,2,3 域唯一标识了一个实体，5,6,7唯一标识了一个实体。
# 一行里面1,2,3和5,6,7表明了朋友关系
# 朋友关系是传递的，就是说，a是b的朋友，c是d的朋友，b是c朋友，那么a,b,c,d都是朋友
# 朋友关系是相互的，a是b的朋友，那么b也是a的朋友。这样，a,b是朋友，a,c是朋友的前提，a,b,c都是朋友
# 如果5,6,7域为空，表明1,2,3域标识的实体没有朋友，属于只有他自己的一个朋友圈。
# 输出朋友圈和其中的所有成员。圈号从1开始编号。
# 输出格式
# 圈1->
# 成员1,成员2,成员3.....
# 圈2->
# 成员1,成员2,成员3.....


1. 不需要输出所有的子圈
2. 看看谁的代码最少

[ 本帖最后由 ivhb 于 2007-10-30 10:42 编辑 ]

ly5066113

如果a 和 c是朋友，b 和 c是朋友，那么a，b，c是不是朋友？
如果已知a，b，c，d是朋友圈，那么输出的时候是否要输出a，b；a，b，c；b，c。。。。。。等子圈。

[ 本帖最后由 ly5066113 于 2007-10-30 10:36 编辑 ]

ivhb

也是朋友

ivhb

原帖由 ly5066113 于 2007-10-30 10:31 发表
如果a 和 c是朋友，b 和 c是朋友，那么a，b，c是不是朋友？
如果已知a，b，c，d是朋友圈，那么输出的时候是否要输出a，b；a，b，c；b，c。。。。。。等子圈。

我已经更新了 题干 和 要求。一开始没有写明白，谢谢提醒了：）

shihk

难！

zongyaotang

还可以简化些，比如只剩两列，以便突出要求的算法。
据我理解这是个依赖关系的问题，如果两列，按每行建立一个目录结构。
有个 tree 来看目录结构。
比如：
a b
c d

a 目录中建个 b 目录
c 目录中建个 d 目录
最后是个关系树。
用 tsort 可以排出 rpm 包的安装次序。

[ 本帖最后由 zongyaotang 于 2007-10-30 11:37 编辑 ]

ly5066113

把源记录简化了一下：

1. $ cat urfile
   
2. a b
   
3. b c
   
4. c d
   
5. e
   
6. f g
   
7. h c
   
8. c i
   
9. a j
   
10. $ cat test.awk
    
11. #!/bin/awk -f
    
12. NR==1{
    
13.         i=1
    
14.         a[i]=$1","$2
    
15. }
    
16. NR>1{
    
17.         if($2==""){
    
18.                 i++
    
19.                 a[i]=$1
    
20.                 next
    
21.         }
    
22.         b=0
    
23.         c=0
    
24.         for(j=1;j<=i;j++){
    
25.                 split(a[j],A,",")
    
26.                 for(k in A){
    
27.                         if($1==A[k])b=1
    
28.                         if($2==A[k])c=1
    
29.                 }
    
30.                 if(b==1&&c==1)next
    
31.                 if(b==0&&c==1){a[j]=a[j]","$1;next}
    
32.                 if(b==1&&c==0){a[j]=a[j]","$2;next}
    
33.         }
    
34.         i++
    
35.         a[i]=$1","$2
    
36. }
    
37. END{
    
38.         n=1
    
39.         for(l in a){
    
40.                 printf "圈%d->\n%s\n" ,n,a[l]
    
41.                 n++
    
42.         }
    
43. }
    
44. $ awk -f test.awk urfile
    
45. 圈1->
    
46. e
    
47. 圈2->
    
48. f,g
    
49. 圈3->
    
50. a,b,c,d,h,i,j
    

复制代码

没写过awk脚本，写的比较罗嗦，但好象能实现需求。

springwind426

1. 
   
2. BEGIN{FS="|"}
   
3. {
   
4. a=$1"|"$2"|"$3;b=$5"|"$6"|"$7;
   
5. fi="";
   
6. for(i in f){
   
7.         a1=index(f[i],a);b1=index(f[i],b);
   
8.         if(a1+b1>0){
   
9.                 if(a1==0) f[i]=f[i]","a;
   
10.                 if(b1==0 && b !="||") f[i]=f[i]","b;
    
11.                 fi=i;
    
12.                 break;
    
13.         }
    
14. }
    
15. if(b=="||")b="";
    
16. if(fi=="")f[i+1]=a "," b;
    
17. }
    
18. END{for(i in f) print "朋友圈" i "->" f[i];}
    

复制代码

寂寞烈火

忒深奥, 看不懂

waker

原帖由 寂寞烈火 于 2007-10-30 13:32 发表
忒深奥, 看不懂

保证完成火哥的看不懂