排列组合问题

awk就是awp加ak

不行，在BEGIN 里面用的话，貌似得这么写 ^_^
awk -vword="good" 'BEGIN { print word; }'

doctorjxd

如果你只是求若干字母的排列组合，可以用下面的代码编译后： echo "abaccedf" | ./mytool
我的机器上求8个字母的全排列也只要0.91秒。
要是不输出到屏幕上，而是重定向到文件里，比如 echo "abcdefgh" | ./mytool > data.txt
只需要0.16秒

求全排列的程序

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.   sort(thestr.begin(),thestr.end());
    
15.   while(next_permutation(thestr.begin(),thestr.end()))
    
16.   {
    
17.      copy(thestr.begin(),thestr.end(),ostreambuf_iterator<char>(cout));
    
18.      cout << endl;
    
19.   }
    
20.   return 0;
    
21. }
    
22. 
    

复制代码

rdcwayx

很奇怪，你的第一个mytool程序，我只有一行的输出
$ echo "abaccedf" | ./mytool
abaccefd

可能我们的环境不一样。我公司用Solaris.但在自己电脑上用cygwin。

但是你最新的mytool， 我可以得到正常输出。只需3秒左右。

yjh777

原帖由 rdcwayx 于 2007-4-2 07:37 发表


7 9999999
./c1: line 8: 0000008: value too great for base (error token is "0000008"

7个9 输出正确，但是还是有后面的问题。

是取字符串固定位置的字符的操作又用错了，而且应该用7进制，却用成10进制了
今天上班在机器上测了一下：  ：

1. array=(a c r d m a g)
   
2. loop=`perl -e "print 6 x ${#array[@]}"`
   
3. loop=`echo "obase=10; ibase=7; $loop" | bc -l`
   
4. 
   
5. for ((i=1; i<=loop; i++))
   
6. do
   
7.         j=`echo "obase=7; ibase=10; $i" | bc -l`
   
8.         j=`printf %07d $j`
   
9.         echo  ${array[${j:0:1}]} ${array[${j:1:1}]} ${array[${j:2:1}]} \
   
10.               ${array[${j:3:1}]} ${array[${j:4:1}]} ${array[${j:5:1}]} \
    
11.               ${array[${j:6:1}]}
    
12. done #>file
    
13. 
    
14. #sort file | uniq

复制代码

---------------------------------------------------
这样写频繁调用外部命令，效率很低。还是用awk，perl，或像doctorjxd 那样用C写 效率会比较高。

[ 本帖最后由 yjh777 于 2007-4-2 13:30 编辑 ]

doctorjxd

原帖由 rdcwayx 于 2007-4-2 12:47 发表
很奇怪，你的第一个mytool程序，我只有一行的输出
$ echo "abaccedf" | ./mytool
abaccefd

可能我们的环境不一样。我公司用Solaris.但在自己电脑上用cygwin。

但是你最新的mytool， 我可以得到 ...

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

echo "abaccedf" | ./mytool 在我的机器上显示全部序列用0.21秒。
echo "abaccedf" | ./mytool > result.txt 花0.05秒。
但是 cat result.txt 也花0.20 秒。 说明时间主要花在IO上。

我用的是FreeBSD。

rdcwayx

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



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

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

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

Iambitious

1. public boolean nextPermutation(int[] a) {
   
2.                 int i, j;
   
3.                 for (i = a.length - 1; i > 0; i--) {
   
4.                         if (a[i] > a[i - 1]) {
   
5.                                 break;
   
6.                         }
   
7.                 }
   
8.                 i--;
   
9.                 if (i == -1)
   
10.                         return false;
    
11.                 for (j = a.length - 1; j >= 0; j--) {
    
12.                         if (a[j] > a[i])
    
13.                                 break;
    
14.                 }
    
15.                 int t = a[j];
    
16.                 a[j] = a[i];
    
17.                 a[i] = t;
    
18.                 for (i = i + 1, j = a.length - 1; i < j; i++, j--) {
    
19.                         t = a[i];
    
20.                         a[i] = a[j];
    
21.                         a[j] = t;
    
22.                 }
    
23.                 return true;
    
24.         }

复制代码

doctorjxd

还是模板的效率高

1. 
   
2. 
   
3.   template<typename _BidirectionalIterator>
   
4.     bool
   
5.     next_permutation(_BidirectionalIterator __first,
   
6.                      _BidirectionalIterator __last)
   
7.     {
   
8.       // concept requirements
   
9.       __glibcxx_function_requires(_BidirectionalIteratorConcept<
   
10.                                   _BidirectionalIterator>)
    
11.       __glibcxx_function_requires(_LessThanComparableConcept<
    
12.             typename iterator_traits<_BidirectionalIterator>::value_type>)
    
13.       __glibcxx_requires_valid_range(__first, __last);
    
14. 
    
15.       if (__first == __last)
    
16.         return false;
    
17.       _BidirectionalIterator __i = __first;
    
18.       ++__i;
    
19.       if (__i == __last)
    
20.         return false;
    
21.       __i = __last;
    
22.       --__i;
    
23. 
    
24.       for(;;)
    
25.         {
    
26.           _BidirectionalIterator __ii = __i;
    
27.           --__i;
    
28.           if (*__i < *__ii)
    
29.             {
    
30.               _BidirectionalIterator __j = __last;
    
31.               while (!(*__i < *--__j))
    
32.                 {}
    
33.               std::iter_swap(__i, __j);
    
34.               std::reverse(__ii, __last);
    
35.               return true;
    
36.             }
    
37.           if (__i == __first)
    
38.             {
    
39.               std::reverse(__first, __last);
    
40.               return false;
    
41.             }
    
42.         }
    
43.     }
    
44. 
    
45. 
    

复制代码

yjh777

这个帖可以转到 C/C++ 版了，名为排列组合算法。

doctorjxd

原帖由 rdcwayx 于 2007-4-2 13:59 发表


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

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

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