Scripting HelpersARCHIVE
A little piece of Roblox history. Preserved for everyone, one question at a time.Read about the archive →
✓ ANSWER ACCEPTED

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

5 comments

0

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

0

Combination. [As I said, I didn't get really close :( ]

0

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.

0

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

0

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.

3 answers

✓ Accepted answer

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:


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 store[^1].

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)

[^1]: 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)

1 comment

0

Thanks for the detailed explanation, I managed to answer myself, but this is way simpler.

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

This discussion is preserved as it was. New answers, comments, and votes are closed.