Board logo

标题: 字符串全排列 [打印本页]

作者: happy886rr    时间: 2017-4-7 21:08     标题: 字符串全排列

本帖最后由 happy886rr 于 2017-4-8 09:38 编辑

字符串 def 的全排列为:def、dfe、edf、efd、fde、fed。那么字符串bathome的全排列是?
(不限编程语言,能输出正确的全排列即可,代码越少越好。)

示例代码: C
  1. #include <stdio.h>
  2. #include <string.h>
  3. void swap(char *a, char *b)
  4. {
  5.       char tmp = *a;
  6.       *a = *b;
  7.       *b = tmp;
  8. }
  9. void arrange(char *str, int start, int end)
  10. {
  11.       int i;
  12.       if(start == end)
  13.       {
  14.             printf("%s\n",str);
  15.       }else{
  16.             for(i = start; i < end; i++)
  17.             {
  18.                   swap(str+start,str+i);
  19.                   arrange(str,start+1,end);
  20.                   swap(str+start,str+i);
  21.             }
  22.       }
  23. }
  24. int main(void)
  25. {
  26.       char str[10]="bathome";
  27.       int len = strlen(str);
  28.       arrange(str,0,len);
  29.       return 0;
  30. }
复制代码
示例代码: js混编
  1. 1>1/* :
  2. @echo off
  3. cscript -nologo -e:jscript "%~f0"  %*
  4. pause&exit /b
  5. */
  6. permutations('bathome'.split(''));
  7. function permutations(arr)
  8. {  
  9. (function exfn(source, result)
  10. {  
  11. if(source.length == 0){
  12. WSH.echo(result.join(''));
  13. }else{
  14. for (var i=0; i<source.length; i++){
  15. exfn(source.slice(0, i).concat(source.slice(i+1)), result.concat(source[i]));
  16. }
  17. }
  18. })(arr, []);  
  19. }
复制代码

作者: CrLf    时间: 2017-4-7 22:13

每次看到这话题,总想安利一下 plp626 那神一样的纯批解:
http://bbs.bathome.net/redirect. ... 11959&pid=76175
作者: happy886rr    时间: 2017-4-7 23:10

回复 2# CrLf
plp这个也太牛了吧,骨瘦如柴啊。
  1. setlocal&set "s=%~1 "&if "!s: =!" == ""  (echo %~2)else for %%b in (%~1)do call:perm "!s:%%b =!" "%~2 %%b"
复制代码
感觉他是在写诗。
作者: codegay    时间: 2017-4-7 23:28

本帖最后由 codegay 于 2017-4-7 23:40 编辑

我只知道这么写:
python3
  1. from itertools import permutations as pm
  2. for r in pm("bathome"):
  3.     print(''.join(r))
复制代码

作者: codegay    时间: 2017-4-7 23:29

没有内置类库我大约不会写。
作者: happy886rr    时间: 2017-4-7 23:41

回复 5# codegay
非常短,这次代码数你的最短,最好。因为题目不限语言。你几乎胜了。
作者: flashercs    时间: 2017-4-8 00:50

  1. function arrange(str) {
  2.     str = str + '';
  3.     if (str.length <= 1) {
  4.         return [str];
  5.     }
  6.     var aStrRest = arrange(str.slice(1));
  7.     var sFirst = str.charAt(0);
  8.     var item;
  9.     var aReturn = [];
  10.     for (var i = 0, l = aStrRest.length; i < l; i++) {
  11.         item = aStrRest[i];
  12.         for (var j = 0, litem = item.length; j <= litem; j++) {
  13.             aReturn.push(item.slice(0, j) + sFirst + item.slice(j));
  14.         }
  15.     }
  16.     return aReturn;
  17. }
  18. console.log(arrange('bathome').join('\n'));
复制代码

作者: a20150604    时间: 2017-4-8 01:13

本帖最后由 a20150604 于 2017-4-8 02:27 编辑

