I wanted to know if the algorithm that i wrotte just below in python is correct.
My goal is to find an algorithm that print/find all the possible combinaison of words that can be done using the character from character '!' (decimal value = 33) to character '~' (decimal value = 126) in the asccii table:
Here the code using recursion in python:
byteWord = bytearray(b'\x20') # Hex = '\x21' & Dec = '33' & Char = '!'
cntVerif = 0
def comb_fct(bytes_arr, cnt: int):
global cntVerif
if len(bytes_arr) > 3:
print(f'{cntVerif+1}:TEST END')
sys.exit()
if bytes_arr[cnt] == 126:
if cnt == len(bytes_arr) or len(bytes_arr) == 1:
bytes_arr.insert(0, 32)
bytes_arr[cnt] = 32
cnt += 1
cntVerif += 1
print(f'{cntVerif}:if bytes_arr[cnt] == 126: \n\tbytes_arr = {bytes_arr}')
comb_fct(bytes_arr, cnt)
if cnt == -1 or cnt == len(bytes_arr)-1:
bytes_arr[cnt] = bytes_arr[cnt] + 1
cntVerif += 1
print(f'{cntVerif}:if cnt==-1: \n\tbytes_arr = {bytes_arr}')
comb_fct(bytes_arr, cnt=-1) # index = -1 means last index
bytes_arr[cnt] = bytes_arr[cnt] + 1
cntVerif += 1
print(f'{cntVerif}:None if: \n\tbytes_arr={bytes_arr}')
comb_fct(bytes_arr, cnt+1)
comb_fct(byteWord, -1)
Pseudo-code:
byteWord = bytearray(b'\x20') # create a byte with value 20 in hex basis
cntVerif = 0
def comb_fct(bytes_arr, cnt: int):
if length(bytes_arr) > 3:
print(f'{cntVerif+1}:TEST END')
stop
if bytes_arr[cnt] == 126:
if cnt == length(bytes_arr) or length(bytes_arr) == 1:
bytes_arr.insert(index=0, value=32) # Insert at the top of the byte array an other byte at index 0 (the begining) with value 32
bytes_arr[cnt] = 32
cnt += 1
cntVerif += 1
print(f'{cntVerif}:if bytes_arr[cnt] == 126: \n\tbytes_arr = {bytes_arr}')
comb_fct(bytes_arr, cnt)
if cnt == -1 or cnt == len(bytes_arr)-1:
bytes_arr[cnt] = bytes_arr[cnt] + 1
cntVerif += 1
print(f'{cntVerif}:if cnt==-1: \n\tbytes_arr = {bytes_arr}')
comb_fct(bytes_arr, cnt=-1) # index = -1 means last index
bytes_arr[cnt] = bytes_arr[cnt] + 1
cntVerif += 1
print(f'{cntVerif}:None if: \n\tbytes_arr={bytes_arr}')
brute_force_fct(bytes_arr, cnt+1)
comb_fct(byteWord, -1)
Thank your for your help because python allow just a limited number of recursion (996 on my computer) so for exemple i can't verify if my algorithm give all the word of length 3 that can be realised with the range of character describe upper.
And more generally i would like to know if my algorithm is correct genrally (the logic).
Of course if anyone has a better idea to writte this algorithm (a faster algorithm for exemple). I will be happy to read it.
Best Answer
EDIT: a full efficient python code (see the accepted answer): https://stackoverflow.com/questions/72762403/algorithm-verification-get-all-the-combinaison-of-possible-word
EXPLANATION:
To solve this problem i think that i ve found a more elegant and faster way to do it without using recursive algorithm.
Complexity:
I think too that it is the time and space optimal solution.
As it is in time: O(n) with n the total number of possible combinaison that can be very very high. And theorically O(1) in space complexity. Concerning the space complexity because of the python language characteristics my code ,from a practical point of view, creates a lot of bytearray. This can be corrected with light modification. But for a better code check the solution posted by @ricci here that i marked as the accepted answer.
Mathematical principle used:
I am using the fact that it exists a bijection between all the number in decimal basis and the number in base 94.
It is obvious that each number in base 94 can be written using a special sequance of unique character as the one in the range [30, 126] (in decimal value) in the ascii code.
Exemple of base conversion:
https://www.rapidtables.com/convert/number/decimal-to-hex.html
The operator '//' is the quotient operator and the operator '%' is the modulo operator.
I will be happy if anyone can confirm that my solution is correct. :-)
ALGORITHM
VERSION 1:
If you are NOT interested by getting all the sequence of words starting by '!'.
For exemple in lenght 2, you are NOT interested by the words of the form
'!!'...'!A' '!B' ... etc ...'!R'...'!~'
(as in our base '!' is equivalent to zero).VERSION 2:
If you are interested by getting all the sequence of words starting by '!'.
For exemple in lenght 2, you are interested by the words of the form
'!!'...'!A' '!B' ... etc ...'!R'...'!~'
(as in our base '!' is equivalent to zero).