Solved Generate all possible unique permutations of given string

May 17, 2013 at 07:25:24
Specs: Windows 7
How would this be possible in batch?
E.g if a string inputted is abb the total number of different permutations is 8 which are:
aaa
bbb
abb
bab
bba
aab
aba
baa


How would this be possible to code in batch?
To generate all the possible unique permutations of a given string like the example given above?
I thought of it but couldn't come up with an efficient method, since it would have to change depending on the number of characters.


See More: Generate all possible unique permutations of given string

Report •


✔ Best Answer
May 31, 2013 at 16:44:50
Ha ha! you got me! :-D Since you are still with us, here's the "other" version that allows repeats:
:: this one does all the permutations, allowing repeats: 00,01,10,11
@echo off & setlocal enabledelayedexpansion
:: this one does all the permutations, allowing repeats: 00,01,10,11
set e=
:: foll.is NOT the length of output string, it's the allowable char. set.
set /p e=char. set:
if not defined e goto :eof
set ee=
set r=0
call :xx %e%
set /a len=r-1
set r=
set e=%ee%
if not defined e goto :eof
set q=0
set /p q=length of output string:
if q lss 1 goto :eof
:: q needs to be adjusted to one less than what you really want, so...
set /a q-=1
>>strings echo ======= %~n0.bat =========
call :aa
goto :eof

:aa
@echo off & setlocal
@set z=%1
@for /L %%a in (0,1,%len%) do @(
@rem these next 8 at-signs are not really necessary, but I put them anyway.
@set zz=%z%!e:~%%a,1!
@call :xx !zz!
@if !p! leq %q% @(
@call :aa !zz!
) else @(
@>> strings echo %z%
@goto :eof
)
)
goto :eof

:XX
@echo off
@set p=0
@set xx=%1
:x1
@set x=!xx:~%p%,1!
@if "!x!" equ "" goto :xit
:: all this block had to be added to filter the original input char.s
@if defined r (
set test=!ee!
if defined ee set ee=!ee:%x%=!
if "!ee!" equ "!test!" (
set /a r+=1
set ee=!ee!%x%
) else (
set ee=!test!
)
)
@set /a p+=1
@goto :x1
:xit
@set /a p-=1
::======= end
edited to suppress command echo occuring at deep levels of recursion



