Combination generation

[S_ngng]

I’m having trouble trying to go about generating something

essentially im trying to replicate the countdown letters game and the part i am stuck on is generating all possible combinations of a list of 9 letters which it takes as a parameter, each letter only being used once. another parameter it should take is a number that defines how long the combinations should be. for example, if the list is [“a”,“s”,“d”,“e”,“t”,“u”,“b”,“x”,“a”], and the length number is 5, it should generate all possible ways those 9 letters could be combined to produce combinations of length 5. i also have a binary search function that should check each combination against a word list and if it is valid, adds it to a list

any help with the logic of how to go about this would be much appreciated as im stuck at the minute

[Chung_Xa]

What are you stuck at the moment?

[Pawel]

Do you need combinations in specific order or not? With repetitions or not? It’s generally more of a mathematical questions, because either combination or permutation formula might be useful for you

But I guess, if you have already the binary search function to check against possible word list, you are on a very good track and you only need non-repeating characters combinations, right?

You can either write some recursive function for this or write an iterator creator with coroutines or use some existing math library maybe?

Here’s somehow related topic: Generating all combinations from a table in Lua - Stack Overflow

You can treat it rather as a pseudocode, because I didn’t check it, but perhaps something like this should be a solution for you:

local function combinations(arr, len)
    local function iter(comb, index)
        if #comb == len then
            coroutine.yield(comb)
        else
            for i = index, #arr do
                table.insert(comb, arr[i])
                iter(comb, i + 1)
                table.remove(comb)
            end
        end
    end
    return coroutine.wrap(function() iter({}, 1) end)
end

And then use it:

for comb in combinations(letters, length) do
        local word = table.concat(comb)
        if binary_search(word_list, word) then
            table.insert(valid_combinations, word)
        end
    end

Where binary_search is your function to check valid words and save it in some valid_combinarions table

[S_ngng]

Currently its trying to find or implement the basic logic of using nine letters to create a set of all combinations possible of a specified length

[S_ngng]

Thank you so much for this it has been very helpfull so far. When ive tried implementing this with my own code it seems hat sometimes it doesnt return enough valid words even tough more valid words exist in the dixtionary file

------------------------------------------------------------------------------------------------------------------------------
local function combination_search(arr, len)
	local function iter(comb, index)
		if #comb == len then
			coroutine.yield(comb)
		else
			for i = index, #arr do
				local newComb = {}
				for _, v in ipairs(comb) do
					table.insert(newComb, v)
				end
				table.insert(newComb, arr[i])
				iter(newComb, i + 1)
			end
		end
	end

	return coroutine.wrap(function() iter({}, 1) end)
end

-------------------------------------------------------------------------------
--implementation

for comb in combination_search(solve, i) do
	local word = table.concat(comb)
	if search(word, splitList) == "found" and #valid < 5 then
		if #valid == 0 or valid[#valid] ~= word then
			table.insert(valid, word)
			print(word)
		end
	end
	if #valid >= 5 then
		break
	end
end

is it something wrong with how i have implemented the check for the list being 5 long or could it be something else. i do realise you said it is untested but i would appreciate it if i could get some help with making sure it works fully

[Pawel]

@S_ngng

it doesnt return enough valid words even tough more valid words exist in the dixtionary file

But you write there is limit up to 5 valid words to be found.

if #valid >= 5 then
	break
end

Do you mean this or there is sometimes even less than 5 words found?

What is implementation of search ?

Could you please add it here?

