2019-05-21

Others

Syntax highlighting by Prism

String Permutation Enumeration

Siamack Yousofi

Siamack Yousofi

Description

Enumerates all possible unique permutations from a given data range.

n/a

Source

n/a

Source Code

``````'I have posted 2 pieces of code below.  They are not much of an offering
'and are really "Programming 101" stuff. However I need to use the posting
'as the basis for a wish list posting in the Programming Forum.
'
'A bit of background first.  I have invented a new online user authentication
'system and applied for international patents for it.         The ideal business
'model for making money from the invention is to licence the �Process� to
'the end users and provide them with an SDK so they can implement the
'technology any which way they like.
'
'During the development of the SDK I needed to write functions that
'generate random permutations of any specified set of elements.
'The 2 pieces of code below are the results.
'
'Some theory:
'
'We can arrange N unique elements in N! Different ways.  For those who are
'a bit rusty with their school Maths         N! (Pronounced N-Factorial) is simply
'
'             N! = N * (N-1) * (N-2) * . . . * (1)
'
'So for 3 elements (a,b,c) we have 3x2x1 or 6 possible arrangements.
'There  are 3,628,800 arrangements of digits 0 to 9
' (without repeating
'digits within each permutation).
'
'Using random permutations of a given set of elements have applications
'in cryptography and crypto-analysis among other things.
'
'Suggestions for improvement will be greatly appreciated.
'
'Siamack

'###############################################################
'
'The code below will generate all the 3,628,800 10 digit permutations of
'elements 0-9 and saves them in a file.  To get a random arrangement one
'can simply choose a line in the file at random.  This is similar to the
'old printed random number tables we used in Statistic courses during the
'Slide-Rule days.
'
'Please note that the file generated has the permutations in ascending order
'so they are not really random! You may wish to randomise the file after it
'is generated and create a new file.
'
'The advantage of this over generating a random permutation on the fly is
'that you can ensure no permutation is used a second time until you finish
'using all of them.

FUNCTION PBMAIN() AS LONG
DIM x AS STRING
DIM j AS INTEGER
DIM k AS INTEGER
DIM s AS STRING
DIM FileNumber AS INTEGER
STDOUT
"Generating all 10 digit permutations for elements 0 to 9 and"
STDOUT "writing the results to the file random.txt . . ."
STDOUT CHR\$(13,10)
STDOUT "WARNING:"
STDOUT CHR\$(13, 10)
STDOUT "This will take some time and the generated text file will be"
STDOUT "approximately 43 MB in size!"
STDOUT CHR\$(13,10)
STDOUT "To stop the process use the (exit) button of the application"
STDOUT "window."
STDOUT CHR\$(13,10)
STDOUT "Working . . .";
FileNumber = FREEFILE
OPEN "random.txt" FOR APPEND AS #FileNumber
FOR i = 0123456789 TO 9876543210 STEP 9      'From smallest permutation to the largest permutation
x = FORMAT\$(i,"0000000000")              'Makes the leading 0 present in the string variable
k = 0
FOR j = 0 TO 9
s = FORMAT\$(j,"0")
IF TALLY(x, s) = 1 THEN
k = k + 1
ELSE
EXIT FOR                           'We do not want permutations with repeated digits
END IF
NEXT
IF k = 10 THEN                           'This test is not really necessary but good practice!
PRINT #FileNumber, x
END IF
NEXT
CLOSE FileNumber
BEEP
END FUNCTION

'###############################################################
'
'This one is more generic and will generate a specified number of random
'permutations of a specified set of elements (of any type not just digits)
'on the fly.  I will refer to this code in my wish-list posting in the
'Programming Forum.
'Input examples: 0123456789  |  QWERTY  |  &\$#@%*^  |  etc.

DECLARE FUNCTION Permute(BYVAL AllElements AS STRING) AS STRING
FUNCTION PBMAIN()
DIM Permutation AS STRING
DIM Original AS STRING
DIM Count AS STRING
DIM i AS INTEGER
DO
STDOUT "To quit the program enter Q"      ' Show them the way out
STDOUT CHR\$ (13,10)
STDOUT "Enter original sequence > ";      ' This includes white spaces
STDIN LINE Original
IF UCASE\$(Original) = "Q" THEN EXIT
STDOUT "How many permutations?  > ";      ' This should be a number
STDIN LINE Count                          ' Add validation if you like
IF UCASE\$(Count) = "Q" THEN EXIT
STDOUT CHR\$(13,10)
FOR i = 1 TO VAL(Count)                   ' If Count is a letter then nothing will happen
Permutation = Permute(Original)         ' Original is passed on "BY VALUE"
STDOUT Permutation
NEXT
STDOUT CHR\$(13,10)
LOOP
END FUNCTION

FUNCTION Permute(BYVAL AllElements AS STRING) AS STRING
DIM ThisElement AS STRING
DIM MixedElements AS STRING
DIM i AS INTEGER
FOR i = 1 TO LEN(AllElements)
ThisElement = MID\$(AllElements, INT((LEN(AllElements) * RND) + 1), 1)
MixedElements = MixedElements & ThisElement
AllElements = REMOVE\$(AllElements, ThisElement)     ' Repeated elements will all be removed!
NEXT
Permute = MixedElements
END FUNCTION
``````