#1
May 17, 2013 at 19:05:14
Are nulls allowed? Like "ab" (That "up"s the ante quite a bit).
I'm sure this problem has been studied and solved, it's too common not to have been, so I recommend using Google ad-nauseum before relying on my feeble efforts. The main inputs are number of slots (or "places", "powers of...)", and number of values, kind of a matrix. You must stipulate a number of possible values (f/e: binary is 0, 1 only), then a number of powers (or "places" to be filled: 1 place is 0 or 1, two places is 00, 01, 10, 11 etc.) Once these two items are specified, I'm sure there's an existing algorithm you can plug into for populating the entire geometry. Potential for both dimensions is of course infinite with exponentially diminishing returns. It might be a fun challenge, but i'm not smart enough to qualify with an answer any time soon.

Report •

#2
May 18, 2013 at 08:31:41
The limitation of possible commands through batch is what makes this a hard task and takes thinking to accomplish.
I'll try later tonight and see how far i get.

Report •

#3
May 18, 2013 at 21:57:23
I worked on this (using a "saner" language than batch). It was not an easy thing for me, but here is a "qbasic" solution, which will give you the idea. I might try to implement batch (or anyone else is welcome to try!) but for now, this is my work:
DECLARE SUB YY (ZZ$)
CLS
'initialize and go.
DIM SHARED A$, Q
INPUT "CHAR SET: ",A$
IF A$="" THEN A$ = "01"
INPUT "SIZE OF STRING: ",Q
IF Q<2 THEN Q = 4
CALL YY(ZZ$)
STOP

SUB YY (ZZ$)
Z$ = ZZ$
FOR I = 1 TO LEN(A$)
ZZ$ = Z$ + MID$(A$, I, 1)
IF LEN(ZZ$) < Q THEN
CALL YY(ZZ$)
ELSE
PRINT "*****"; Z$
EXIT FOR
END IF
NEXT I
END SUB

you can obviously see why I tried to solve this in "real" language, before
tackling batch. I might (or might not) come back with an attempted batch soln.
(edited this code for efficiency)


Report •

Related Solutions

#4
May 19, 2013 at 09:55:19
This does it:
@echo off
setlocal EnableDelayedExpansion

if "%2" neq "" goto Permutations

if "%1" equ "" echo Give the desired string in the parameter & goto :EOF
set string=0%1
for /L %%i in (1,1,80) do if "!string:~%%i,1!" neq "" set strLen=%%i
for /F %%a in ('"%~F0" %string% %strLen%') do (
set /A p[%%a]+=1
)
for /F "tokens=2,3 delims=[]=" %%a in ('set p[') do (
echo %%b- %%a
)
goto :EOF
:Permutations string strLen
set string=%1
if %2 equ 2 (
echo %string:~1,1%%string:~2,1%
echo %string:~2,1%%string:~1,1%
) else (
set /A newStrLen=%2-1
for /L %%i in (1,1,%2) do (
set oneChar=!string:~%%i,1!
set /A leftSide=%%i-1, rightSide=%%i+1
for /F "tokens=1,2" %%a in ("!leftSide! !rightSide!") do (
set newString=0!string:~1,%%a!!string:~%%b!
)
for /F %%a in ('"%~F0" !newString! !newStrLen!') do (
echo !oneChar!%%a
)
)
)
exit /B

You use it in the format:
filename.bat string.
That by definition produces the permutations, just need more code to output aaa and bbb if the given string was abb.


Report •

#5
May 19, 2013 at 14:52:39
Here's a vbscript version as well (i got bored):
WSCRIPT.ECHO WSCRIPT.ARGUMENTS.COUNT
IF WSCRIPT.ARGUMENTS.COUNT>1 THEN
'usage: strings.vbs chars slots
A = WSCRIPT.ARGUMENTS(0)
Q = CINT(WSCRIPT.ARGUMENTS(1))+1
ELSE
'defaults to binary digits only, 4 slots or "places"
A="01"
Q=5
END IF
'oops, edited. I commented out the next line by accident.
CALL YY(ZZ)
WSCRIPT.QUIT

SUB YY (ZZ)
Z = ZZ
FOR I = 1 TO LEN(A)
ZZ = Z & MID(A, I, 1)
IF LEN(ZZ) < Q THEN
CALL YY(ZZ)
ELSE
WSCRIPT.ECHO "*****"& Z
EXIT FOR
END IF
NEXT
END SUB

so far, batch has been too much of a hassle to keep me interested in struggling with it. I was bored, but not THAT bored, Ha ha!


Report •

#6
May 19, 2013 at 14:59:11
Try PowerShell next. :V

How To Ask Questions The Smart Way


Report •

#7
May 26, 2013 at 07:26:46
We got off to a goofy start. abb has TWO unique elements.

Foe THREE unique elements, as on xyz, the number of
[ermutations is 6.

P=n!

=============================
Moving right along...

Don't bother telling me this script is a bodge.

As posted, it uses 4 elements and generates 24 perms.
The var E holds the elements.


:: =====  script starts here  ===============
:: 
:: perms.bat  2013-05-20 15:52:50.98
@echo off & setLocal enableDELAYedeXpansioN

echo.start  %TIME%
set TRIES=
set E=R G B Z
set N=&set/a P=1
for %%i in (!E!) do (set/a N+=1 & set/a P*=N & set E!N!=%%i)

for /L %%i in (1 1 !P!) do (set PM%%i=)

set/a TRIM=2*N-1

:generate 
set NUMS=
for /L %%x in (1 1 !N!) do (
set/a NUM=!random!%%N+1& set NUMS=!NUM! !NUMS! 
)
set NUMS=!NUMS:~0,%TRIM%!

for /L %%i in (1 1 !N!) do (set %%i=NO)

for %%z in (!NUMS!) do (
for /L %%i in (1 1 !N!) do (
if %%z equ %%i set %%i=OK
)
)
:check ALL NUMS ==================================================
set ALL=OK

for /L %%i in (1 1 !N!) do (if !%%i!==NO set ALL=NO)
if !ALL!==NO goto :generate

set/a TRIES+=1
for /L %%i in (1 1 !P!) do (
if "!PM%%i!"=="!NUMS!" goto :done
if not defined PM%%i set PM%%i=!NUMS!&& goto :done
)
:done

if not defined PM!P! goto :generate

@echo off > !P!-PERMS.TXT
for /L %%i in (1 1 !P!) do (
echo.PM%%i !PM%%i!
)>> !P!-PERMS.TXT

echo.finish %TIME%
echo.!TRIES! TRIES
goto :eof
::======  script ends here  =================

=====================
M2 Golden-Triangle


Report •

#8
May 28, 2013 at 03:36:34
This one is a bit quicker.


:: =====  script starts here  ===============
:: 
:: newperm.bat  2013-05-27 18:22:10.50
@echo off & setLocal enableDELAYedeXpansioN

if %1'==' echo how many elements? & goto :eof
set/a N=%1
echo start  %TIME%
set/a P=1 & for /L %%i in (1 1 !N!) do set/a P*=%%i
for /L %%i in (1 1 !P!) do set PM%%i=
set TRIES=
:generate
set S=
for /L %%i in (1 1 !N!) do set %%i=

:buildS
set/a C=!random!%%N+1

for /L %%i in (1 1 !N!) do (
  if "!%%i!"=="!C!" (
if defined !N! goto :ALLSET
    goto :buildS
  )
)
for /L %%i in (1 1 !N!) do (
  if not defined %%i (
    set %%i=!C!
    set S=!S!!C!
    goto :ADDED
  )
)
:ADDED

for /L %%i in (1 1 !N!) do (
  if not defined %%i goto :notDONE
)
:notDONE

goto :buildS
:ALLSET

set/a TRIES+=1
for /L %%i in (1 1 !P!) do (
if "!PM%%i!"=="!S!" goto :done
if not defined PM%%i set PM%%i=!S!&& goto :done
)
:done

if not defined PM!P! goto :generate

@echo off > !P!-PERMS.TXT
for /L %%i in (1 1 !P!) do (
echo.PM%%i !PM%%i!
)>> !P!-PERMS.TXT

echo.finish %TIME%
echo.!TRIES! TRIES
goto :eof

goto :eof
::======  script ends here  =================

=====================
M2 Golden-Triangle


Report •

#9
May 28, 2013 at 20:03:10
@M2: i see you got "hooked" on this one like I did. (We both know the OP is history) I couldn't resist messing with batch attempting the self-recursive approach:

@echo off & setlocal
:: restricted to non-repeating values. 01, 10 but not 11 or 00
set e=
set /p e=char. set:
:: should test for, or filter out non-unique char.s, but I'm too lazy
rem set e=ABCD
set e2=%e%
call :xx
>>strings echo ======= %~n0.bat =========
call :aa %e% %p%
echo done.
goto :eof

:aa
setlocal
set e2=%1
set e=%1
set z=%3
set p=%2
for /L %%a in (0,1,%p%) do (
set t=!e:~%%a,1!
if %p% gtr 0 (
set zz=%3!t!
call :ff
call :aa !e2! !p! !zz!
) else (
:: some debugging stuff
rem echo ********* z: %z% zz: !zz!!t! %1%3
>> strings echo !zz!!t!
goto :eof
)
)
goto :eof

:ff
set e2=!e:%t%=!

:: just find the current length of e2 using non-FOR-loop
:xx
set p=-1
:x1
set /a p+=1
set x=!e2:~%p%,1!
if "!x!" neq "" goto :x1
set /a p-=1
::=== end

I re-learned something I'd forgotten, which can really f-up performance:
for /L %%a in (1,1,10000) do (
etc
IF xx GOTO :out-of-loop
)
will iterate through all 10000, even if the IF-GOTO exit is activated early in the loop. At least, it seemed that way before I changed my code to use a non-FOR loop. Pls correct me if I'm wrong on this.
sample:
@echo off
for /L %%a in (0,1,100000) do (
if %%a equ 2 goto :eof
echo %%a
)


Report •

#10
May 31, 2013 at 05:51:25
I'm still here nbrane ;).

Report •

#11
May 31, 2013 at 16:44:50
✔ Best Answer
Ha ha! you got me! :-D Since you are still with us, here's the "other" version that allows repeats:
:: this one does all the permutations, allowing repeats: 00,01,10,11
@echo off & setlocal enabledelayedexpansion
:: this one does all the permutations, allowing repeats: 00,01,10,11
set e=
:: foll.is NOT the length of output string, it's the allowable char. set.
set /p e=char. set:
if not defined e goto :eof
set ee=
set r=0
call :xx %e%
set /a len=r-1
set r=
set e=%ee%
if not defined e goto :eof
set q=0
set /p q=length of output string:
if q lss 1 goto :eof
:: q needs to be adjusted to one less than what you really want, so...
set /a q-=1
>>strings echo ======= %~n0.bat =========
call :aa
goto :eof

:aa
@echo off & setlocal
@set z=%1
@for /L %%a in (0,1,%len%) do @(
@rem these next 8 at-signs are not really necessary, but I put them anyway.
@set zz=%z%!e:~%%a,1!
@call :xx !zz!
@if !p! leq %q% @(
@call :aa !zz!
) else @(
@>> strings echo %z%
@goto :eof
)
)
goto :eof

:XX
@echo off
@set p=0
@set xx=%1
:x1
@set x=!xx:~%p%,1!
@if "!x!" equ "" goto :xit
:: all this block had to be added to filter the original input char.s
@if defined r (
set test=!ee!
if defined ee set ee=!ee:%x%=!
if "!ee!" equ "!test!" (
set /a r+=1
set ee=!ee!%x%
) else (
set ee=!test!
)
)
@set /a p+=1
@goto :x1
:xit
@set /a p-=1
::======= end
edited to suppress command echo occuring at deep levels of recursion


Report •

#12
June 1, 2013 at 06:37:43
@nbrane
Great work as always ;).
However, when i enter abb can you modify it a little so i can have the desired result i got in my original post? Basically just removing the duplicates.
So through doing that modification the ending result would be:
aaa
bbb
abb
bab
bba
aab
aba
baa

Report •

#13
June 1, 2013 at 12:41:58
I assume you mean to filter the input char.s to eliminate dupes? I'll modify post #11 to save space.

Report •

#14
June 1, 2013 at 14:56:16
@nbrane
Spot on, script works perfectly.
Thanks :).

