Advertisement
If you have a new account but are having problems posting or verifying your account, please email us on hello@boards.ie for help. Thanks :)
Hello all! Please ensure that you are posting a new thread or question in the appropriate forum. The Feedback forum is overwhelmed with questions that are having to be moved elsewhere. If you need help to verify your account contact hello@boards.ie
Hi there,
There is an issue with role permissions that is being worked on at the moment.
If you are having trouble with access or permissions on regional forums please post here to get access: https://www.boards.ie/discussion/2058365403/you-do-not-have-permission-for-that#latest

need an algorithm !

  • 25-01-2008 4:01pm
    #1
    Closed Accounts Posts: 426 ✭✭


    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


Comments

  • Closed Accounts Posts: 81 ✭✭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);
                }
            }
        }
    


  • Registered Users, Registered Users 2 Posts: 304 ✭✭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


  • Closed Accounts Posts: 426 ✭✭roughan


    any VB6 examples


  • Closed Accounts Posts: 4,943 ✭✭✭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.


  • Closed Accounts Posts: 426 ✭✭roughan


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


  • Advertisement
  • Closed Accounts Posts: 81 ✭✭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();
                }
            }
        }
    }
    


  • Registered Users, Registered Users 2 Posts: 304 ✭✭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


  • Closed Accounts Posts: 426 ✭✭roughan


    God isnt everone very angrt in this Forum!!

    Anyway thanks for the help
    R


  • Registered Users, Registered Users 2 Posts: 9,579 ✭✭✭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.


  • Closed Accounts Posts: 426 ✭✭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


  • Advertisement
  • Registered Users, Registered Users 2 Posts: 9,579 ✭✭✭Webmonkey


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


  • Registered Users, Registered Users 2 Posts: 413 ✭✭ianhobo


    a + b + c ? :D


  • Registered Users, Registered Users 2 Posts: 2,534 ✭✭✭FruitLover


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


Advertisement