A function that returns all possible combinations of a sequence

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By blurymind
:warning: Old Version Published before Godot 3 was released.

Basically I am trying to write a function in gdscript that returns an array of all possible combinations of a sequence of numbers.

something similar to this:

Class1 = [1,2,3,4] Class2 = [1,2,3,4] Class3 = [1,2,3,4]

Now what I would like to do is return all possible combinations of
these three classes.

Example:

1 1 1
2 1 1
3 1 1
4 1 1
1 2 1
2 2 1
3 2 1
4 2 1…

In my case the number of classes and the number of items in each class varies

The top answer for this is:

import itertools
iterables = [ [1,2,3,4], [88,99], ['a','b'] ]

for t in itertools.product(*iterables):
     print t

Looking at itertools, this is how the product function there looks like:

def product(*args, repeat=1):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

Can you guys please help me somehow get this functionality translated to gdscript please?
I am really struggling with this one!

:bust_in_silhouette: Reply From: Omicron

You can’t really translate such pythonic code to GDscript.

But why do you want to store those combinations ?

Also, just think how you would do to enumerate all possible combinations for a lock of 3 digits. This is a very similar case.

I am storing them in order to create an array that holds all possible procedurally generated enemies or any type of game objects.

This gives me much more flexibility and cleaner code further down.
I can’t really understand your suggestion to implement it. Would you care to please share some example code?

blurymind | 2017-06-19 10:36

Also note that the function that I need requires to be able to use a different number of digits (not specifically only 3). Also each digit needs to be able to contain more than 0-9

Itertools.prodcut can do this easily.
Writing a loop in gdscript that does that is really difficult , you can try if you want to

blurymind | 2017-06-19 10:40

Up to how many ClassX and their max sizes ?
This could be quite inefficient, memory-wise, if it gets too huge in case you reall store them all.

One simple way to generate all possible indexes, I see is :
(pseudo code) + (there is more optimized way, but here not worth it, and this one is easy to understand)

my_list = []
for seed in range(Class0.size() * Class1.size() * ... * ClassN.size()):
    my_list.append(combination(seed, list_of_classes)); 
    // or do something else if you don't really need to store

with combination function being :

function combination(int seed, list_of_classes):
    result = []
    for my_class in list_of_classes:
        result.append(seed % my_class.size())
        seed = seed / my_class.size()
    return result

enjoy :wink:

Omicron | 2017-06-19 11:11

Thank you for the function. Unfortunately did not work :slight_smile:
Godot marked the use of ‘seed’ in a for loop as an error. I renamed it to another word that is not taken (seede).
When running the function, I got a nonsensical result:

