Hey folks,

I am trying to solve a combinational sum issue in vex. So I have a given value of k, lets say 16 and specific items in an array, lets say {17,7,4,2,1}. I want Houdini to give me at least the first combination (ideal would be the shortest one) of items that results in k as an array.
My not so charming start:
How can I tell Houdini, if the result is not equal to k, try another combination. But also limit the comb array to max 3 items (I dont want a combination like {1+1+1+1+1+1+1...}. And if nothing is ever found, then it is allowed to expand the items count as long as it needs to find the first combination.
Sorry for the dumb question, I am not really good at vex, but want to get better. Thanks everyone .

Hi,

I would just use Python permutations for this:
https://www.geeksforgeeks.org/permutation-and-combination-in-python/ [www.geeksforgeeks.org]

The performance difference should be negligible.

@animatrix_ thank you very much, that helps a lot and is pretty easy. But I have now the problem that I cant get that into an attribute.

point.setAttribValue("combination", i)

would not work here. Can you point out, what I am missing? Maybe a different syntax for writing arrays as attributes?

this article seems to be addressing your issue almost exactly, you may find it interesting
https://www.baeldung.com/cs/subset-of-numbers-closest-to-target [www.baeldung.com]

@tamte this article explains it quite good. Unfortunately my skill level is not even near the quality needed to understand how I could implement that in python or vex in Houdini. I guess I need to dive a bit deeper. Thank you very much .

So, unfortunataly the permutations in python will only give me all unique rearrangements of my elements. It's also factorial. So when I am going to have, lets say 21 elements in my array, and I need the shortest combination to get a target sum, this will give me an unbearable amount of data, of which non of it might hold the right sum. In fact the sum will stay the same in each permutation, cause its "just" a rearrangement.

Maybe the "combinations_with_replacement" might be a better solution for that case and just working with a count as array length instead of a static one. That will give me at least every possible set, including using the same element more than once.

Will dig deeper in the "Backtracking/ Meet in the middle" approach as well, since it seems to provide much more control. Would be cool, if I can pull off a vex solution for that, but my monkey brain has its limitations I guess...

Irinel
@animatrix_ thank you very much, that helps a lot and is pretty easy. But I have now the problem that I cant get that into an attribute.

point.setAttribValue("combination", i)

would not work here. Can you point out, what I am missing? Maybe a different syntax for writing arrays as attributes?

You can use hou.Geometry.addArrayAttribute:

https://www.sidefx.com/docs/houdini/hom/hou/Geometry.html [www.sidefx.com]

Thanks everyone for their help. If anyone is interested, I was finally able to wrap something up in vex though. In case it's useful for you, this is how it works (it is not perfect at all, but seems to get the job done):
The code requires that the target could be covered up by the items in the array. In this case it begins with the biggest item (due to sorting), tries to fit that in and if it does, it adds it to the combination, updates the target and moves on until the last bit of the target is reached.