最大兼容项个数筛选

sequencing

有1-12,12个数，同一行的两个数表示不能同时出现，如第一行表示1出现10就不能出现，

1. 1       10
   
2. 11      10
   
3. 11      12
   
4. 11      2
   
5. 2       12
   
6. 3       1
   
7. 5       1
   
8. 7       6
   
9. 8       1
   
10. 9       4
    
11. 9       7
    

复制代码

现在需要获取最大个数的可以同时出现的数字，没说清楚的地方大家再挑刺

lkk2003rty

出现数字的范围没有要求？

dzhxc

楼主的意思是说，出现的数字范围内？

lkk2003rty

每个数字作为一个节点 如果这个数字与其他数字能够同时出现 就有一条通路
由此组成一张图
问题转化为求图中 最长路径的一条通路
也就是最大割问题

sequencing

回复 2# lkk2003rty


    您的范围是什么意思，这里的不兼容的项是一对一的，如1-10,3-1,5-1，是不连续的，不是范围

lkk2003rty

回复 5# sequencing


    有多少个数字 可以用于按照你给出的条件来选择啊 这就是范围

sequencing

楼主的意思是说，出现的数字范围内？
dzhxc 发表于 2011-05-09 16:53

    是就这些数字

sequencing

回复 6# lkk2003rty


    1-12，12个

dzhxc

1. [root@bill cu]# cat 12num.txt
   
2. 1       10
   
3. 11      10
   
4. 11      12
   
5. 11      2
   
6. 2       12
   
7. 3       1
   
8. 5       1
   
9. 7       6
   
10. 8       1
    
11. 9       4
    
12. 9       7
    
13. [root@bill cu]# cat num.sh
    
14. #!/bin/bash
    
15. 
    
16. for i in `seq 1 12`
    
17. do
    
18.   cat 12num.txt|while read line
    
19.   do
    
20.     a=`echo $line|awk '{print $1}'`
    
21.     b=`echo $line|awk '{print $2}'`
    
22.     [ $a -eq $i ] && echo "$b" >> $i.tmp
    
23.     [ $b -eq $i ] && echo "$a" >> $i.tmp
    
24.   done
    
25.   for j in `seq 1 12`
    
26.   do
    
27.     cat $i.tmp | egrep "\b$j\b" >> /dev/null
    
28.     [ $? -ne 0 ] && echo "$i and $j"
    
29.   done
    
30.   rm -rf $i.tmp
    
31. done
    
32. [root@bill cu]# sh num.sh
    
33. 1 and 1
    
34. 1 and 2
    
35. 1 and 4
    
36. 1 and 6
    
37. 1 and 7
    
38. 1 and 9
    
39. 1 and 11
    
40. 1 and 12
    
41. 2 and 1
    
42. 2 and 2
    
43. 2 and 3
    
44. 2 and 4
    
45. 2 and 5
    
46. 2 and 6
    
47. 2 and 7
    
48. 2 and 8
    
49. 2 and 9
    
50. 2 and 10
    
51. 3 and 2
    
52. 3 and 3
    
53. 3 and 4
    
54. 3 and 5
    
55. 3 and 6
    
56. 3 and 7
    
57. 3 and 8
    
58. 3 and 9
    
59. 3 and 10
    
60. 3 and 11
    
61. 3 and 12
    
62. ……
    

复制代码

看看是否符合要求？如果要 计数 的话，就重定向一下 wc吧