Report •

#15
June 2, 2013 at 01:40:51
@nbrane
Not really a problem but i was wondering, when i enter charset:abcdefghijklmnopqrstuvwxyz
and length as 2 i get output on the screen of the commands running after ~9 seconds although there's @echo off in the beginning, i assume it has to do with the calls?
How can i stop this from occurring since it drastically reduces speed?

Report •

#16
June 2, 2013 at 11:43:04
Yes, I'm sure it has something to do with the recursive calls and stack-space overflow. That is the "fatal flaw" of this arrangement: there is a limit to the length of the char. set (and probably also the output string) determined by stack-space and memory. If batch could be made to utilize virtual (disk-based) memory, then the constraints would be much less restricted, but I doubt if that is possible. I'll put my fixes in post #11 for the 26-byte char.set, this fixed the problem at that limit, but of course at some point the limit will crash the batch.

Report •

#17
June 2, 2013 at 12:18:19
I really appreciate all the work you put into this.
But it still has the same problem, the interesting cut-off point is when the strings file reaches 1.50 kb, that's when the commands start to be displayed in the console.
I found a pretty lame method to speed things up which is to add @echo off
above this code for /L %%a in (0,1,%len%) do (. The result with that is, it displays the commands on the console at the same point 1.50 kb, but only for 2-3 seconds and there's a massive change in speed.

Report •

#18
June 2, 2013 at 18:40:44
I don't know, it must be a difference in system specs, because there was no output on my end after the aforementioned modifications. It took about 12 seconds to complete. Then I ran it without the modifications and output piped to nul, which also dodged the screen junk, and that one ran about 10 seconds. Maybe you can just use the first version but pipe the output to nul? (That doesn't affect the "strings" file output).
Unless you're restricted to batch for some reason, there's also always the other two alternatives: vbscript and visbasic/qbasic, which might (probably will) improve performance time-wise. There's a bunch of things that could be affecting this thing, such as other programs that are running (and thus using up memory and cpu-time), ram capacity, ram speed, virus-condoms, etc. Nothing will be perfect, especially with batch, so we just have to hack around (at least in my case, since I don't know squat!)
;-)
ps: i forgot! Of course I had to modify the script to output to nul, because of the set /p. I used commandline parms instead of set/p's to get around that issue (set e=%1, set q=%2)

