Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C++ C Java
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:
 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 9:04am
Comments
Sergey Alexandrovich Kryukov at 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 at 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

Rate this: bad
good
Please Sign up or sign in to vote.

Solution 1

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.
 
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.
  Permalink  
Comments
CPallini at 9-Apr-13 16:41pm
   
Very, very nice. 5++.
nv3 at 9-Apr-13 16:48pm
   
Thank you!
H.Brydon at 12-Apr-13 14:30pm
   
Just a guess but this looks like you did somebody's homework for them. (+5 anyhow, yeah I'm back)
nv3 at 12-Apr-13 14:53pm
   
Could well be; but it looked non-trivial and interesting enough to me. Thanks, H.

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

  Print Answers RSS
0 OriginalGriff 381
1 Praneet Nadkar 237
2 Marcin Kozub 225
3 Sergey Alexandrovich Kryukov 200
4 Shweta N Mishra 161
0 OriginalGriff 8,284
1 Sergey Alexandrovich Kryukov 7,327
2 DamithSL 5,614
3 Manas Bhardwaj 4,986
4 Maciej Los 4,920


Advertise | Privacy | Mobile
Web01 | 2.8.1411023.1 | Last Updated 9 Apr 2013
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100