2017-12-15

Navigation

Skip Navigation Links

Hash algorithms

Asymmetric Algorithms

Symmetric Cipher Algorithms

Encoding Algorithms

Compression Algorithms

Pseudo Random Number Algorithms

Steganography

Library Wrappers

String Comparison

Others

Syntax highlighting by Prism
PBCrypto.com Mirror

String Permutation Enumeration

Algorithm creator(s)

Siamack Yousofi


PB author(s)

Siamack Yousofi


Description

Enumerates all possible unique permutations from a given data range.


Note

n/a


Source

https://forum.powerbasic.com/forum/user-to-user-discussions/source-code/23901-random-permutations


See also

n/a


Source Code

Download source code file permenum.bas (Right-click -> "Save as ...")

'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 i AS QUAD
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

Mirror provided by Knuth Konrad