How to get every possible combination of alphanumeric characters for the given length?
So, what I pretty much want to do, is, make a "function"? (I think that's what I'll call it) that makes up every possible combination of alphanumeric characters for the given length.
I've tried a countless number of things, my brain is really confused right now...
Here's one of the closest things I tried..
--Set up the character table
local chars, charStr = {}, "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
for i=1,#charStr do
table.insert(chars, charStr:sub(i,i))
end
setmetatable(chars, { -- make the table loop (magic)
__index = function(t, i)
return (i>#t and t[i-#t]) or (#t>i and t[#t-i])
end
})
--Continue
local maxLen = 3
local s = ""
for i=1,(#chars) ^ maxLen do --iterate through the number of possible combinations?
if #s == maxLen then
local b = false
for i,v in next, chars do
b = s:sub(1,1) == v and i or false
if b then break end
end
s = b and chars[b+1] or s
else
s = s .. chars[i]
end
print(s)
wait()
end
0
0
0
0
0
3 answers
You can't do this with just for loops (unless you know specifically how long it will always be -- e.g., 5)
The most straightforward way to do this is recursion.
Let's call a n-string a string made of the alphabet that is n characters long.
Then we know all of the 1-strings -- they are just all of the letters in chars.
What are all of the 2-strings? Well, they're any two letters in chars. But we can say something a little nicer:
A 2-string is any one character from chars followed by any of the 1-strings.
We can use this definition in general:
A
k-string is any one character fromcharsfollowed by ak-1-string
The code to get all of them, then, would look something like this:
chars = "abcd" -- Returns a list of strings (each of length k) -- (Works inductively) function kstrings( k ) if k == 0 then -- There is only one length 0 string: return {""} else local kminus1s = kstrings( k - 1 ) -- all (k-1)-strings local result = {} for i = 1, #chars do -- chars[i] followed by each (k-1)-string for _, km1 in pairs(kminus1s) do table.insert(result, chars:sub(i, i) .. km1 ) end end return result; end end print( kstrings(3) )
Warning: This will be very, very slow. The result will be #chars^k strings. If you're using uppercase and lowercase and you're just inputting 5, that's 380 million. Each will be 5 chars long, so this will take at least 1.9 GB to store1.
Because of the massive memory requirement, you probably won't be able to generate a list of all of them.
A better approach? (edited)
Instead, we can make a "successor" of a string by counting up repeatedly in base-#chars.
function successor(list, base, at)
at = at or #list;
list[at] = list[at] + 1
if list[at] > base then
list[at] = 1
if at > 1 then
return successor(list, base, at - 1);
end
else
return true;
end
end
function numsToString(list, char)
local r = ""
for i = 1, #list do
r = r .. char:sub(list[i], list[i])
end
return r
end
-- Going over all of the options:
local chars = "abc"
local k = {1, 1, 1, 1}
repeat
print(numsToString(k, chars));
until not successor(k, #chars);
This will still have to consider a very large number of strings, but it does it in much less memory, so this will actually be able to be usable (just extremely slow)
-
Actually, it's might not be that bad, as long as you're really using strings. But it will still be really bad (and the less memory use will come at a high performance cost) ↩
0
Note: This is a difficult question to compute. Any answer is probably going to be pretty slow, because you will need to do many calculations regardless of what approach you use. Beware.
Probably the most intuitive answer to this problem is to go through all permutations and then eliminate permutations that aren't unique combinations.
The first thing we want to do is get all permutations of a set of elements. My favorite algorithm to use is the QuickPerm algorithm. Below is an implementation of QuickPerm with a function parameter execute that executes every time QuickPerm calculates a new permutation. This will be useful for solving our problem, because then we just have to eliminate permutations that aren't unique combinations.
function executeOverPermutations(array, execute)
-- QuickPerm algorithm implementation
local function getArrayOfZeroes(size)
local array = { }
for index = 0, size - 1 do
array[index] = index
end
return array
end
local size = #array
local p = getArrayOfZeroes(size + 1)
array[0] = array[size]
array[size] = nil
local index = 0
while index < size do
p[index] = p[index] - 1
swapIndex = index % 2 == 1 and p[index] or 0
local savedValue = array[swapIndex]
array[swapIndex] = array[index]
array[index] = savedValue
execute(array)
index = 1
while p[index] == 0 do
p[index] = index
index = index + 1
end
end
return p
end
One of the best ways to check if two permutations are the same combination is comparing the two when they are ordered. For example...
function areArrayElementsSame(a, b)
for index = 1, #a do
if a[index] ~= b[index] then
return false
end
end
return true
end
local a = {1, 2, 3}
local b = {3, 1, 2}
table.sort(a) -- orders a
table.sort(b) -- orders b
print(areArrayElementsSame(a, b))
For this problem we will use table.sort because its comparison algorithm is good enough to differentiate between capital letters, lowercase letters, and numbers. We will first sort the permutation (which should be in an array) and then check if it already exists within a lookup table that we have created. If it does not exist in there yet, we just add it to the lookup table.
local combinations = { }
function addTableToCombination(combination)
table.sort(combination)
local uniqueCombination = table.concat(combination)
if not combinations[uniqueCombination] then
combinations[uniqueCombination] = true
print(uniqueCombination)
end
end
Putting all of this together, we get an answer...
local maxLength = 3
local source = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"
local combinations = { }
function getArrayFromString(str)
local array = { }
for strIndex = 1, #str do
local character = str:sub(strIndex, strIndex)
array[strIndex] = character
end
return array
end
function addTableToCombination(combination)
table.sort(combination)
local uniqueCombination = table.concat(combination)
if not combinations[uniqueCombination] then
combinations[uniqueCombination] = true
end
end
function executeOverPermutations(array, execute)
-- QuickPerm algorithm implementation
local function getArrayOfZeroes(size)
local array = { }
for index = 0, size - 1 do
array[index] = index
end
return array
end
local size = #array
local p = getArrayOfZeroes(size + 1)
array[0] = array[size]
array[size] = nil
local index = 0
while index < size do
p[index] = p[index] - 1
swapIndex = index % 2 == 1 and p[index] or 0
local savedValue = array[swapIndex]
array[swapIndex] = array[index]
array[index] = savedValue
execute(array)
index = 1
while p[index] == 0 do
p[index] = index
index = index + 1
end
end
return p
end
function main()
local sourceTable = getArrayFromString(source)
local buffer = { }
executeOverPermutations(sourceTable, function(combination)
for index = 1, maxLength do
buffer[index] = combination[index - 1]
end
addTableToCombination(buffer)
end)
end
main()
Hello me, I managed to answer myself, here's what I used. I realised I need to use recursion. BlueTaslem's way is way simpler, go use that.
function stringCombinations(chars, maxLen)
local TO_RETURN, a = {}, {};
local vals = {};
for i=1, #chars do
table.insert(vals, chars:sub(i,i));
end
local function aux(m) -- you need recursion
for i=1, #vals do
a[m] = vals[i];
if m <= maxLen then
aux(m + 1);
else
local s = table.concat(a);
table.insert(TO_RETURN, s);
end
end
end
aux(1);
return TO_RETURN;
end
--------------------------------------------------------
local r = stringCombinations("abcdefg", 2)
print("Number of stringCombinatons: "..#r..";")
for i,v in next, r do
print(string.format(
" [%0"..#tostring(#r).."i]: %s",
i, v
))
game:service'RunService'.RenderStepped:wait()
end