need an algorithm !

roughan

hi i need to find an algorithm to find every combination of 3 numbers up to a certain value

so if i pass in 3 i need

3 , 0 ,0
0,3,0
0,0,3
1,1,1
1,0,2


etc

dzy

Here is a recursive algorithm in PHP to do it.

x is the number in question and n is the number of numbers. No guarantees on the efficiency.

    find_sum(3, 3);

    function find_sum($x, $n)
    {
        find_sum_recurse($x, $x, $n, array());
    }

    function find_sum_recurse($x, $z, $n, $list)
    {
        if ($n == 0)
        {
            if ($z == 0)
            {
                var_dump($list);
            }
        }
        else
        {
            for ($i = 0; $i <= $z; $i++)
            {
                array_push($list, $i);
                find_sum_recurse($x, $z - $i, $n - 1, $list);
                array_pop($list);
            }
        }
    }

PhantomBeaker

Strange, I was helping some people out with exactly the same problem in college. Or rather, it was a case of finding neighbouring numbers.

The way I ended up doing something like that would be (and this is off the top of my head, so mileage may vary):

First there were certain constraints in the problem I was given - no number in the triple could be negative.

Let's work through this on paper. Plot out an equilateral triangle with (0,1,0) on top, and (1,0,0) at the bottom left and (0,0,1) on the bottom right.

To move from (1,0,0) to (0,0,1) you apply a transformation (-1, +0, +1) I.e. you're moving to the right of the triangle

To move up-right from (1,0,0) to (0,1,0), you apply a transformation of (-1, +1, 0).

Now, the trick to generating all of the numbers, is to create way to recursively traverse up-right from a point, and adding numbers to a list or whatever, and then also one which will traverse to the node on the right, and then traverse the up-right chain. So, if I was to sketch it in python-like pseudo-code (i.e. this is how I'm doing it off the top of my head, but may not compile in python):

def upRight(node, depth, numlist):
 if(node[0] < 0):
  return
 #endif
 numlist.append(node)
 newnode = (node[0] -1, node[1] + 1, node[2])
 upRight(newnode, numlist)
#enddef

def right(node, numlist):
 if(node[0] < 0):
  return
 #endif
 upright(node, numlist)
 right(node,numlist)
#enddef

def getAllNumbers(startnum):
 numlist = list()
 firstnode = tuple(startnum, 0, 0)
 right(firstnode, numlist)

Now, that's pretty much all I can think of. I hope it makes some degree of sense.

Aoife

roughan

any VB6 examples

Mutant_Fruit

What do you want exactly? Do you want someone else to write the entire thing for you? There's places like www.rentacoder.com if you want that sort of thing. There are two examples there and some good explanations. It shouldn't be that hard to convert it to VB6 yourself.

roughan

no i cat follow the syntax of the examples as im not familiar with them

dzy

I don't have Visual Studio 6 I'm afraid. How about Java?

import java.util.Stack;

class Algorithm
{
    public static void main(String[] args)
    {
        Algorithm a = new Algorithm();
        a.findSum(3, 3);    
    }

    public Algorithm()
    {
    }

    public void findSum(int x, int n)
    {
        findSumRecurse(x, n, new Stack());
    }

    private void findSumRecurse(int x, int n, Stack stack)
    {
        if (n == 0)
        {
            if (x == 0)
            {
                System.out.println(stack);
            }
        }
        else
        {
            for (int i = 0; i <= x; i++)
            {
                stack.push(i);
                findSumRecurse(x - i, n - 1, stack);
                stack.pop();
            }
        }
    }
}

PhantomBeaker

roughan wrote: »

no i cat follow the syntax of the examples as im not familiar with them

Um, no. There's a really good reason I tend to give my answers to (apparently) questions that sound like college homework in languages that are generally not taught by lecturers. Plus I don't know VB6.

If you want another way to think of it, you're more than welcome to it. If you want the answer on a plate, go swim.

The other approach (which is essentially the same but without code, and without that triangle, but better for thinking of it in terms of pure maths):

Given a positive integer n, we're looking for all integer points in 3d space that sum to n. This is your primary invariant

Your secondary invariant is probably that no element may be negative

Another way of saying that is, you're looking for all points within a Manhattan Distance of n from the point (n, 0, 0). That means if you move one unit in one direction, you reduce your first element by one, and increment another dimension by one. This maintains your primary invariant

In other words, you can take one step in any direction, and to maintain your primary invariant. Now, if we only allow ourselves linearly independent moves of (-1, +1, 0) and (-1, 0, -1) we can cover all points we need to with just combinations of those.

That essentially means that you want to visit all points that are n of those steps away, and all of the points in between. So, we just need to devise a method to do that.

So, what we do is we take a step in one direction. We then keep taking steps in the other direction until we reach a point (0, x, y) for some x, y (because the directions we use will always decrement the first element), and record all the points visited. When we've visited all the points on that chain, we step again in our original direction and keep doing that until we reach a point (0, a, b) for some a, b.

So it's a case of (in pseudocode)

function stepY(x, y, z):
if x < 0:
return
endif
visit(x, y, z)
stepY(x-1, y+1, z)
endfun

function stepZ(x, y, z):
if x < 0:
return
endif
# We don't visit this node because stepY will do it for you
stepY(x, y, z)
endfun

You then run it by calling stepZ(n, 0, 0)b

This is a more formal (but not completely formal) and mathematical explanation, just in case your brain works that way. If you have questions about how this works, I'm more than happy to explain it so that you get to a point that you understand enough to write it for yourself in vb6, but I'm not doing your homework for you.

Aoife

roughan

God isnt everone very angrt in this Forum!!

Anyway thanks for the help
R

Webmonkey

If you can't understand pseudocode you might as well quit now and stop wasting your time.

Programming isn't about writing/copying/converting code - its about being able to think and solve problems and I think this is where a lot of people fail.

I am guessing you are a student by the original post thing - The reason your lecturer gave you that is to make you think. Trust me, the more you solve problems, the easier you will find it in the future.

By the way - I am a student too

Best of luck.

roughan

Eh no im not a student its an algortihm i was stuck in for work
for loading combinations of passengers ie adults & children & infants for hotels

ie
given the occupancy for the room ie occupancy is

Room Max occupancy is 3

3 adults 0 child 0 Infants
2 1 0
1 1 1
2 0 1

etc
all i wanted was a little help not lectures
thanks to all who gave me positives

Webmonkey

Ah sorry then - did sound very much like an assignment.

ianhobo

a + b + c ?

FruitLover

Show what you've done so far and we'll give you a nudge in the right direction.