Report •

#19
June 2, 2013 at 20:53:44
@nbrane
Thanks, it works now.
There was just a tiny typo "s@et" that had to be changed to "@set".

Report •

#20
June 2, 2013 at 21:24:42
Ha ha! Sorry. I missed that entirely. My bad. Fixed in post #11 for any future reference. Also this for variable inputs (prompted vs. commandline):
@echo off & setlocal enabledelayedexpansion
:: this one does all the permutations, allowing repeats: 00,01,10,11
prompt $M
set e=%1
set q=%2
:: foll.is NOT the length of output string, it's the allowable char. set.
if not defined e set /p e=char. set:
if not defined e goto :eof
set ee=
set r=0
call :xx %e%
set /a len=r-1
set r=
set e=%ee%
if not defined e goto :eof
if not defined q set /p q=length of output string:
if q lss 1 goto :eof
:: q needs to be adjusted to one less than what you really want, so...
set /a q-=1
>>strings echo ======= %~n0.bat ========= start: %time% char.set: %e%
call :aa
>> strings echo done at %time%
goto :eof

:aa
@echo off & setlocal
@set z=%1
@for /L %%a in (0,1,%len%) do @(
set zz=%z%!e:~%%a,1!
call :xx !zz!
if !p! leq %q% (
call :aa !zz!
) else (
>> strings echo %z%
goto :eof
)
)
goto :eof