https://defold.com/codepad/#?c=#cp_sprite&s1=GYVwdgxgLglg9mABDMMoAoDOBTANsASgCgBIAczgDoBDVAW2qm3QCJKWAaRFgBzkzTwwlAJ6dEFSgAUAMgEEAmgCE5AYQDSAfRkB5HVM1SAkgDkA4lJ3muARgAMdrpICicgMqmz2064BKXACZiElJcOAhqXERMOFwAN2xEAF5EAG8Acmp0jnSAI2z0iAKAEwLsAuACsgKACwKYAoArAoBrAtwCqHSAX1DwyMRcbDAyKBrkxBsAZj6IqLjImGKJ1N6SMLnonlw0GRhMKBW86lysrjzsUvPgGDIaruudu4fEdMbsF/Sn++zXmphGtQIG1zrBgb90rBnhDijAIOVzmQTuU1rMBqBILAEIgIHA6LkUIwhJocNQAE4QGroclkrhDMDERBMxDrfpRDHQITIJhk9C4/FcFDFbAAD0ZzJIJBgwEQAGJ+blkil6YgxsMiMyWZLcWS4CBYGBsKIYHhiny8blxUzJXgcBqJZLgHAycgJkLRVxZTTEMU4PbrZLWZtDQB3VQWla9TWBkhOl2aLhxZBIGA8agwMmYc34gg+v3RmNQE5DSgoHBkjCh8MCxBxK1am1gYr+hskIu5Etl7AV9BVi1cGkAbRgAF16zG0N3e9gw/3XQBqSbjxvNgvDVcS9ctlskMkfEBkpA6vUGo0hsnUHjoDlYsDoXOT3mrWy59f1rctgC035/v7//4AwCgOAkDQM/L9PxgOhtmwOhhiLW8iBbOMcQjFBUPxQlbxJbByUpLBYgSOlhlGGpc19HcNgGENnWWFJ2xLXFIEYbNLR3aVolwikqRoslii4TBtl2fYoFzJIUhYJ1wGKFhEFoZZZQWHZlgAHkQABWVUanVAsOMUxY6JSOxEGdWsDMHfTlJHRAAD8Ul45Y1TAHdJQYo0ux7JSli4BzlxIHgyRQDBfJcrdozCiU9K85YAD4Uk0pyXNyPdqBaHcIqZDLEBbHgAqC9BovrbcPxvLkbjASIsDwQgkJK8BOWxEAeGKRhmBwfAuGKUTaqbJDSuxBBNDgzBMGoMg2uqrhhtG8bNG8xBprG7ABPXbtiCIOrMS5QaUB4fUqo6uSGrAOb+KO291s246TJOvcwmoM12pqjbeqAA===

Edit.

The combinations functions is not returning proper strings, it’s wrong

[S_ngng]

what i meant with the enough words is any time i try to generate a valid combination of 5 letters or longer, there are no words returned from the combination when there should be

for example here, lengths 2,3 and 4 return enough for the chosen letters (zptfeamla) but nothing is returned for 5 when there should be at least 5 valid words which ive checked against an online word generator

