最大兼容项个数筛选

dzhxc

想简单了……

dzhxc

晕哦，这是个算法问题，和shell关系不大

sequencing

每个数字作为一个节点 如果这个数字与其他数字能够同时出现 就有一条通路
由此组成一张图
问题转化为求图 ...
lkk2003rty 发表于 2011-05-09 16:55

应该是最长路径问题
frewise 发表于 2011-05-09 17:29

算法是很难啊，小毛孩，frewise。。。帮帮忙啊。。。。

lkk2003rty

回复 14# sequencing


    这个我觉得用shell不合适啊 而且最大割问题是一个NP问题。。。要搞的话用用C或者其他的神马吧。。。俺还得去翻以前代码了。。。

sequencing

等等等。。。

yinyuemi

回复 1# sequencing

1. 
   
2. {a[$1":"$2]=1;a[$2":"$1]=1}
   
3. END{
   
4.         for(i=1;i<=12;i++)
   
5.                 {for(j=1;j<=12;j++)
   
6.                         if(a[i":"j]&&i!=j)
   
7.                         s=s?s FS j:j
   
8.                 b[i]=s
   
9.                   s=""
   
10.                 }
    
11.         t="1 2 3 4 5 6 7 8 9 10 11 12 "
    
12.         {for(m=1;m<=12;m++){
    
13.                 x=t;
    
14.                 l=split(b[m],c)
    
15.                 {for(k=1;k<=l;k++)       
    
16.                         x=gensub(c[k] FS,"","1",x)}
    
17.                 for(n=1;n<=12;n++){
    
18.                         if(sub(n FS,n FS,x)&&m!=n){
    
19.                         l=split(b[n],c)
    
20.                         {for(k=1;k<=l;k++)
    
21.                                 x=gensub(c[k] FS,"","1",x)}
    
22.                         }
    
23.                 }
    
24.         print x}
    
25.         }
    
26. }
    
27. 
    
28. 
    
29. awk -f awk.script file
    
30. 
    
31. 1 2 4 6
    
32. 1 2 4 6
    
33. 2 4 6
    
34. 1 2 4 6
    
35. 2 4 6
    
36. 1 2 4 6
    
37. 1 2 4 7
    
38. 2 4 6
    
39. 1 2 6 9
    
40. 2 3 4 5 6 8 10
    
41. 1 4 6 11
    
42. 1 4 6
    

复制代码

blackold

看不懂。

sequencing

回复  sequencing
yinyuemi 发表于 2011-05-10 06:24

    膜拜。。。
大侠能否大致讲下思路，看不太懂，另外结果为什么有重复的行