Scripting Helpers is winding down operations and is now read-only. More info→

How to get every possible combination of alphanumeric characters for the given length?

Asked by

Vlatkovski 320

10 years ago

Please make your question title relevant to your question content. It should be a one-sentence summary in question form.

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..

01--Set up the character table
02local chars, charStr = {}, "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
03for i=1,#charStr do
04    table.insert(chars, charStr:sub(i,i))
05end
06 
07setmetatable(chars, { -- make the table loop (magic)
08    __index = function(t, i)
09        return (i>#t and t[i-#t]) or (#t>i and t[#t-i])
10    end
11})
12 
13--Continue
14local maxLen = 3
15local s = ""
16 
17for i=1,(#chars) ^ maxLen do --iterate through the number of possible combinations?
18    if #s == maxLen then
19        local b = false
20        for i,v in next, chars do
21            b = s:sub(1,1) == v and i or false
22            if b then break end
23        end
24 
25        s = b and chars[b+1] or s
26    else
27        s = s .. chars[i]
28    end
29 
30    print(s)
31 
32    wait()
33end
 View all 33 lines...

Do you mean combination or permutation? Combinations are where order doesn't matter, so {1, 2} is the same as {2, 1}. Permutations are where order does matter so {1, 2} is distinctly different from {2, 1}. Unclear 1776 — 10y

Combination. [As I said, I didn't get really close :( ] Vlatkovski 320 — 10y

Not sure what you're trying to do and it's probably above me, but I would like to point out that all those semicolons are not needed in Lua and make it kind of annoying to read. Perci1 4988 — 10y

@Perci1 I know they're not needed, I just got use to them because of other coding/scripting languages. Anyway, I removed some extra stuff so it's easier to read. Vlatkovski 320 — 10y

Good luck. I used the combinations formula to try and do what you want, but the amount of characters you have is way too large. It caused number overflows and froze because it will require billions of looping. MrNicNac 855 — 10y

3 answers

Answered by

BlueTaslem 18071

10 years ago

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 from chars followed by a k-1-string

The code to get all of them, then, would look something like this:

01chars = "abcd"
02 
03-- Returns a list of strings (each of length k)
04-- (Works inductively)
05function kstrings( k )
06    if k == 0 then
07        -- There is only one length 0 string:
08        return {""}
09    else
10        local kminus1s = kstrings( k - 1 ) -- all (k-1)-strings
11        local result = {}
12        for i = 1, #chars do
13            -- chars[i] followed by each (k-1)-string
14            for _, km1 in pairs(kminus1s) do
15                table.insert(result,  chars:sub(i, i) .. km1 )
16            end
17        end
18        return result;
19    end
20end
21 
22print( kstrings(3) )
 View all 22 lines...

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 store¹.

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.

01function successor(list, base, at)
02    at = at or #list;
03    list[at] = list[at] + 1
04    if list[at] > base then
05        list[at] = 1
06        if at > 1 then
07            return successor(list, base, at - 1);
08        end
09    else
10        return true;
11    end
12end
13 
14function numsToString(list, char)
15    local r = ""
16    for i = 1, #list do
17        r = r .. char:sub(list[i], list[i])
18    end
19    return r
20end
21 
22-- Going over all of the options:
23local chars = "abc"
24local k = {1, 1, 1, 1}
25repeat
26    print(numsToString(k, chars));
27until not successor(k, #chars);
 View all 27 lines...

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) ↩

Thanks for the detailed explanation, I managed to answer myself, but this is way simpler. Vlatkovski 320 — 10y

Answered by

Unclear 1776

10 years ago

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.

01function executeOverPermutations(array, execute)
02    -- QuickPerm algorithm implementation
03 
04    local function getArrayOfZeroes(size)
05        local array = { }
06        for index = 0, size - 1 do
07            array[index] = index
08        end
09        return array
10    end
11 
12    local size  = #array
13 
14    local p     = getArrayOfZeroes(size + 1)
15 
16    array[0]    = array[size]
17    array[size] = nil
18 
19    local index = 0
20 
21    while index < size do
22        p[index]            = p[index] - 1
23        swapIndex           = index % 2 == 1 and p[index] or 0
24 
25        local savedValue    = array[swapIndex]
26        array[swapIndex]    = array[index]
27        array[index]        = savedValue
28 
29        execute(array)
30 
31        index               = 1
32 
33        while p[index] == 0 do
34            p[index]    = index
35            index       = index + 1
36        end
37    end
38 
39    return p
40end
 View all 40 lines...

One of the best ways to check if two permutations are the same combination is comparing the two when they are ordered. For example...

01function areArrayElementsSame(a, b)
02    for index = 1, #a do
03        if a[index] ~= b[index] then
04            return false
05        end
06    end
07    return true
08end
09 
10local a = {1, 2, 3}
11local b = {3, 1, 2}
12table.sort(a) -- orders a
13table.sort(b) -- orders b
14print(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.

1local combinations  = { }
2function addTableToCombination(combination)
3    table.sort(combination)
4    local uniqueCombination = table.concat(combination)
5    if not combinations[uniqueCombination] then
6        combinations[uniqueCombination] = true
7        print(uniqueCombination)
8    end
9end

Putting all of this together, we get an answer...

01local maxLength     = 3
02local source        = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"
03 
04local combinations  = { }
05 
06function getArrayFromString(str)
07    local array = { }
08    for strIndex = 1, #str do
09        local character     = str:sub(strIndex, strIndex)
10        array[strIndex]     = character
11    end
12    return array
13end
14 
15function addTableToCombination(combination)
16    table.sort(combination)
17    local uniqueCombination = table.concat(combination)
18    if not combinations[uniqueCombination] then
19        combinations[uniqueCombination] = true
20    end
21end
22 
23function executeOverPermutations(array, execute)
24    -- QuickPerm algorithm implementation
25 
26    local function getArrayOfZeroes(size)
27        local array = { }
28        for index = 0, size - 1 do
29            array[index] = index
30        end
31        return array
32    end
33 
34    local size  = #array
35 
36    local p     = getArrayOfZeroes(size + 1)
37 
38    array[0]    = array[size]
39    array[size] = nil
40 
41    local index = 0
42 
43    while index < size do
44        p[index]            = p[index] - 1
45        swapIndex           = index % 2 == 1 and p[index] or 0
46 
47        local savedValue    = array[swapIndex]
48        array[swapIndex]    = array[index]
49        array[index]        = savedValue
50 
51        execute(array)
52 
53        index               = 1
54 
55        while p[index] == 0 do
56            p[index]    = index
57            index       = index + 1
58        end
59    end
60 
61    return p
62end
63 
64function main()
65    local sourceTable   = getArrayFromString(source)
66    local buffer        = { }
67 
68    executeOverPermutations(sourceTable, function(combination)
69        for index = 1, maxLength do
70            buffer[index] = combination[index - 1]
71        end
72        addTableToCombination(buffer)
73    end)
74end
75 
76main()
 View all 76 lines...

Answered by

Vlatkovski 320

10 years ago

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.

01function stringCombinations(chars, maxLen)
02    local TO_RETURN, a = {}, {};
03    local vals = {};
04 
05    for i=1, #chars do
06        table.insert(vals, chars:sub(i,i));
07    end
08 
09    local function aux(m) -- you need recursion
10        for i=1, #vals do
11            a[m] = vals[i];
12            if m <= maxLen then
13                aux(m + 1);
14            else
15                local s = table.concat(a);
16                table.insert(TO_RETURN, s);
17            end
18        end
19    end
20 
21    aux(1);
22 
23    return TO_RETURN;
24end
25 
26--------------------------------------------------------
27 
28local r = stringCombinations("abcdefg", 2)
29 
30print("Number of stringCombinatons:   "..#r..";")
31 
32for i,v in next, r do
33    print(string.format(
34        "   [%0"..#tostring(#r).."i]:   %s",
35        i, v
36    ))
37    game:service'RunService'.RenderStepped:wait()
38end
 View all 38 lines...

How to get every possible combination of alphanumeric characters for the given length?

3 answers

A better approach? (edited)

Answer this question