RESULTS 2:[0, 0, 0, 0]
RESULTS 2:[1, 0, 0, 0, 0]
RESULTS 2:[2, 0, 0, 0, 0, 0]
RESULTS 2:[0, 1, 0, 0, 0, 0, 0]
RESULTS 2:[1, 1, 0, 0, 0, 0, 0, 0]
RESULTS 2:[2, 1, 0, 0, 0, 0, 0, 0, 0]
RESULTS 2:[0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
RESULTS 2:[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
RESULTS 2:[2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
RESULTS 2:[0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
RESULTS 2:[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
RESULTS 2:[2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
RESULTS 2:[0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
RESULTS 2:[1, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
RESULTS 2:[2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
RESULTS 2:[0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
RESULTS 2:[1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
RESULTS 2:[2, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

In any case, I solved this by writing my own function that generates a custom for loop script, which it then runs. It’s an ugly hack, but it works at least. :smiley: I suggested this feature being added to godot at the bug tracker and Bogdan seems to have liked it.
Maybe some of the future versions will have a cleaner approach to this challenge

blurymind | 2017-06-20 09:13

Result looks ok, combination-wise.
There are just zeros appended, while they should not.
It is just that you probably don’t initialize result var properly / messing with var scope or wrong number of ClasseXs being incremented for whatever reason.

Omicron | 2017-06-20 09:28

:bust_in_silhouette: Reply From: blurymind

The simple way to do this in gdcript would be:

class = [[1,2,3],[1,2],[1,2,3]]
	for a in class[0]:
		for b in class[1]:
			for c in class[2]:
				print (a,b,c)

However it doesnt work, because it cant be reused as a function - it has a very specific number of classes

The difficulty comes when you try to proceduraly construct a loop that works on any number of classes

You could use funcrefs to execute various things without changing the loop, this way you won’t have to rewrite the whole iteration just to change the inner operation

Zylann | 2017-06-19 11:03

Can you share some example code please?
I have never used funcrefs before, so I am going to look into this now

blurymind | 2017-06-19 11:06

I wrote a function that generates a for loop script and runs it. Its a hack, but it works :smiley:

blurymind | 2017-06-20 09:41

You can’t be serious xD
That’s a scripting language, you can do way better than that, even in C++ you can do function pointers to improve on this, even with no itertools to generate all combinations in an array and needlessly occupy memory.

Here is a quick example of funcrefs for iteration:

for_all_classes(class, funcref(self, "print_action"))	
for_all_classes(class, funcref(self, "other_action"))
#...


func for_all_classes(class, action)
	for a in class[0]:
		for b in class[1]:
			for c in class[2]:
				action.call_func (a,b,c)


func print_action(a, b, c):
	print(a,b,c)

func other_action(a, b, c):
	#...

Zylann | 2017-06-20 09:48

:bust_in_silhouette: Reply From: Brice

Something like that ?

var a = [[1,2,3],[4,5],[6,7,8],[9,10]]
for i in compute(a): print(i)

func compute(a): # Array<Array<int>> : Array<Array<int>>

var r = []
var a0 = a[0]

if a.size() == 1:
	r.append(a0)
	return r

var a1
var t

if a.size() > 2:
	a.pop_front()
	a1 = compute(a)

	for i in a0:
		for j in a1:
			t = []
			t.append(i)
			for k in j: t.append(k)
			r.append(t)

else :
	for i in a0:
		for j in a[1]:
			t = []
			t.append(i)
			t.append(j)
			r.append(t)

return r

This is it! This function worked and it did what I wanted! :smiley:

I wrote a much uglier function that does it yesterday too, but your function is better I think.
Here was my approach that also solves it:

func createArrMixes(layers): #return array of combinations [[1,1,1],[1,1,2], ..etc]
	var layerIterationScript = "func mix():"
	layerIterationScript += "\n\tvar layers = " + str(layers) + "\n"
	layerIterationScript += "\n\tvar outputMixes = []\n"
	layerIterationScript += "\n\tvar mixResult= []\n"
	
	var tabsInFunc = ""
	var mixLayersOutputString = ""
	
	for line in range(layers.size()):
		tabsInFunc += "\t"
		layerIterationScript += tabsInFunc + "for layer" + str(line) + " in layers[" + str(line) + "]:"
		if line != 0:mixLayersOutputString += ","
		mixLayersOutputString += "layer" + str(line)
		layerIterationScript += "\n"
	tabsInFunc += "\t"
	for line in range(layers.size()):
		layerIterationScript += tabsInFunc + "mixResult.append(layer" + str(line) + ")\n"
	layerIterationScript += tabsInFunc + "outputMixes.append(mixResult)\n"
	layerIterationScript += tabsInFunc + "mixResult = []\n"
	layerIterationScript += "\treturn outputMixes\n\n"

	var newScriptMix = GDScript.new()
	newScriptMix.set_source_code(layerIterationScript)
	newScriptMix.reload()
	
	var tmpObj = Reference.new()
	tmpObj.set_script(newScriptMix)
	var finalResultOfTheMix = tmpObj.mix()
	return tmpObj.mix()

blurymind | 2017-06-20 09:20