[Autoit] Combinations n^r

elmarcia · 04/20/2016, 23:00

Hi everybody, i've been bored so i decided to make a combination algorithm i explain how i get to those step by step.

Usage:
1)Get any combination n^r where:
n is a set of symbols like {"a","b",...}
r is the length of the string
(Getting all combinations of 5 letters in a text file for fun lasts 1 hour (14million aprox) limited by hard disc writting time (Remember all combinations of 5 letters means all words in any language that have that length

))

2)Brute force passwords..
Nehh a password that contains {A,B,...}U{a,b,...}U {0,1,...} Where n = aprox 65 with a length of 10 has: 65^10 possible combinations or 1.34627433446289e18 -> lets say your computer can process 1millon per second that gives us a total of = 1346274334462.89 secs = 711.501318314989 years-> great

Code with tutorial:

Spoiler

Code:

#include <Array.au3>
#cs
aaaa
aaab
aaac
aaba
aabb
aabc
aaca
aacb
aacc
abaa
abab
abac
abba
abbb
abbc
abca
abcb
abcc
acaa
acab
acac
acba
acbb
acbc
acca
accb
accc
baaa
baab
baac
baba
babb
babc
baca
bacb
bacc
bbaa
bbab
bbac
bbba
bbbb
bbbc
bbca
bbcb
bbcc
bcaa
bcab
bcac
bcba
bcbb
bcbc
bcca
bccb
bccc
caaa
         Repetitions->  (first character) 3^3   (second character)3^2  (third character)3^1  (fourth character)3^0
		 Number of symbols = K = 3
		 String len = 4
		 Our first character repeats  -> K^(n-1)
		 Second repeats                     -> K^(n-2) -> until (n-m) = 0

lets say our first word (aaaa) is in index = 1 ->
and (accc) is index 27 or 3^3...
Our array is -> ["a","b","c"] -> where  "a" = 0 , "b" = 1 , "c" = 2
That means we need that 0 so ->

aaaa = 1
accc = 27 -> 3^3 -> K^(n-1) Where K = number of symbols (we have 3 Symbols (abc)) ->
3^(n-1) -> where n = string len (4) => 3^3

We want a 0, how do we get a cero between that range: -> easy 1/27 or -> firstLetterIndex/3^3 -> firstLetterIndex/K^(n-1)
now we got something like this: 1/27 = 0,037037037037037 -> so Int(0,037037037037037) = 0 -> Int(1/27) -> Int(firstLetterIndex/K^(n-1))
In practice arrays starts with 0 so -> aaaa index = 0
#ce                                                  	    0  1  2  3  4  5  6  7  8
Local $test[] = ["a","b","c"] ; -> Combinations with n=2 : aa ab ac ba bb bc ca cb cc
$K = UBound($test)
$n = 2
$firstLetterIndex = 3
$res = $test[Int($firstLetterIndex/$K^($n-1))]
MsgBox(0,"EXAMPLE 1","[Getting first letter using a combination Index as input]" & @CRLF & $res) ;will return b


;Now is working but only for the first character, lets make it work in a for loop and see what we got
Local $m[] = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","ñ","o","p","q","r","s","t","u","v","w","x","y","z"]
$K = UBound($m) ;number of symbols
$wordIndex = 113788 ; don't tell anyone :(
$combination = ""
$stringLen = 4
For $n = $stringLen-1 To 0 Step -1
$index =Int($wordIndex/$K^($n))
$index = Mod($index,$K); index should be between 0 and numberOfSymbols -> mod solve the problem of getting bigger indexes
$combination &= $m[$index] ;we don't use n-1 because we need to increment that 1 everytime n-2 n-3 n-4 ... solved in the for loop $stringLen -1
Next
MsgBox(0,"EXAMPLE 2","[Getting a word combination using an index as input]" & @CRLF & $combination)

;SO the function will be ->
Func getCombination($array,$length,$wordIndex)
$K = UBound($array) ;number of symbols
$combination = ""
For $n = $length-1 To 0 Step -1
$index =Int($wordIndex/$K^($n))
$index = Mod($index,$K)
$combination &= $m[$index]
Next
Return $combination
EndFunc

#cs
;Now what if we want to get the wordIndex instead (? -> we can clear previous equation like this
$wordIndex is for the whole combination, so lets get index of every letter -> $letterIndex
1)$temp = Int($letterIndex/$K^($n)) ->lets call this temp where our X will be $letterIndex
2)$index = Mod($temp,$K) -> where index is the index of the letter we want to search for -> for example if we want  the letter c index its 2 ["a","b","c",...], arrays start in 0

what the hell is mod-> is the remainder of an integer division...
From autoit help file we got that mod is = Mod(dividend,divisor) = dividend - Int(dividend / divisor) * divisor
Replacing that in ec 2)
$index = $temp - int($temp/$K) * $K -> common factor $temp -> $index = $temp(1-int(1/$K) * $K)
clearing $temp -> 3) $index/(1 - INT(1 / $K) * $K) = $temp
Replacing 1) in 3) ->
$index/( 1 - INT(1/$K) * K ) = INT($letterIndex/$K^$n)
lets divide each member with INT
$index/INT(1-INT(1/$K)*K) = $letterIndex/$K^$n -> clearing $letterIndex
$index * $K^$n / INT(1 - INT(1 / $K) * K) = $letterIndex
#ce
;Testing...                   0  1   2   3   4     5
Local $array[] = ["a","b"] ; aaa aab aba abb baa bab
$cIndex = 1;letter b in array...
$K = UBound($array)
$n = 3;string len = to word length
$n = $n-1 ;remember for each...
$index = $cIndex
$letterIndex = $index * $K^$n / INT(1 - INT(1 / $K) * $K)
MsgBox(0,"EXAMPLE 3","[Getting combination Index using 1 letter as input]" & @CRLF & $letterIndex) ;we got a 4 that means that in index 4 the first letter is a b

;now with any word...
MsgBox(0,"EXAMPLE 4","[Getting combination Index using a word as input]" & @CRLF & getWordIndex("bab",$array))
Func getWordIndex($word,$array)
$K = UBound($array)
$length = StringLen($word)
$n = $length -1
$wordIndex = 0
For $i = 1 To $length
$charIndex = _ArraySearch($array,stringmid($word,$i,1),0,0,1);case sensitive search..
$letterIndex = $charIndex * $K^$n / INT(1 - INT(1 / $K) * $K)
$wordIndex += $letterIndex
$n-=1
Next
Return $wordIndex
EndFunc

;Verify -

Local $m[] = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","ñ","o","p","q","r","s","t","u","v","w","x","y","z"]
$index = getWordIndex("hello",$m)
MsgBox(0,"EXAMPLE 5","[Getting combination index of hello]" & @CRLF & $index)
MsgBox(0,"EXAMPLE 6","[Using index: " & $index  & " to get word]"& @crlf & getCombination($m,5,$index))

Give me the [2239695393] code:

Spoiler

Lawliet · 04/28/2016, 11:44