awk 做全排列

最近在逛论坛shell 板块， 发现有一些类似全排列的问题
比如：文本编辑的一点心得--awk篇 http://bbs.chinaunix.net/forum.php?mod=viewthread&tid=1790335&fromuid=29189749

8楼expert1 版主提到的问题
点击(此处)折叠或打开

1. x abcd
   
2. y 0,1
   
3. z a,b,c
   
4. 
   
5. 变成：
   
6. x abcd y 0 z a
   
7. x abcd y 0 z b
   
8. x abcd y 0 z c
   
9. x abcd y 1 z a
   
10. x abcd y 1 z b
    
11. x abcd y 1 z c
    
12. ===================
    
13. 规则：y （0/1） z （a/b/C）有6种情况

当然， 如果给的文本只有这3行， 这并没有啥， 如给改成：

点击(此处)折叠或打开

1. 给一文本， 每行按","分隔，然后按照各行取一个域先后排列，罗列出所有排列组合：
   
2. $cat file
   
3. a
   
4. b,c
   
5. => 排列为
   
6. a b
   
7. a c
   
8. 
   
9. $cat file2
   
10. a,b
    
11. 1,2,3
    
12. m
    
13. => 排列为
    
14. a 1 m
    
15. a 2 m
    
16. a 3 m
    
17. b 1 m
    
18. b 2 m
    
19. b 3 m

这里和上面的例子类似， 只是明确了文本行数不定

点击(此处)折叠或打开

1. 我的思路就是每处理一行时， 就存储该行及该行之前的行的情况， 最后在打印出来
   
2. 比如
   
3. a,b
   
4. 1,2,3
   
5. m
   
6. 
   
7. 处理第一行的时候， 保留a[1,1]=a 和 a[1,2]b
   
8. 处理第二行的时候， 就保留a[2,1]=a 1, a[2,2]=a 2, a[2,3]=a 3, a[2,4]=b 1, a[2,5]=b 2, a[2,6]=b 3
   
9. ...
   
10. 可以发现a[NR,n]是关于a[NR-1,m]的
    
11. 代码：
    
12. awk -F, -vn=1 '{l=split($0,b,",");for(i=1;i<=l;++i)for(k=1;k<=n;++k)a[NR,++m]=a[NR-1,k]b[i] OFS;n=m;m=0}END{for(i=1;i<=n;++i){print a[NR,i]}}'

所以最上面的例子的代码可以很快得出：

点击(此处)折叠或打开

1. awk -vn=1 '{l=split($2,b,",");for(i=1;i<=l;++i)for(k=1;k<=n;++k)a[NR,++m]=a[NR-1,k]$1 FS b[i] FS;n=m;m=0}END{for(i=1;i<=n;++i){print a[NR,i]}}'

这写是通过各行的域来顺序排列的，当然也有按列的顺序来的
又比如， shell能生成数组吗？ http://bbs.chinaunix.net/forum.php?mod=viewthread&tid=4243196&fromuid=29189749

点击(此处)折叠或打开

1. 大意就是：
   
2. 文本有2行，分别代表两个向量， 给出一个步长
   
3. 比如：
   
4. $cat file
   
5. 0 0.75
   
6. 0.25 0
   
7. 
   
8. 给出步长为0.25
   
9. 则要求得到：
   
10. 0 0
    
11. 0 0.25
    
12. 0 0.5
    
13. 0 0.75
    
14. 0.25 0
    
15. 0.25 0.25
    
16. 0.25 0.5
    
17. 0.25 0.75
    
18. 
    
19. 即每列从该列最小值按给定步长递增到不超过最大值，然后给出所有符合条件的组合情况，总共有2*4=8种情况
    
20. 同样， 假如文本是
    
21. $cat file2
    
22. 1 2 1
    
23. 3 2 2
    
24. 
    
25. 配合给的步长为1，则要得出：
    
26. 1 2 1
    
27. 1 2 2
    
28. 2 2 1
    
29. 2 2 2
    
30. 3 2 1
    
31. 3 2 2
    
32. 
    
33. 总共有3*1*2=6种情况，当然，有可能会有重复的

这里按列来全排列的情况与按行的情况类似， 我的思路是先得到每列的最大最小值， 然后得到各列符合条件的元素， 最后来做排列

点击(此处)折叠或打开

1. awk -vv=0.25 '{for(i=1;i<=NF;++i){max[i]=max[i]!=""?(max[i]>$i?max[i]:$i):$i;min[i]=min[i]!=""?(min[i]<$i?min[i]:$i):$i}}END{for(i=1;i<=NF;++i){for(k=min[i];k<=max[i];k+=v)a[i,++n]=k;b[i]=n;n=0}t=1;for(i=1;i<=NF;++i){for(k=1;k<=b[i];++k)for(j=1;j<=t;++j){c[i,++n]=c[i-1,j]a[i,k] FS}t=n;n=0}for(i=1;i<=t;++i)print c[NF,i]}