返回列表 发帖

字符串全排列

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

字符串 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;
}COPY
示例代码: 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, []);  
}COPY
3

评分人数

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

TOP

回复 2# CrLf
plp这个也太牛了吧,骨瘦如柴啊。
setlocal&set "s=%~1 "&if "!s: =!" == ""  (echo %~2)else for %%b in (%~1)do call:perm "!s:%%b =!" "%~2 %%b"COPY
感觉他是在写诗。

TOP

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

我只知道这么写:
python3
from itertools import permutations as pm
for r in pm("bathome"):
    print(''.join(r))COPY
1

评分人数

去学去写去用才有进步。安装python3代码存为xx.py 双击运行或右键用IDLE打开按F5运行

TOP

没有内置类库我大约不会写。
去学去写去用才有进步。安装python3代码存为xx.py 双击运行或右键用IDLE打开按F5运行

TOP

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

TOP

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'));COPY
1

评分人数

TOP

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

追求高效的纯批置换算法: 从生成一个元素的全排列, 逐次进阶扩展到 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
exitCOPY
4

评分人数

TOP

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

Wolfram 语言
Permutations[{b,a,t,h,o,m,e}]COPY
格式处理一下
StringJoin /@ Permutations[Characters["bathome"]]COPY
2

评分人数

    • happy886rr: 真短,貌似你赢了。看看后边的坛友还有更短 ...技术 + 1
    • codegay: 1技术 + 1

TOP

最近论坛新来的几个ID技术都很不错啊。
去学去写去用才有进步。安装python3代码存为xx.py 双击运行或右键用IDLE打开按F5运行

TOP

@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 /bCOPY
1

评分人数

TOP

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

TOP

本帖最后由 pcl_test 于 2017-4-8 09:30 编辑
@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';
pauseCOPY
2

评分人数

TOP

回复 1# happy886rr


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

TOP

[url=][/url]

TOP

返回列表