Generate all possible unique permutations of given string

[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.

[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.

[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.

[Endoro]

permutation

[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

[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.

[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...

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:

@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