追求高效的纯批置换算法: 从生成一个元素的全排列, 逐次进阶扩展到 2, 3, .... 个元素, 排除命令行窗口显示耗时, 仅数据生成时间 < 1秒 (i3 处理器)
  1. @echo off & setlocal enabledelayedexpansion & mode 160, 1000
  2. set z=1;
  3. set z
  4. for /L %%j in (2 1 6) do (
  5.     set /a k=%%j-1
  6.     set x=
  7.     for /L %%i in (1 1 !k!) do (
  8.         set t=!z:%%i=%%j!
  9.         set x=!x!!t:;=%%i;!
  10.     )
  11.     set z=!z:;=%%j;!!x!
  12.     set z
  13. )
  14. echo;complete 6
  15. REM 7个元素的全排列用带分隔符的单变量存储超出批处理变量存储极限, 只能另行处理
  16. REM 数字形式
  17. REM echo;!z:;=7;!
  18. REM for /L %%i in (1 1 6) do (
  19.     REM set t=!z:%%i=7!
  20.     REM echo;!t:;=%%i;!
  21. REM )
  22. set t7=!z:;=e;!
  23. for /L %%i in (1 1 6) do (
  24.     set t%%i=!z:%%i=e!
  25.     set t%%i=!t%%i:;=%%i;!
  26. )
  27. for /L %%i in (1 1 7) do (
  28.     for %%Q in (1:b 2:a 3:t 4:h 5:o 6:m) do for /f "tokens=1-2 delims=:" %%W in ("%%Q") do set t%%i=!t%%i:%%W=%%X!
  29.     echo;!t%%i:;= !
  30. )
  31. echo;complete 7
  32. pause
  33. exit
复制代码

作者: a20150604    时间: 2017-4-8 01:52

本帖最后由 a20150604 于 2017-4-8 02:56 编辑

Wolfram 语言
  1. Permutations[{b,a,t,h,o,m,e}]
复制代码
格式处理一下
  1. StringJoin /@ Permutations[Characters["bathome"]]
复制代码

作者: codegay    时间: 2017-4-8 04:42

最近论坛新来的几个ID技术都很不错啊。
作者: flashercs    时间: 2017-4-8 06:59

  1. @echo off
  2. REM %str%为要排列的字符串,但不能含"^
  3. set "str=|&<>bat"
  4. call :arrange "%str%"
  5. pause
  6. exit /b
  7. :arrange
  8. setlocal
  9. set "s=%~1"
  10. if not defined s (
  11.     call :escape "%~2"
  12.     call echo,%%r%%
  13.     goto end
  14. )
  15. set /a "n=0"
  16. :loop
  17. set /a "m=n+1"
  18. call set "pre=%%s:~%n%,1%%"
  19. call set "rest=%%s:~,%n%%%%%s:~%m%%%"
  20. if not defined pre goto end
  21. call :arrange "%rest%" "%~2%pre%"
  22. set /a "n+=1"
  23. goto loop
  24. :end
  25. endlocal
  26. exit /b
  27. :escape
  28. set "r=%~1"
  29. set "r=%r:^=^^%"
  30. set "r=%r:&=^&%"
  31. set "r=%r:|=^|%"
  32. set "r=%r:<=^<%"
  33. set "r=%r:>=^>%"
  34. set "r=%r:"=^"%"
  35. exit /b
复制代码

作者: happy886rr    时间: 2017-4-8 08:57

回复 10# codegay
藏龙卧虎啊,你不出点题,他们怎能显山露水。
作者: pcl_test    时间: 2017-4-8 09:16

本帖最后由 pcl_test 于 2017-4-8 09:30 编辑
  1. @echo off
  2. powershell ^
  3. function perm($str, $t){^
  4. $len=$str.length;^
  5. if($len -le 1){$t+''+$str}else{^
  6. for($i=0; $i -lt $len; ++$i)^
  7. {^
  8. perm ($str.Substring(0, $i)+''+$str.Substring($i+1, $len-$i-1)) ($t+''+$str[$i]);^
  9. }}^
  10. }^
  11. perm 'bathome';
  12. pause
复制代码

作者: flashercs    时间: 2017-4-8 11:01

