# Combination generation

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

What are you stuck at the moment?

1 Like

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

2 Likes

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

1 Like

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

1 Like

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` ?

Edit.

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

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

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?

1 Like

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

could you also explain how this part works please