Entry

BBCBASIC: Combinatorics: Permutation: Can you give program enumerating permutations of given string?

May 4th, 2007 10:26
Knud van Eeden,

----------------------------------------------------------------------
--- Knud van Eeden --- 04 May 2021 - 06:03 pm ------------------------
BBCBASIC: Combinatorics: Permutation: Can you give program enumerating 
permutations of given string?
---
The idea is to keep splitting the given string in simpler (=smaller)
strings, until the length of the string equals 0 or 1.
Then you stop and print the current result.
===
--- cut here: begin --------------------------------------------------
 PROCCombinatoricsPermutationSwapRecursive( "" )
 PRINT "---"
 PROCCombinatoricsPermutationSwapRecursive( "a" )
 PRINT "---"
 PROCCombinatoricsPermutationSwapRecursive( "ab" )
 PRINT "---"
 PROCCombinatoricsPermutationSwapRecursive( "abc" )
 PRINT "---"
 PROCCombinatoricsPermutationSwapRecursive( "abcd" )
 PRINT "---"
 END
 :
 :
 :
 REM library: Combinatorics: Permutation: Swap: Recursive [kn, ri, fr, 
04-05-2021 17:58:02]
 DEF PROCCombinatoricsPermutationSwapRecursive( s$ )
 REM e.g. PROCCombinatoricsPermutationSwapRecursive( "" )
 REM e.g. PRINT "---"
 REM e.g. PROCCombinatoricsPermutationSwapRecursive( "a" )
 REM e.g. PRINT "---"
 REM e.g. PROCCombinatoricsPermutationSwapRecursive( "ab" )
 REM e.g. PRINT "---"
 REM e.g. PROCCombinatoricsPermutationSwapRecursive( "abc" )
 REM e.g. PRINT "---"
 REM e.g. PROCCombinatoricsPermutationSwapRecursive( "abcd" )
 REM e.g. PRINT "---"
 REM e.g. END
 REM e.g. :
 REM e.g. :
 REM e.g. :
 PROCCombinatoricsPermutationRepetitionSwapRecursiveSub( "", s$ )
 ENDPROC
 :
 REM library: Combinatorics: Permutation: Swap: Recursive: Sub [kn, 
ri, fr, 04-05-2021 17:58:26]
 DEF PROCCombinatoricsPermutationRepetitionSwapRecursiveSub( left$, 
right$ )
 LOCAL lengthI%
 LOCAL I%
 lengthI% = LEN( right$ )
 REM You check for the length of the
 REM incoming right string, which is
 REM more the main string
 REM
 REM The left string is more a temporary
 REM string (which carries the removed
 REM characters further)
 REM
 REM case: if length is zero:
 REM the permutation of 0 characters gives
 REM again an empty character.
 REM Also stop the recursion.
 REM (e.g. permutation of "" is again "")
 REM
 REM case: if length is one:
 REM the permutation of 1 character gives
 REM the character itself.
 REM Also stop the recursion.
 REM (e.g. permutation of "a" is again "a")
 REM
 IF ( lengthI% = 0 ) OR ( lengthI% = 1 ) THEN 
PROCCombinatoricsPermutationRepetitionSwapRecursivePrint( left$, 
right$ ) : ENDPROC
 REM
 REM case: the length is greater than one:
 REM then for all characters in the string
 REM you permute the remaining characters
 REM by concatenating all the characters before
 REM (left of) the current character and
 REM all the characters after (=right of)
 REM the current character and making this
 REM the new right string.
 REM Which thus shrinks all the time one in
 REM length (so stopping the recursion when
 REM the length finally becomes 1).
 REM
 REM The current character you concatenate
 REM on the left string, and carry it so further,
 REM as it also has to be known for the final
 REM printing purposes when the recursion stops.
 REM
 REM For example if 2 characters,
 REM the permutation of 2 characters
 REM are the first and the second character,
 REM and also swapping the second and the first character
 REM (e.g. permutation of "ab" gives "ab" and "ba").
 REM
 REM This swapping takes indeed place in the below for next loop.
 REM If I% equals 1, then you get filled in as parameters
 REM  "" + "a", "" + "b", which when printed later gives "a"+"b",
 REM or thus "ab"
 REM If I% equals 2, then you get filled in as parameters
 REM  "" + "b", "a" + "", which when printed later gives "b"+"a",
 REM or thus ="ba"
 REM
 REM For example if 3 characters,
 REM You split this in:
 REM
 REM 1. the first character
 REM    and the permutation of the other 2 characters,
 REM    thus "a" and "bc"
 REM    which gives "a" and "bc" and "a" and "cb"
 REM
 REM 1. the second character
 REM    and the permutation of the other 2 characters,
 REM    thus "b" and "ac"
 REM    which gives "b" and "ac" and "b" and "ca"
 REM
 REM 3. the third character
 REM    and the permutation of the other 2 characters,
 REM    thus "c" and "ab"
 REM    which gives "c" and "ab" and "c" and "ba"
 REM
 REM This swapping takes indeed place in the below for next loop.
 REM If I% equals 1, then you get filled in as parameters
 REM  "" + "a", "b" + "c", which when printed later gives "a"+"bc",
 REM and "a" + "cb",
 REM or thus "abc" and "acb"
 REM If I% equals 2, then you get filled in as parameters
 REM  "" + "b", "a" + "c", which when printed later gives "b"+"ac",
 REM and "b" + "ca",
 REM or thus "bac" and "bca"
 REM If I% equals 3, then you get filled in as parameters
 REM  "" + "c", "a" + "b", which when printed later gives "c"+"ab",
 REM and "c" + "ba",
 REM or thus "cab" and "cba"
 REM
 REM Thus it works (by inductive reasoning) for 0, 1 and 2 characters,
 REM thus also for 3 characters, which you split in three times 1
 REM character and 2 characters.
 REM
 REM and so on ... for 4, 5, ..., N characters.
 REM
 FOR I% = 1 TO lengthI%
   PROCCombinatoricsPermutationRepetitionSwapRecursiveSub( left$ + 
MID$( right$, I%, 1 ), LEFT$( right$, I% - 1 ) + RIGHT$( right$, 
lengthI% - I% ) )
 NEXT I%
 ENDPROC
 :
 REM library: Combinatorics: Permutation: Swap: Recursive: Print [kn, 
ri, fr, 04-05-2021 18:34:28]
 DEF PROCCombinatoricsPermutationRepetitionSwapRecursivePrint( left$, 
right$ )
 PRINT left$ + right$
 ENDPROC
 :
--- cut here: end ----------------------------------------------------
===
Book: see also:
---
[book: Rohl, Jeff S. - recursion via PASCAL - Cambridge university 
press / Cambridge / UK - 1984]
===
Internet: see also:
---
BBCBASIC: Windows: Combinatorics: Link: Can you give an overview of 
links?
http://www.faqts.com/knowledge_base/view.phtml/aid/45285/fid/768
----------------------------------------------------------------------