回复 1# happy886rr


    为什么你这算法的数组操作35ms完成,而我字符串操作7ms完成,为什么数组会慢 这么多?不合理啊!!
作者: 523066680    时间: 2017-4-8 11:20

本帖最后由 523066680 于 2017-4-8 11:24 编辑

挖坟

http://bbs.bathome.net/viewthrea ... p;extra=&page=1

http://bbs.bathome.net/viewthread.php?tid=11959

http://bbs.bathome.net/viewthread.php?tid=8747

以及 plp 的那段代码 可以不要 setlocal enabledelayedexpansion
http://bbs.bathome.net/redirect.php?goto=findpost&ptid=25423&pid=134729
作者: flashercs    时间: 2017-4-8 11:24

回复 14# flashercs


    我明白了,性能差主要是函数调用次数太多,那种算法调用了7的阶乘次函数,而用循环来实现会快很多。我那个调用7次函数,所以快一些,但是应该可以只用循环实现的,就是三个嵌套循环。
作者: 523066680    时间: 2017-4-8 13:02

本帖最后由 523066680 于 2017-4-8 13:20 编辑

C语言已忘光,代码毫无新意
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. void f(char *oldstr, char *newstr, int len, int lv)
  5. {
  6. char *ostr = (char *)malloc( len * sizeof(char) );
  7. for (int i = 0; i < len; i++)
  8. {
  9. strcpy( ostr, oldstr );
  10. newstr[lv] = ostr[i];
  11. newstr[lv+1] = '\0';
  12. if (len == 1)
  13. printf("%s \n", newstr);
  14. for (int j = i; j < (len-1); j++)
  15. ostr[j] = ostr[j+1];
  16. if ( len > 0 )
  17. f( ostr, newstr, len-1, lv+1 );
  18. }
  19. }
  20. int main(int argc, char *argv[])
  21. {
  22. char oldstr[] = "bathome";
  23. char *newstr = (char *)malloc( (strlen(oldstr)+1) * sizeof(char) );
  24. f(oldstr, newstr, strlen(oldstr), 0);
  25. return 0;
  26. }
