Find all vectors with sum equal of vector elements and elements not bigger of k without recursion

Question

1.60/5 (2 votes)

See more:

I want to find all vectors with sum equal of vector elements and elements not bigger of k but without using recursion. For example in number of vector elements n is 5, sum=10 and k=3 than, the output will be:

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

The source code with using recursion in Java is:

Java

private static void printVectors(int p[], int n) {

       for (int i = 0; i < n; i++) {
           System.out.print(p[i] + " ");
       }
       System.out.println();
   }

   private static void computeVectors(int[] n, int sum, int k, int k1, int i) {


       if (sum == 0) {

           printVectors(n, n.length);
       } else if (i < n.length) {

           for (int j = k; j >= 0; j--) {

               if (j <= k1) {
                   n[i] = j;
                   computeVectors(n, sum - j, sum - j, k1, i + 1);
               }
           }
       }
   }

My question is how to redesign computeVectors() function without using recursion?

Posted 9-Apr-13 8:04am

zlristovski

Add a Solution

Comments

Sergey Alexandrovich Kryukov 9-Apr-13 14:22pm

You need to formulate it exactly. This isn't clear: "all vectors with sum equal of vector elements and elements not bigger of k".
Anyway, what did you try?
—SA

zlristovski 9-Apr-13 15:56pm

This question is connected with partition number, but it's not same, in my question you have and example with some of the output. Basically, the function should return all vectors with size n who satisfy some conditions, in this case condition is: sum of all elements in vector must be one value, every element in vector must be smaller from some number, in this that number is k.

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

nv3 · Accepted Answer · 2013-04-09T10:03:00

Let me rephrase your question: I understand you want to enumerate all vectors of length dim, in which each element can have a value of [0 ... K] and for which the sum of all elements is N.

One easy approach would be to enumerate all vectors of length, in which the elements have a value of [0 ... K]. That's K to the Nth combinations. Then for every such vector check whether its element sum is N. Although that might work for small N and K, it is a rather time consuming approach.

For large N and K the following approach might be faster: Think of the sum N as collection of balls that we want to distribute into dim bins. Start by distributing them into the first bins, always spending as many balls as fits into the bin. For N = 5, K = 3 and dim = 4 that would deliver:

3 2 0 0

We call this kind of distribution a "left-most" distribution as all balls reside as far left as posible according to our rules.

Now try to move a single ball at the time. We always take the first ball from the left that we can pick and only carry it forward a minimal number of bins until we can drop it legally. In our example that would yield

2 3 0 0

There is one more rule to consider: As soon as we have dropped a ball, we must redistribute the balls to its left to form a left-most configuration. So our next step will take one ball out of the left bin in drop it into the third bin, after which we redistrubte the remaining four balls anew:

3 1 1 0

We simply continue with these rules until we are no longer able move a ball forward. The following code represents these rules. I have written it in simple C-like style, so you can adapt it to whatever programming language you like.

C++

void Distribute (int* vec, int dim, int k, int n)
{
    for (int idx = 0; idx < dim; ++idx)
    {
        vec[idx] = min (n, k);
        n -= vec[idx];
    }
    assert (n == 0);
}

bool MoveUp (int* vec, int dim, int k)
{
    int collected = 0;
    for (int idx = 0; idx < dim; ++idx)
    {
        if (collected == 0)
            collected = vec[idx];
        else
        {
            if (vec[idx] < k)
            {
                vec[idx] += 1;
                Distribute (vec, idx, k, collected-1);
                return true;
            }
            else
            {
                collected += k;
            }
        }
    }
    assert (collected != 0);
    return false;
}

void PrintVec (int* vec, int dim)
{
    for (int idx = 0; idx < dim; ++idx)
        printf ("%d", vec[idx]);
    printf ("\n");
}

int main()
{
    int vec[4];
    memset (vec, 0, sizeof vec);
    Distribute (vec, 4, 3, 5);
    PrintVec (vec, 4);
    while (MoveUp (vec, 4, 3))
        PrintVec (vec, 4);
    return 0;
}

I guess that demonstrates nicely that it can be done in a simple iterative way - as so many problems. The code is not as elegant as the recursive one, for sure. But that was not your question I guess.