排列组合问题

rdcwayx

原帖由 doctorjxd 于 2007-4-2 13:44 发表



开始给的mytool是只输出一行，便于在脚本中分行处理。但是每次起一个进程速度很慢。
后来给的C++代码是输出全部的序列。

echo "abaccedf" | ./mytool 在我的机器上显示全部序列用0.21秒。
e ...

是这样啊，那么你的电脑确实不错。跑得很快啊。

rdcwayx

原帖由 doctorjxd 于 2007-4-2 18:28 发表


我的计算机是Celeron(R) CPU 2.53GHz，256M memory.
是两年前配置的。

难道是FreeBSD比Cygwin的Gcc速度快很多？

我的laptop是 Intel core duo processor 1.66Ghz, 1G DDR内存。应该要比你的快，应该是cygwin环境的效率问题。

我用了你的第二个mytool, 运行我的结果，花了5秒不到。用前一个mytool, 要花5分钟以上。后一个的优化效果很好。

特地作了你的那个测试：（因为是Windows 系统下的模拟unix环境，运行该测试程序时，cygwin最高只能用50%的CPU).

size    array   vector with pointers    vector with iterators   deque   list    set     multiset
10      2.17    3.75    4.47    9.36    70.75   11.55   19.98
100     0.78    0.83    1.78    3.16    13.23   6.23    10.36
1000    0.78    0.80    1.58    2.53    7.99    4.75    7.47
10000   0.75    0.73    1.53    2.36    6.39    4.09    6.12
100000  0.69    0.69    1.39    2.06    5.92    4.23    6.08
1000000 0.72    0.72    1.47    2.17    7.50    5.56    7.28

rdcwayx

原帖由 doctorjxd 于 2007-4-2 11:54 发表
求全排列的程序

#include <vector>
#include <iterator>
#include <algorithm>

int main()
{
  using namespace std;
  typedef vector<char> vec_char;
  vec_char thestr;
  copy(istream_iterator<char>(cin),istream_iterator<char>(),back_insert_iterator<vec_char>(thestr));
  sort(thestr.begin(),thestr.end());
  while(next_permutation(thestr.begin(),thestr.end()))
  {
     copy(thestr.begin(),thestr.end(),ostreambuf_iterator<char>(cout));
     cout << endl;
  }
  return 0;
} ...

还有，这个程序的输出结果还是同长度排列， 并不是全排列，也就是得到任意单个字母，两个，三个。。。到全部字母排列组合。

rdcwayx

好像来晚了，只能再等等。博士兄辛苦了。

rdcwayx

这次全都可以了。谢谢大家。尤其是谢谢doctorjxd

rdcwayx

不怕，就怕大家不来灌水。我对代码没有太大要求，只要能解决我的问题就好。

“不管黑猫，白猫，能抓老鼠的就是好猫”

[ 本帖最后由 rdcwayx 于 2007-4-4 19:07 编辑 ]

rdcwayx

现在,我来做个总结. 我当时的目的就是要做个jumble的解题游戏。大家可以参考这个网站（http://www.jumble.org）他的解题速度奇快，而且后面的词汇量很大。这个网站比较专业。

Jumble游戏，就是给出任意的几个英文字母，看看是否可以组成一个英语单词。因为通常4个单词以内的，比较容易，7个单词以上的太难，我就想试着用shell 做个程序，能够解出5~7个字母的英语单词。用了doctorjxd的程序后，我试验成功，特地上传上来，大家可以试一下。

将上传的文件，解压后，放在同一个目录下。

给几个运行例子

jumble arbox
jumble rufor
jumble bittid

[ 本帖最后由 rdcwayx 于 2007-4-17 12:55 编辑 ]

rdcwayx

第二个应用程序稍微不同。给出7个字母，试着用里面最多的字母组成一个英语单词。7个分数最高，6个，5格都可以。

这个游戏叫 WordScrimmage, 大家可以参考这个网站 （http://www.featurebank.com/?title=Samples:WORDScrimmage%20(R)）

我用doctorjxd 提供的第二段老外的一个经典程序，做成另一个小程序。专门用来解WordScrimmage

将所有的程序解压后，放在同一目录。

给几个运行例子

jumble loanppl
jumble uildiar
jumble teanstb
jumble nltrsey

[ 本帖最后由 rdcwayx 于 2007-4-17 13:52 编辑 ]

rdcwayx

找到一个简单的jumble方案 ，但是效率很差。

echo {e,x,p,e,c,t}{e,x,p,e,c,t}{e,x,p,e,c,t}{e,x,p,e,c,t}{e,x,p,e,c,t}{e,x,p,e,c,t} |xargs -n1 |xargs -i grep -x {} /usr/dict/words