复制代码
Perl (不借用外部模块)
  1. my @cup;
  2. my @nums;
  3. our $len;
  4. @nums = (split("", "bathome"));
  5. $len = $#nums+1;
  6. &func(\@cup, \@nums);
  7. sub func
  8. {
  9.     my ($a, $b) = (shift, shift);
  10.     my @ar;
  11.     my @br;
  12.    
  13.     print join(",", @{$a}),"\n" if ( scalar(@{$a}) == $len );
  14.     for my $i ( 0 .. $#{$b} )
  15.     {
  16.         @ar = (@{$a}, $b->[$i]);
  17.         @br = @{$b}[0..$i-1, $i+1..$#{$b}];
  18.         &func(\@ar, \@br);
  19.     }
  20. }
复制代码
以下拷贝自《High-Order Perl》
  1. sub permute
  2. {
  3. my @items = @{ $_[0] };
  4. my @perms = @{ $_[1] };
  5. unless (@items)
  6. {
  7. print join("", @perms) ,"\n";
  8. }
  9. else
  10. {
  11. my(@newitems,@newperms,$i);
  12. for $i (0 .. $#items)
  13. {
  14. @newitems = @items;
  15. @newperms = @perms;
  16. unshift(@newperms, splice(@newitems, $i, 1));
  17. permute([@newitems], [@newperms]);
  18. }
  19. }
  20. }
  21. # sample call:
  22. permute([qw(b a t h o m e)], []);
复制代码
《High-Order Perl》里面有更有趣的思路,午休,有空再更
作者: happy886rr    时间: 2017-4-8 14:52

回复 16# flashercs

你的速度确实蛮快,但是那个批处理版就很慢了。
作者: 523066680    时间: 2017-4-8 15:34

本帖最后由 523066680 于 2017-4-8 16:50 编辑

Here's a little program that generates all permutations of all the words
on each line of input. The algorithm embodied in the "permute()"
function is discussed in Volume 4 (still unpublished) of Knuth's *The
Art of Computer Programming* and will work on any list:
  1. #!/usr/bin/perl -n
  2. # Fischer-Krause ordered permutation generator
  3. sub permute (&@) {
  4.     my $code = shift;
  5.     my @idx = 0..$#_;
  6.     while ( $code->(@_[@idx]) ) {
  7.         my $p = $#idx;
  8.         --$p while $idx[$p-1] > $idx[$p];
  9.         my $q = $p or return;
  10.         push @idx, reverse splice @idx, $p;
  11.         ++$q while $idx[$p-1] > $idx[$q];
  12.         @idx[$p-1,$q]=@idx[$q,$p-1];
  13.     }
  14. }
  15. permute { print "@_\n" } split;
复制代码
来自 perldoc -q permute, 调用示例:echo a b c | permute.pl
刚开始真没看懂,蜜汁语法 ……
只看出来说是 knuth 在 计算机程序设计艺术 卷4 里面提到的算法,该书还未出版。

待会儿再更
作者: a20150604    时间: 2017-4-8 15:54

8 楼置换算法的 JS 和 VBS 版

JS
  1. Z = "1;";
  2. for( j = 2; j <= 7; j++ ) {
  3.     t = Z;
  4.     Z = Z.replace(/;/g, j + ";")
  5.     for ( i = 1; i <= j - 1; i++ ) Z = Z + t.replace(RegExp(i, "g"), j).replace(/;/g, i + ";");
  6. }
  7. for( i = 1; i <= 7; i++ ) Z = Z.replace(RegExp(i, "g"), "bathome".substr(i - 1, 1));
  8. console.log(Z);
复制代码
VBS
  1. Z = "1;"
  2. For j = 2 To 7
  3.     t = Z
  4.     Z = Replace(Z, ";", j & ";")
  5.     For i = 1 To j - 1
  6.       Z = Z & Replace(Replace(t, i, j), ";", i & ";")
  7.     Next
  8. Next
  9. For i = 1 To 7
  10.     Z = Replace(Z, i, Mid("bathome", i, 1))
  11. Next
  12. WScript.Echo Z
复制代码

作者: a20150604    时间: 2017-4-8 16:35

http://www.cs.utsa.edu/~wagner/knuth/

Donald E. Knuth  
  The Art of Computer
Programming
Volume 4,
Combinatorial Algorithms
作者: 523066680    时间: 2017-4-8 17:54

本帖最后由 523066680 于 2017-4-8 20:28 编辑

解读和代码转C,主要是有一个数字调换的规律
  1. /* Translate by 523066680@163.com */
  2. #include <stdio.h>
  3. void splice_and_reverse( int *arr, int p, int ubound )
  4. {
  5. int t;
  6. for (int i = p; i <= (ubound+p)/2 ; i++ )
  7. {
  8. t = arr[i];
  9. arr[i] = arr[ubound - i + p];
  10. arr[ubound - i + p] = t;
  11. }
  12. }
  13. void exchange(int *arr, int a, int b)
  14. {
  15. int t;
  16. t = arr[a];
  17. arr[a] = arr[b];
  18. arr[b] = t;
  19. }
  20. void print_array(int *arr, int ubound)
  21. {
  22. for (int i = 0; i <= ubound; i++)
  23. printf("%d", arr[i]);
  24. printf("\n");
  25. }
  26. int main(int argc, char *argv[] )
  27. {
  28. int arr[] = {0, 1, 2, 3};
  29. int ubound = sizeof(arr) / sizeof(arr[0]) - 1;
  30. int p, q;
  31. while (1)
  32. {
  33. p = ubound;
  34. //p 递减,直到 当前元素 > 上一个元素 ,上一个元素记为 N
  35. while ( arr[p-1] > arr[p] ) p--;
  36. if ( p <= 0 ) break;
  37. q = p;
  38. //反转 从 p 至 末尾的元素
  39. splice_and_reverse( arr, p, ubound );
  40. //q 递增,直到当前元素 > N
  41. while ( arr[p-1] > arr[q] ) q++;
  42. //交换
  43. exchange(arr, p-1, q);
  44. //打印结果
  45.     print_array(arr, ubound);
  46. }
  47.     return 0;
  48. }
复制代码
有了这一个规则,我们可以 通过某个中间的排列得出下一个结果:

举一个 6 位的
arr[] = 5 3 4 2 1 0

arr[] = 5 4 0 1 2 3
作者: taofan712    时间: 2017-4-10 10:50

  1. @echo off & setlocal enabledelayedexpansion
  2. set "str[0]= b a t h o m e"
  3. set tm1=%time%
  4. for %%a in (%str[0]%) do (
  5. set /a n+=1
  6. set /a odr[!n!]=n-1
  7. set var[!n!]=%%~a
  8. )
  9. ::FOR的嵌套递归,借鉴了http://bbs.bathome.net/viewthread.php?tid=1701&extra=&page=2中22楼CrLf的答案。
  10. for /l %%a in (1, 1, %n%) do if not "%%~a"=="%n%" (
  11. set "for=!for!for %%!var[%%~a]! in (^!str[!odr[%%~a]!]^!) do ( set "str[%%~a]=^^^!str[!odr[%%~a]!]: %%~!var[%%~a]!=^^^!" & "
  12. ) else (
  13. set "for=!for!for %%!var[%%~a]! in (^!str[!odr[%%~a]!]^!) do ( "
  14. )
  15. set "for=!for!echo;!str[0]: = %%~!"
  16. for /l %%a in (1, 1, %n%) do set "for=!for!) "
  17. %for%
  18. echo; 始于%tm1% ^
  19. 终于%time%
  20. pause
复制代码

作者: 523066680    时间: 2017-4-10 18:31

回复 10# codegay


    我可是在知乎给论坛打了广告哇 https://www.zhihu.com/question/57102581/answer/152543345
作者: 523066680    时间: 2017-4-26 14:13     标题: 模式计算-迭代法

本帖最后由 523066680 于 2017-5-15 12:35 编辑

编辑/整理:523066680@163.com
日期:2017-05

概念不同模式的生成和换算将模式应用到排列顺序枚举所有情况的代码:[Finished in 0.9s]
作者: CrLf    时间: 2017-4-26 20:43

回复 10# codegay


    何止是不错...我刷完贴只能灰溜溜逃了好吗
作者: 523066680    时间: 2017-5-15 12:00

本帖最后由 523066680 于 2017-5-15 12:41 编辑

Perl 6 (这也太梦幻了)

pythonRuby (也是挺梦幻的)[Finished in 0.2s]
作者: 老刘1号    时间: 2019-3-29 23:33

填坑,汇编递归版
  1. Include masm32rt.inc
  2. .const
  3. CrLf db 0DH,0AH,0
  4. .data?
  5. Input db 20 dup (?)
  6. .code
  7. recursion Proc Uses Ebx Eax Ecx lpStr:dword
  8. Mov Ebx,lpStr
  9. .If Byte Ptr [Ebx+1] != NULL
  10. Mov Al,Byte Ptr [Ebx]
  11. Xor Ecx,Ecx
  12. .Repeat
  13. XChg Al,[Ebx+Ecx]
  14. Mov Byte Ptr [Ebx],Al
  15. Inc Ebx
  16. Invoke recursion,Ebx
  17. Dec Ebx
  18. XChg Al,[Ebx+Ecx]
  19. Mov Byte Ptr [Ebx],Al
  20. Inc Ecx
  21. .Until Byte Ptr [Ebx+Ecx] == NULL
  22. .Else
  23. Invoke StdOut,Offset Input
  24. Invoke StdOut,Offset CrLf
  25. .EndIf
  26. Ret
  27. recursion Endp
  28. Start:
  29. Invoke ArgClC,1,Offset Input
  30. Invoke recursion,Offset Input
  31. Invoke ExitProcess,NULL
  32. End Start
  33. End
复制代码





欢迎光临 批处理之家 (http://bathome.net./) Powered by Discuz! 7.2