12,399,561 members (62,203 online)
Rate this:
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:
```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

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.

Rate this:

## 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.
CPallini 9-Apr-13 16:41pm

Very, very nice. 5++.
nv3 9-Apr-13 16:48pm

Thank you!
H.Brydon 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 12-Apr-13 14:53pm

Could well be; but it looked non-trivial and interesting enough to me. Thanks, H.

Top Experts
Last 24hrsThis month
 ppolymorphe 380 OriginalGriff 355 Vincent Maverick Durano 265 0x01AA 195 Karthik Bangalore 135
 OriginalGriff 6,723 ppolymorphe 2,835 Karthik Bangalore 2,707 Richard MacCutchan 2,057 F-ES Sitecore 2,052