字符串全排列

happy886rr

字符串 def 的全排列为：def、dfe、edf、efd、fde、fed。那么字符串bathome的全排列是？
（不限编程语言，能输出正确的全排列即可，代码越少越好。）

示例代码: C

#include <stdio.h>
#include <string.h>

void swap(char *a, char *b)
{
      char tmp = *a;
      *a = *b;
      *b = tmp;
}

void arrange(char *str, int start, int end)
{
      int i;
      if(start == end)
      {
            printf("%s\n",str);

      }else{
            for(i = start; i < end; i++)
            {
                  swap(str+start,str+i);
                  arrange(str,start+1,end);
                  swap(str+start,str+i);
            }

      }
}

int main(void)
{
      char str[10]="bathome";
      int len = strlen(str);
      arrange(str,0,len);
      return 0;
}
复制代码

示例代码: js混编

1>1/* :
@echo off
cscript -nologo -e:jscript "%~f0"  %*
pause&exit /b
*/

permutations('bathome'.split(''));

function permutations(arr)
{  
	(function exfn(source, result)
	{  
		if(source.length == 0){ 
			WSH.echo(result.join('')); 
		}else{ 
			for (var i=0; i<source.length; i++){
				exfn(source.slice(0, i).concat(source.slice(i+1)), result.concat(source[i]));
			} 
		} 
	})(arr, []);  
}
复制代码

CrLf

每次看到这话题，总想安利一下 plp626 那神一样的纯批解：
http://bbs.bathome.net/redirect. ... 11959&pid=76175

happy886rr

回复 2# CrLf
plp这个也太牛了吧，骨瘦如柴啊。

setlocal&set "s=%~1 "&if "!s: =!" == ""  (echo %~2)else for %%b in (%~1)do call:perm "!s:%%b =!" "%~2 %%b"
复制代码

感觉他是在写诗。

codegay

我只知道这么写:
python3

from itertools import permutations as pm

for r in pm("bathome"):
    print(''.join(r))
复制代码

codegay

没有内置类库我大约不会写。

happy886rr

回复 5# codegay
非常短，这次代码数你的最短，最好。因为题目不限语言。你几乎胜了。

flashercs

function arrange(str) {
    str = str + '';
    if (str.length <= 1) {
        return [str];
    }
    var aStrRest = arrange(str.slice(1));
    var sFirst = str.charAt(0);
    var item;
    var aReturn = [];
    for (var i = 0, l = aStrRest.length; i < l; i++) {
        item = aStrRest[i];
        for (var j = 0, litem = item.length; j <= litem; j++) {
            aReturn.push(item.slice(0, j) + sFirst + item.slice(j));
        }
    }
    return aReturn;
}
console.log(arrange('bathome').join('\n'));
复制代码

a20150604

追求高效的纯批置换算法: 从生成一个元素的全排列, 逐次进阶扩展到 2, 3, .... 个元素, 排除命令行窗口显示耗时, 仅数据生成时间 < 1秒 (i3 处理器)

@echo off & setlocal enabledelayedexpansion & mode 160, 1000
set z=1;
set z
for /L %%j in (2 1 6) do (
    set /a k=%%j-1
    set x=
    for /L %%i in (1 1 !k!) do (
        set t=!z:%%i=%%j!
        set x=!x!!t:;=%%i;!
    )
    set z=!z:;=%%j;!!x!
    set z
)
echo;complete 6

REM 7个元素的全排列用带分隔符的单变量存储超出批处理变量存储极限, 只能另行处理
REM 数字形式
REM echo;!z:;=7;!
REM for /L %%i in (1 1 6) do (
    REM set t=!z:%%i=7!
    REM echo;!t:;=%%i;!
REM )

set t7=!z:;=e;!
for /L %%i in (1 1 6) do (
    set t%%i=!z:%%i=e!
    set t%%i=!t%%i:;=%%i;!
)
for /L %%i in (1 1 7) do (
    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!
    echo;!t%%i:;= !
)

echo;complete 7
pause
exit
复制代码

a20150604

Wolfram 语言

Permutations[{b,a,t,h,o,m,e}]
复制代码

格式处理一下

StringJoin /@ Permutations[Characters["bathome"]]
复制代码

codegay

最近论坛新来的几个ID技术都很不错啊。

flashercs

@echo off
REM %str%为要排列的字符串，但不能含"^
set "str=|&<>bat"
call :arrange "%str%"
pause
exit /b
:arrange
setlocal
set "s=%~1"
if not defined s (
    call :escape "%~2"
    call echo,%%r%%
    goto end
)
set /a "n=0"
:loop
set /a "m=n+1"
call set "pre=%%s:~%n%,1%%"
call set "rest=%%s:~,%n%%%%%s:~%m%%%"
if not defined pre goto end
call :arrange "%rest%" "%~2%pre%"
set /a "n+=1"
goto loop
:end
endlocal
exit /b
:escape
set "r=%~1"
set "r=%r:^=^^%"
set "r=%r:&=^&%"
set "r=%r:|=^|%"
set "r=%r:<=^<%"
set "r=%r:>=^>%"
set "r=%r:"=^"%"
exit /b
复制代码

happy886rr

回复 10# codegay
藏龙卧虎啊，你不出点题，他们怎能显山露水。

pcl_test

@echo off
powershell ^
	function perm($str, $t){^
		$len=$str.length;^
		if($len -le 1){$t+''+$str}else{^
		for($i=0; $i -lt $len; ++$i)^
		{^
			perm ($str.Substring(0, $i)+''+$str.Substring($i+1, $len-$i-1)) ($t+''+$str[$i]);^
		}}^
	}^
	perm 'bathome';
pause
复制代码

flashercs

回复 1# happy886rr


    为什么你这算法的数组操作35ms完成，而我字符串操作7ms完成，为什么数组会慢 这么多？不合理啊！！

523066680

挖坟

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