排列组合问题

rdcwayx

我想在任意给出的7 个字母(任意的26个英语字母，比如 a c r d m a g)，里面任意选择6个或者7个组成不重复的所有排列组合。

其中给出的字母可以有重复。

更新: 看第六页,有个总结.

jumble游戏 在51楼
WordScrimmage游戏在52楼

doctorjxd

先解决排列问题：  编译后用法 echo "yourstring" | mytool, 可以循环排出，直至返回空。

1. 
   
2. 
   
3. #include <iostream>
   
4. #include <vector>
   
5. #include <iterator>
   
6. #include <algorithm>
   
7. 
   
8. int main()
   
9. {
   
10.   using namespace std;
    
11.   typedef vector<char> vec_char;
    
12.   vec_char thestr;
    
13.   copy(istream_iterator<char>(cin),istream_iterator<char>(),back_insert_iterator<vec_char>(thestr));
    
14.   if(next_permutation(thestr.begin(),thestr.end()))
    
15.     copy(thestr.begin(),thestr.end(),ostream_iterator<char>(cout));
    
16.   else
    
17.     return -1;
    
18.   return 0;
    
19. }
    
20. 
    

复制代码

[ 本帖最后由 doctorjxd 于 2007-3-31 11:17 编辑 ]

doctorjxd

例如取完组合后：

1. 
   
2. #!/bin/sh
   
3. 
   
4. ...
   
5. 
   
6. #比如是good
   
7. mystring="good"
   
8. 
   
9. #排序处理
   
10. mystring=`echo $mystring  | sed 's/\(.\)/\1\
    
11. /g;s/\n$//;' | sort | sed -n -e :a -e 'N;$!ba' -e 's/\n//g;p;'`
    
12. 
    
13. #处理排列
    
14. while [ ! -z $mystring ]
    
15. do
    
16.   #显示或其他处理
    
17.   echo $mystring
    
18.   #调用自己的工具
    
19.   mystring=`echo $mystring | ./mytool`
    
20. done
    

复制代码

[ 本帖最后由 doctorjxd 于 2007-3-31 12:02 编辑 ]

rdcwayx

非常感谢，这个程序非常精简，而且完全达到了我的要求。

只是有个问题： 运行这个语句的时候， 放在程序里，没有输出结果，但是单独在/bin/sh下执行的时候，输出很正常。

mystring=`echo $mystring  | sed 's/\(.\)/\1\
/g;s/\n$//;' | sort | sed -n -e :a -e 'N;$!ba' -e 's/\n//g;p;'`

echo $mystring

awk就是awp加ak

我有个非常笨的办法~ ^_^

1. 
   
2. seq 10000 100000 |sed '/[0-4]/d;/\(.\).*\1/d' |awk '
   
3. BEGIN { split("aefgh", gTable, ""); }
   
4. { split($0, arr, ""); for (idx in arr) printf gTable[arr[idx]-4]; printf "\n";}
   
5. '

复制代码

awk就是awp加ak

哦，没看题。。给出的字母可以重复阿

rdcwayx

原帖由 awk就是awp加ak 于 2007-3-31 15:41 发表
哦，没看题。。给出的字母可以重复阿

没关系，但是也要谢谢。

用doctorjxd 的方法，我只能每次先将字母顺序排列好，也就是跳过那条我碰到问题的语句。但是现在至少已经可以解决我的问题了。

大家知道那条语句为何不能在脚本里执行吗？

doctorjxd

原帖由 rdcwayx 于 2007-3-31 14:18 发表
非常感谢，这个程序非常精简，而且完全达到了我的要求。

只是有个问题： 运行这个语句的时候， 放在程序里，没有输出结果，但是单独在/bin/sh下执行的时候，输出很正常。

mystring=`echo $mystring  | sed  ...

不客气，呵呵。
试试这个,把``改成$(....)就行了。

1. 
   
2. 
   
3. mystring=$(echo $mystring  | sed 's/\(.\)/\1\
   
4. /g;s/\n$//;' | sort | sed -n -e :a -e 'N;$!ba' -e 's/\n//g;p;')
   
5. 
   
6. 
   

复制代码

rdcwayx

原帖由 doctorjxd 于 2007-3-31 16:30 发表


不客气，呵呵。
试试这个,把``改成$(....)就行了。

1. 
   
2. 
   
3. mystring=$(echo $mystring  | sed 's/\(.\)/\1\
   
4. /g;s/\n$//;' | sort | sed -n -e :a -e 'N;$!ba' -e 's/\n//g;p;')
   
5. 
   
6. 
   

复制代码

再次感谢，这次成功了。

awk就是awp加ak

想到一种更令人抓狂的方法，没试验~

1. seq 10000 100000 |sed '/[0-4]/d;/\(.\).*\1/d' |awk '
   
2. BEGIN { split("aefgh", gTable, ""); }
   
3. {
   
4.     split($0, arr, "");
   
5.     for (idx in arr) printf gTable[arr[idx]-4];
   
6.     printf "\n";
   
7. }' |sed 's,g,a,' |sort -u
   

复制代码