https://defold.com/codepad/#?c=#cp_sprite&s1=GYVwdgxgLglg9mABDMMoAoDOBTANsASgCgBIAczgDoBDVAW2qm3QCJKWAaRFgBzkzTwwlAJ6dEFSgAUAMgEEAmgCE5AYQDSAfRkB5HVM1SAkgDkA4lJ3muARgAMdrpICicgMqmz2064BKXACZiElJcOAhqXERMOFwAN2xEAF5EAG8Acmp0jnSAI2z0iAKAEwLsAuACsgKACwKYAoArAoBrAtwCqHSAX1DwyMRcbDAyKBrkxBsAZj6IqLjImGKJ1N6SMLnonlw0GRhMKBW86lysrjzsUvPgGDIaruudu4fEdMbsF/Sn++zXmphGtQIG1zrBgb90rBnhDijAIOVzmQTuU1rMBqBILAEIgIHA6LkUIwhJocNQAE4QGroclkrhDMDERBMxDrfpRDHQITIJhk9C4/FcFDFbAAD0ZzJIJBgwEQAGJ+blkil6YgxsMiMyWZLcWS4CBYGBsKIYHhiny8blxUzJXgcBqJZLgHAycgJkLRVxZTTEMU4PbrZLWZtDQB3VQWla9TWBkhOl2aLhxZBIGA8agwMmYc34gg+v3RmNQE5DSgoHBkjCh8MCxBxK1am1gYr+hskIu5Etl7AV9BVi1cGkAbRgAF16zG0N3e9gw/3XQBqSbjxvNgvDVcS9ctlskMkfEBkpA6vUGo0hsnUHjoDlYsDoXOT3mrWy59f1rctgC035/v7//4AwCgOAkDQM/L9PxgOhtmwOhhiLW8iBbOMcQjFBUPxQlbxJbByUpLBYgSOlhlGGpc19HcNgGENnWWFJ2xLXFIEYbNLR3aVolwikqRoslii4TBtl2fYoFzJIUhYJ1wGKFhEFoZZZQWHZlgAHkQABWVUanVAsOMUxY6JSOxEGdWsDMHfTlJHRAAD8Ul45Y1TAHdJQYo0ux7JSli4BzlxIHgyRQDBfJcrdozCiU9K85YAD4Uk0pyXNyPdqBaHcIqZDLEBbHgAqC9Bovrbctyo9lwE5bFSW49AHK4WEKrAckRFzYCCUaskRE4vCajRKIwhDCYbF6xB/juCZZXq28muGqSmwmYBIjtEgQ3+IZEDAOBDlm5Z5MGOABpUlJRvGCjJVKxA6CWPggomBgxkoYAwmddB0H6xBF2O3MAHpECCUggwGS7igAdVoiZJqEJrByB66wCgEd/o4oHQb4pVEAcrT1UDbaJigMkQGwf7bWwJGlhR1T0bBxLAzelIYbgG7FyGm1cCWyVjtuq6GbhxBP0mImm1ILcpRlHHqd3fdD24baWCF1nCclPcoAPJAWA2qBZZILcPxvLkbka3AsDwQgkJ18rb0QEAeGKRhmBwfA6tE03BaIXXsQQTQ4MwTBqDIO3ja4L2fb9zRvIu7Bvd97ABPXbtiCIM3MS5D2UB4fUjYduSGtD/is9vePE4akywE0PcwmoM17ZNhPBaAA=

[Alex_8BitSkull]

Disclaimer: Used an AI to generate the permutation/concatenation algorithm, so tread with caution. Wrote the second part (matching permutations to valid words) myself.

-- Function to generate permutations
local function permutations(t)
    local n = #t
    if n <= 1 then
        return {t}
    end

    local perm = {}
    for i = 1, n do
        local rest = {}
        for j = 1, n do
            if j ~= i then
                rest[#rest + 1] = t[j]
            end
        end
        local p = permutations(rest)
        for _, v in ipairs(p) do
            v[#v + 1] = t[i]
            perm[#perm + 1] = v
        end
    end
    return perm
end

-- Main function to generate concatenated strings
local function generateConcatenations(letters)
    local perms = permutations(letters)
    local concatTable = {}
    for _, perm in ipairs(perms) do
        concatTable[#concatTable + 1] = table.concat(perm)
    end
    return concatTable
end

local letters = {"a", "b", "c",}
local concatenations = generateConcatenations(letters)

print("all possible permutations:")
for _, str in ipairs(concatenations) do
    print(str)
end

local valid_words = {"abc", "acb", "cba"}
local num_valid_target = 2 --how many valid words do we need before stopping search
local valid_words_found = {}

for _, str in ipairs(concatenations) do
    for valid_i, valid_word in ipairs(valid_words) do
        if str == valid_word then
            table.insert(valid_words_found, str)
            break
        end
    end
    if #valid_words_found >= num_valid_target then
        break
    end
end
print("")
print("valid words found:")
for i, valid_word in ipairs(valid_words_found) do
    print(valid_word)
end

This outputs:

all possible permutations:
cba
bca
cab
acb
bac
abc

valid words found:
cba
acb 

Which is what I think you’re looking for?

[S_ngng]

With adding another print statement to print “nothing” when a word is checked but not added when adding up amounts of checks for the letter lengths i get: 4 = 126, 5 = 126, 6 = 84, 7 = 34, 8 = 9, 9 = 1. So im unsure whats happening

[S_ngng]

could you also explain how this part works please