Forums Technical Discussion Combinational sum in a given array

Combinational sum in a given array

   1801   7   0
User Avatar
Irinel
Member
12 posts
Joined: May 2016
Offline
 
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:
int iter = chi("iter");
int k = 16;
int result;
int array[] = {17,7, 4, 2, 1};
int comb[];

for(int n=0; n<iter ; n++)
{
    append(comb, array[n]);
    result = sum(comb);
    if(result==k)
    {
        return;
    }
}
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 .
 Report
User Avatar
animatrix_
Member
4495 posts
Joined: Feb. 2012
Offline
 
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.
Senior FX TD @ Industrial Light & Magic
Get to the NEXT level in Houdini & VEX with Pragmatic VEX! [www.pragmatic-vfx.com]

youtube.com/@pragmaticvfx | patreon.com/animatrix | animatrix2k7.gumroad.com
 Report
User Avatar
Irinel
Member
12 posts
Joined: May 2016
Offline
 
@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?
 Report
User Avatar
tamte
Member
8521 posts
Joined: July 2007
Online
 
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]
Tomas Slancik
FX Supervisor
Method Studios, NY
 Report
User Avatar
Irinel
Member
12 posts
Joined: May 2016
Offline
 
@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 .
 Report
User Avatar
Irinel
Member
12 posts
Joined: May 2016
Offline
 
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...
 Report
User Avatar
animatrix_
Member
4495 posts
Joined: Feb. 2012
Offline
 
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]
Senior FX TD @ Industrial Light & Magic
Get to the NEXT level in Houdini & VEX with Pragmatic VEX! [www.pragmatic-vfx.com]

youtube.com/@pragmaticvfx | patreon.com/animatrix | animatrix2k7.gumroad.com
 Report
User Avatar
Irinel
Member
12 posts
Joined: May 2016
Offline
 
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):
float target = chi("target");
int array[] = {177, 167, 157, 147, 137, 127, 117, 107, 97, 87, 77, 67, 57, 47, 37, 27, 17, 7, 4, 3, 2, 1};
i[]@combination;

foreach(int item; array)
{
    if(target==0)
    {
        break;
    }
    if(item/target==1)
    {
        append(@combination, item);
        break;
    }
    if(item/target<1)
    {
        append(@combination, item);
        target = target-item;    
    }
}
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.
 Report
  • Quick Links