Page 1 of 1
Generate all possible unique permutations of given string
Posted: 18 May 2013 09:28
by slm
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.
I am willing to share a poc of replacement of input through set /P choice which covers the actual input with asterisks, consisting of 11 lines, which many people say is impossible with whoever is able to accomplish this.
Thanks in advanced.
Re: Generate all possible unique permutations of given strin
Posted: 18 May 2013 10:05
by foxidrive
If a string is input of abb then you can't get aaa out of it.
Just pointing out that a permutation uses all characters, AIUI.
Re: Generate all possible unique permutations of given strin
Posted: 18 May 2013 13:29
by slm
@foxidrive
Number of unique characters:2.
Length:3.
2^3=8
The purpose for this is to use in a regexp. So generating all the possible strings from a given string with the specified length is what i want.
Re: Generate all possible unique permutations of given strin
Posted: 18 May 2013 14:38
by Endoro
Re: Generate all possible unique permutations of given strin
Posted: 18 May 2013 15:30
by Aacini
This question is similar to
Tower of Hanoi problem, and one of the simplest way to solve it is via a recursive subroutine. However, in this case the method have a further complication because you want
unique permutations, that is, although "abb" and "abb" are different permutations (the second and third letters are interchanged), both strings result in the same "real" permutation, so one of it must be eliminated. This detail requires additional code.
Code: Select all
@echo off
setlocal EnableDelayedExpansion
rem Generate all *unique* permutations of the characters in a given string
rem Antonio Perez Ayala
if "%2" neq "" goto Permutations
if "%1" equ "" echo Give the desired string in the parameter & goto :EOF
rem Get the string lenght
set string=0%1
for /L %%i in (1,1,80) do if "!string:~%%i,1!" neq "" set strLen=%%i
rem Generate all permutations and group the unique ones
for /F %%a in ('"%~F0" %string% %strLen%') do (
set /A p[%%a]+=1
)
rem Show unique permutations and number of repetitions
for /F "tokens=2,3 delims=[]=" %%a in ('set p[') do (
echo %%b- %%a
)
goto :EOF
:Permutations string strLen
set string=%1
rem If there are just two characters...
if %2 equ 2 (
rem show the permutations
echo %string:~1,1%%string:~2,1%
echo %string:~2,1%%string:~1,1%
) else (
rem Varying the first character, generate permutations for the rest (newString)
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
For example:
Code: Select all
>permutations abc
1- abc
1- acb
1- bac
1- bca
1- cab
1- cba
>permutations abb
2- abb
2- bab
2- bba
Antonio
Re: Generate all possible unique permutations of given strin
Posted: 18 May 2013 16:06
by slm
@Antonio
First of all great job.
However, just few problems.
It doesn't output the identical strings, e.g if i enter
bba, i want these too:
aaa
bbb.
1 last request, how can i implement this into a script i want to make?
Like it'll ask for the string and it'll output the permutations without having to call an external script, i want to be able to do it from the inside.
Many thanks.
Re: Generate all possible unique permutations of given strin
Posted: 18 May 2013 16:25
by Aacini
Wow! This is NOT a PERMUTATION! (what a confusion here). It is entirely different to have a
string as input, like "abb", and generate all possible
permutations of its characters...
foxidrive wrote:If a string is input of abb then you can't get aaa out of it.
Just pointing out that a permutation uses all characters, AIUI.
... than have a number of unique characters and an output length as input and generate all possible
combinations from they:
slm wrote:@foxidrive
Number of unique characters:2.
Length:3.
2^3=8
The purpose for this is to use in a regexp. So generating all the possible strings from a given string with the specified length is what i want.
I don't know how to call the result you want, but the Batch file below generate it.
Code: Select all
@echo off
setlocal EnableDelayedExpansion
set letter=0abcdefghijklmnopqrstuvwxyz
rem Initialize each positional value with 1
for /L %%i in (1,1,%1) do set pos[%%i]=1
rem Cycle through values until carry from last position
:nextValue
rem Show value
set value=
for /L %%i in (%1,-1,1) do (
for %%p in (!pos[%%i]!) do (
set value=!value!!letter:~%%p,1!
)
)
echo %value%
rem Increment value, position by position
set /A i=1, carry=1
:incPos
set /A pos[%i%]+=carry, carry=0
if !pos[%i%]! gtr %2 (
set /A pos[%i%]=1, carry=1, i+=1
)
if %carry% equ 1 goto incPos
if %i% leq %1 goto nextValue
You must provide the Number of characters (lenght of result string) and the Number of unique characters in the parameters. For example:
Code: Select all
>PositionsNbaseM.bat 3 2
aaa
aab
aba
abb
baa
bab
bba
bbb
You just need to get the lenght of the string and the number of unique characters from your original string!
Antonio