:XX
@echo off
@set p=0
@set xx=%1
:x1
@set x=!xx:~%p%,1!
@if "!x!" equ "" goto :xit
:: all this block had to be added to filter the original input char.s
@if defined r (
set test=!ee!
if defined test set test=!ee:%x%=!
if "!ee!" equ "!test!" (
set /a r+=1
set ee=!ee!%x%
)
)
@set /a p+=1
@goto :x1
:xit
@set /a p-=1
::===== end


Report •

#21
June 3, 2013 at 08:33:19
Both work at roughly the same speed, the script in post 11 works a few milliseconds faster due to the time being set in the latest script.
Was wondering, if i enter characters like <>& the script malfunctions, do you know of a way to enable them to be used in this script?

Report •

#22
June 3, 2013 at 09:59:25
You know, if speed is a concern, consider a different language.
Also, if "batch dangerous" characters are a concern, consider a different language.

How To Ask Questions The Smart Way


Report •

#23
June 3, 2013 at 12:05:34
Yes, exactly, on both counts. You can spend hours, and days trying to trick batch into handling "system" characters, but it's not really worth the effort. Something usually fouls, and the amount of extra code makes it unwieldy. If you want access to the entire printable ascii charset, go with any other language than batch.

Report •

#24
June 3, 2013 at 12:06:34
@Razor2.3
There isn't really a problem apart from the special symbols.
Anyway i'm done with this he did a great job on the script.

Report •

Ask Question