CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: How to distribute a value into vector

1. Member Join Date
Dec 2015
Posts
48

## How to distribute a value into vector

Hi i need help to distribute a value into a vector and print all possible combination for example
If a user input first value that will be the vector size input1size = 15;
Then input2 is the value going to distribute inside the vector . input2 =25;
3rd input is first constant value of the vector input3 = 2 ; then this value minus input2 is the value i need to distribute inside vector

After the distribution vector look like this . When we add vector
Data together the output need to be = to input2 = 25 ; and the first value is user input3;

V1 = {2,9,2,1,1,1,1,1,1,1,1,1,1,1,1} = 25;
V1 = {2,9,1,2,1,1,1,1,1,1,1,1,1,1,1} = 25;
V1 = {2,9,1,1,2,1,1,1,1,1,1,1,1,1,1} = 25;
.........
V1 = {2,1,1,1,1,1,1,8,1,1,1,1,1,1,3} = 25;
So on ..... and find all sequences
How can i do this ...  Reply With Quote

2. Member Join Date
Aug 2006
Posts
232

## Re: How to distribute a value into vector

Find all unique combinations of numbers that have a sum that equals "input2 - input3" and includes "input3". You can think of it like a search tree and use a recursive loop.

Then, with "input3" inserted at the beginning, use std::next_permutation(begin(V1) + 1, end(V1)) to get all possible orders for each of these combinations.  Reply With Quote

3. Member Join Date
Dec 2015
Posts
48

## Re: How to distribute a value into vector Originally Posted by TubularX Find all unique combinations of numbers that have a sum that equals "input2 - input3" and includes "input3". You can think of it like a search tree and use a recursive loop.

Then, with "input3" inserted at the beginning, use std::next_permutation(begin(V1) + 1, end(V1)) to get all possible orders for each of these combinations.
I think the permutations only rearrange value but in my case some time its need to change the value like v1 =
V1 = {2,9,2,1,1,1,1,1,1,1,1,1,1,1,1} = 25;

V1 = {2,10,1,1,1,1,1,1,1,1,1,1,1,1,1} = 25;

V1 = {2,2,2,1,1,1,4,1,1,1,1,3,1,1,1} = 25;  Reply With Quote

4. Member Join Date
Aug 2006
Posts
232

## Re: How to distribute a value into vector

Yes, but the rearranging is the second part of my suggested solution.

In the first part you need to determine the values and update the vector accordingly.

Like I said, one way to do it is to loop recursively. For every iteration, first subtract with the largest number possible, then the second largest, and so on. That way, keep subtracting values that are equal or less than from previous search depth. Keep going until the remaining value reaches 0. If zeroes are allowed in the vector, then just fill any remaining values with zeroes. You can cut off branches in the tree every time the search depth (as limited by input1) is not deep enough to reach 0.

The subtracted values are the ones you will store in the vector.

Try to scetch the tree search on a piece of paper. Start with something simple like 4 as distribution number.
Last edited by TubularX; February 26th, 2016 at 07:26 AM.  Reply With Quote

5. Banned  Join Date
Jun 2015
Posts
208

## Re: How to distribute a value into vector Originally Posted by Ramees219 How can i do this ...
It looks like a problem I've had recently namely how to find all partial derivatives of a certain order and dimension. I solved it as a combinatorics partition problem using bitsets for the implementation.

Say we have a certain sum like 5. We represent it with 5 zeroes like this,

00000

Also we have a vector with a certain number of elements, say 3, which we represent with 3-1=2 ones. We then partition the 5 zeroes with the 2 ones in all possible ways getting different binary patterns like this,

1100000
0110000
0101000
0001100
1000001

Etcetera. The actual number of combinations is the answer to - in how many ways can we place 2 ones at 5+2=7 positions?. This is standard combinatorics and the answer is 7 over 2 = 21. This is also the answer to - in how many ways can we put 5 balls into 3 urns? - which really is what we ultimately are asking.

Also the patterns can be interpreted as bit-sets. Here each of the 7 positions represents a set member and if a position is one that member is present in the set, otherwise not. To generate all such patterns we are looking at generating all 2-subsets of a 7-set in bitset representation. Fortunately there's a nice algorithm for this called Gosper's hack.

Finally we interpret the bitsets as 3 groups of 5 zeroes. We simply count the zeroes between the ones. Using the example patterns above we have,

1100000 = 0,0,5
0110000 = 1,0,4
0101000 = 1,1,3
0001100 = 3,0,2
1000001 = 0,5,0

So when we have all these binary patterns we also will have all combinations of 3 numbers summing up to 5.

Since we are dealing with combinatorics the number of patterns very quickly will become intractable for large sums and vector sizes. In my example there will be just 21 patterns but with your example there will be billions.

Anyway my above (informal) reasoning shows not only how many solutions (for nonnegative integers) there are to the equation

x1 + x2 + x3 + ... + xn = k

(which has been exemplified with n=3 and k=5) but also how all solutions can be generated. If this is what you're looking for I can show some code.
Last edited by tiliavirga; February 27th, 2016 at 01:43 PM.  Reply With Quote

6. Member Join Date
Dec 2015
Posts
48

## Re: How to distribute a value into vector Originally Posted by tiliavirga It looks like a problem I've had recently namely how to find all partial derivatives of a certain order and dimension. I solved it as a combinatorics partition problem using bitsets for the implementation.

Anyway my above (informal) reasoning shows not only how many solutions (for nonnegative integers) there are to the equation

x1 + x2 + x3 + ... + xn = k

(which has been exemplified with n=3 and k=5) but also how all solutions can be generated. If this is what you're looking for I can show some code.
Hi thanks for your reply this is exactly what i want but your code is to show all possible combination of 3 numbers summing up to 5. But simply What i want is quarter of it sequence . I don't want any zero combination

For example
Your code can display all value of 3 numbers summing up to 5 = 21 sequence

5,0,0
0,5,0
0,0,5
4,1,0
4,0,1
1,4,0
1,0,4
0,1,4
0,4,1
3,2,0
3,0,2
2,3,0
2,0,3
0,2,3
0,3,2
2,2,1
2,1,2
1,2,2
3,1,1
1,3,1
1,1,3

I only need this output without zero and negative value

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

I never deal with bitsets type calculation i really like to learn it
Last edited by Ramees219; February 27th, 2016 at 02:26 PM.  Reply With Quote

7. Banned  Join Date
Jun 2015
Posts
208

## Re: How to distribute a value into vector Originally Posted by Ramees219 I don't want any zero combination
I kind of anticipated this since you had no zeroes in your initial example.

One solution is to generate all combinations according to my procedure but then cherry pick combinations with no zeros in them, just like you manually did in your previous post.

I'll post a solution based on the code I used for my own problem. I do this out of respect for early hackers like Gosper who did amazing things on rudimentary CPUs in the 1970's. It's still worthwhile.
Last edited by tiliavirga; February 27th, 2016 at 06:56 PM.  Reply With Quote

8. Banned  Join Date
Jun 2015
Posts
208

## Re: How to distribute a value into vector

What you call sum I call derivative order (D) and I generate all derivative orders from 0 up to and including D. Since you are interested in D only I had to introduce a new start criterion to reflect that.

What you call distribution vector I call variables (V) but this effectively is the same and so requires no changes.

I use a type BitSet (a long long int) to store bitsets. In addition to the bit patterns I've mentioned in previous posts there's also an additional leftmost stop bit in BitSets.

With V=3 and D=5 this is the internal representation of 0,0,5

10000011

This will also be the start value in your case and it's accomplished like this,

BitSet your_start = (1 << (V+D-1)) | ((1 << (V-1)) - 1);

There's also a type VecSet which is a vector used to hold a BitSet in zero count representation. bs_0vector() converts from BitSet to VecSet.

Also I've introduced a function any_zero() that checks whether any zero count is 0. It's overloaded both for BitSet and VecSet. I use it to mark sets you probably want to skip with an * in the output print.

Gosper's hack was first published in a report called HAKMEM from MIT's AI lab in 1972. Gosper's hack is item number 175. The report is available on internet. Gosper's hack is also (briefly) described in Knuth volume 4a and in Hacker's Delight by Warren (page 14-15 in the second edition). I lifted my code verbatim from the latter source. There are also descriptions on the net of course.

Here's the code.

Code:
```#include <string>
#include <vector>

// Gosper related
// The actual Gosper's hack is from Hacker's Delight by Warren on page 15 in the second edition.

template<typename T>
T gosper_start(int k) { // first subset
return (T(1) << k) - T(1);
}

template<typename T>
T gosper_next(T x) { // next subset (Gosper's hack (HAKMEM 175))
T s = x & -x;
T r = x + s;
return r | (((x^r) >> T(2)) / s);
}

template<typename T>
T gosper_limit(int n) { // first non-subset
return T(1) << n;
}

// types

using BitSet = long long int; // a bitset (must be integral type)
using VecSet = std::vector<int>; // vector version of bitset

// bitset manipulation

inline VecSet bs_0vector(BitSet x) { // turn BitSet into VecSet (counting zeroes between ones)
VecSet v;
while (x != 0) {
int c = 0;
while ((x & 1) == 0) {
c++;
x >>= 1;
}
v.push_back(c);
x >>= 1;
}
return v;
}

inline std::string bs_0string(const VecSet& v) { // turn VecSet into string
std::string s = "(";
for (int i = 0, l = int(v.size()) - 1; i <= l; ++i) {
s += std::to_string(v[i]);
if (i < l) s += ",";
}
return s + ")";
}

inline bool any_zero(const VecSet& v) { // check whether any VecSet member is zero
for (auto m : v) {
if (m==0) return true;
}
return false;
}

inline bool any_zero(BitSet x) {  // check whether any BitSet member is zero
if ((x & 1) == 1) return true; // a rightmost 1 means a 0 member
while (x != 0) {
if ((x & 3) == 3 ) return true; // two consecutive 1's means a 0 in-between
x >>= 1;
}
return false;
}

void test() {
int V = 3; // vector size
int D = 5; // sum

//	BitSet my_start = gosper_start<BitSet>(V);
const BitSet ONE = BitSet(1);
BitSet your_start = (ONE << (V+D-1)) | ((ONE << (V-1)) - ONE);

long long int c = 0; // counter
for (BitSet x = your_start; x < gosper_limit<BitSet>(V + D); x = gosper_next<BitSet>(x)) {
VecSet v = bs_0vector(x);
std::cout << bs_0string(v) << (any_zero(x) ? " *" : "") << std::endl;
++c;
}
std::cout << "Number of sets = " << c << std::endl;
}```
Last edited by tiliavirga; February 29th, 2016 at 06:45 AM.  Reply With Quote

9. Member Join Date
Dec 2015
Posts
48

## Re: How to distribute a value into vector

Thanks for the code i didn't understand all of the code but i think the code is calculates zero combination also is there any way we can calculate Only the output i want . Because if we input bigger value instead of 3 and 5 like 8 , 15 , its going to take lots of time .
and if i input v = 15 , D= 85 , number of sets = 0
Last edited by Ramees219; February 28th, 2016 at 08:05 AM.  Reply With Quote

10. Banned  Join Date
Jun 2015
Posts
208

## Re: How to distribute a value into vector Originally Posted by Ramees219 Because if we input bigger value instead of 3 and 5 like 8 , 15 , its going to take lots of time .
and if i input v = 15 , D= 85 , number of sets = 0
The use of bitsets puts a limitation on my solution indeed. It limits V+D to be no bigger than 62 because larger numbers will overflow the long long int used to represent the bitsets. To overcome this the bitset way of generating subsets will have to be replaced by some other subset generating algorithm.

Yes, this algorithm will generate all subsets and thus produce some with zeroes. My suggestion is to accept that and to simply just skip such subsets. Gosper's hack is a very fast algorithm and so skipping unwanted subsets may not even be slower than other approaches that may avoid such subsets altogether.

But okay, for some selections of V and D there will be lots of combinations with zeroes and if you want to keep searching for better fitting solutions I suggest you use the key phrase "restricted integer composition". I may give it a shot the next time I feel an urge for some recreational programming. Finally here's a function I'm using to calculate the number of combinations with my approach,
Code:
```inline long long int bs_binominal(int n, int k) { // the binominal n over k
if (k>n) return 0;
if (k == n) return 1;
long long int f = n;
for (int i = 2; i <= k; ++i) f = (f * (n + 1 - i)) / i;
return f;
}
//
std::cout << "Expected number of combinations: " << bs_binominal(V+D-1, V-1) << std::endl;```
Well, that was my contribution for now. Good luck!
Last edited by tiliavirga; February 29th, 2016 at 06:50 AM.  Reply With Quote

11. Banned  Join Date
Jun 2015
Posts
208

## Re: How to distribute a value into vector

I think maybe my solution can be slightly modified to fit your requirements.

In principle my solution finds all solutions to this equation for non-negative integers,

x1 + x2 + x3 + ... + xn = k

Any variable on the left side may be 0 and that's the problem since you want them all to be at least 1. What if we instead solve the above equation for k-n on the right side and then afterwards add 1 to each x variable on the left side?

Say we have V=3 and D=5 again. Instead we now run my algorithm with a modified D that is D-V which is 5-3=2. We get,

(0,0,2)
(0,1,1)
(1,0,1)
(0,2,0)
(1,1,0)
(2,0,0)

If we then add 1 to all numbers we have,

(1,1,3)
(1,2,2)
(2,1,2)
(1,3,1)
(2,2,1)
(3,1,1)

And this is exactly what you were looking for in your post #6.
Last edited by tiliavirga; February 29th, 2016 at 07:08 PM.  Reply With Quote

12. ## Re: How to distribute a value into vector

A pretty simple approach to this problem is to simply apply the "bar and stars" algorithm. Basically, instead of trying to find N-numbers whose *sum* is equal to a certain amount, try to find every combination of N-1 numbers in the range [0-Sum].

So for example, if you are trying to 3 numbers that sum to 3, you'd have:
Code:
```0 0
0 1
0 2
1 1
1 2
2 2```
Generating this sequence is not very complicated. It's basically the same as trying to count naturally, but you apply a backtracking step, instead of a "back to 0" step.

The trick now, is to consider that these values represent bars that split up a line of sum stars. Then you count the distance between each bar (AKA, count the stars), and you get what you want. Add 1 to every value if you want to weed out 0.
Code:
```||** => 0 0 2
|*|* => 0 1 1
|**| => 0 2 0
*||* => 1 0 1
*|*| => 1 1 0
**|| => 2 0 0```
Here is the code, operating on a small sample: 3 slots, sum of 8, minimum value of 1:
Code:
```#include <iostream>
#include <vector>
#include <algorithm>

template <typename T, typename ForwardIterator>
bool increment(ForwardIterator first, ForwardIterator last, T maximum) {
for (auto it = first; it != last; ++it) {
if (*it != maximum) {
std::fill(first, it, ++*it);
return true;
}
}
return false;
}

int main()
{
int minimum = 1; // included
int slots = 3;
int sum = 8;
int internal_max = sum - slots * minimum;
std::vector<int> vect(slots - 1, 0);
do {
auto previous_pos = internal_max;
for (auto it = vect.begin(); it != vect.end(); ++it) {
auto val = previous_pos - *it + minimum;
previous_pos = *it;
std::cout << val << " ";
}
std::cout << previous_pos + minimum << std::endl;
} while (increment(vect.begin(), vect.end(), internal_max));
}```  Reply With Quote

13. Banned  Join Date
Jun 2015
Posts
208

## Re: How to distribute a value into vector Originally Posted by monarch_dodra A pretty simple approach to this problem is to simply apply the "bar and stars" algorithm.
I'll just mention that the Gosper's hack algorithm I've been promoting is a very direct application of "bars and stars". Here the bars and the stars are represented with a bit-pattern (held in a bitset) where bars are ones and stars are zeroes. For example your example,

||** => 0 0 2
|*|* => 0 1 1
|**| => 0 2 0
*||* => 1 0 1
*|*| => 1 1 0
**|| => 2 0 0

will look like this,

1100 => 0 0 2
1010 => 0 1 1
1001 => 0 2 0
0110 => 1 0 1
0101 => 1 1 0
0011 => 2 0 0

Gosper's hack very efficiently generates all combinations of "bars and stars" but with the drawback that there's an upper limit to how many "bars and stars" can be handled. The issue with 0 in the solutions has been resolved in post#11.

The main reason I got interested in Gosper's hack is because it quite easily can be used with template metaprogramming.
Last edited by tiliavirga; February 29th, 2016 at 07:28 PM.  Reply With Quote

14. Member Join Date
Dec 2015
Posts
48

## Re: How to distribute a value into vector Originally Posted by monarch_dodra A pretty simple approach to this problem is to simply apply the "bar and stars" algorithm. Basically, instead of trying to find N-numbers whose *sum* is equal to a certain amount, try to find every combination of N-1 numbers in the range [0-Sum].
I didn't use the zero combination because i need this code run faster
But since #post 10 i realized its still take lost of time on big value
So redesign my algorithm now i don't want zero combination and dual character in one array like .10, 11, 12 .. so on
For example
Slots = 3
Sum = 17

Output
15 , 1 , 1
14 , 2 , 1
13 , 3 , 1
12 , 4 , 1
11 , 5 , 1
10 , 6 , 1
9 , 7 , 1
8 , 8 , 1
7 , 9 , 1
6 ,10 ,1
5 , 11 ,1
4 , 12 , 1
3 , 13 , 1
2 , 14 , 1
1 ,15 ,1
14 ,1 ,2
13 , 2 ,2
12, 3 ,2
11, 4 ,2
10 ,5 ,2
9 ,6 ,2
8 ,7 ,2
7, 8 ,2
6 ,9 ,2
5 ,10,2
4 ,11 ,2
3 ,12 ,2
2 ,13 ,2
1,14 ,2
3,1,3
12,2,3
11,3,3
10,4,3
9,5,3
8,6,3
7,7,3
6,8,3
5,9,3
4,10,3
3,11,3
2,12,3
1,13,3
12,1,4
11,2,4
10,3,4
9,4,4
8,5,4
7,6,4
6,7,4
5,8,4
4,9,4
3,10,4
2,11,4
1,12,4
11,1,5
10,2,5
9,3,5
8,4,5
7,5,5
6,6,5
5,7,5
4,8,5
3,9,5
2,10,5
1,11,5
10,1,6
9,2,6
8,3,6
7,4,6
6,5,6
5,6,6
4,7,6
3,8,6
2,9,6
1,10,6
9,1,7
8,2,7
And ..continue..

From this output i only need

9 , 7 , 1
8 , 8 , 1
7 , 9 , 1
9 ,6 ,2
8 ,7 ,2
7, 8 ,2
6 ,9 ,2
3,1,3
9,5,3
8,6,3
7,7,3
6,8,3
5,9,3
9,4,4
8,5,4
7,6,4
6,7,4
5,8,4
4,9,4
9,3,5
8,4,5
7,5,5
6,6,5
5,7,5
4,8,5
3,9,5
9,2,6
8,3,6
7,4,6
6,5,6
5,6,6
4,7,6
3,8,6
2,9,6
9,1,7  Reply With Quote

15. Banned  Join Date
Jun 2015
Posts
208

## Re: How to distribute a value into vector Originally Posted by Ramees219 I didn't use the zero combination because i need this code run faster
But since #post 10 i realized its still take lost of time on big value
So redesign my algorithm now i don't want zero combination and dual character in one array like .10, 11, 12 .. so on
For example
Slots = 3
Sum = 17
Have you noticed my post #11?

Say we have V=3 (slots) and D= 17 (sum).

Just use V=3 and D=D-V = 17-3 = 14. Then run Gosper's hack with those values and add 1 to each number in every output combination, like,

Code:
```void test() {
int V = 3; // vector size
int D = 17-V; // modified sum

const BitSet ONE = BitSet(1);
BitSet your_start = (ONE << (V + D - 1)) | ((ONE << (V - 1)) - ONE);

//	std::cout << "Expected number of combinations: " << bs_binominal(V+D-1, V-1) << std::endl;

long long int c = 0; // counter
for (BitSet x = your_start; x < gosper_limit<BitSet>(V + D); x = gosper_next<BitSet>(x)) {
VecSet v = bs_0vector(x);
for (auto& n : v) ++n; // add on 1 to each number in VecSet
std::cout << bs_0string(v) << std::endl;
++c;
}
std::cout << "Actual number of combinations = " << c << std::endl;
}```
I generates exactly the 120 combinations you are looking for, nothing more nothing less.

So Gosper's hack now can be used to very efficiently produce the result you wanted. The D+V <= 62 limit is still there of course but since I too am interested in an unlimited algorithm for this I'll post my own replacement for Gosper's hack anytime soon. Last edited by tiliavirga; March 1st, 2016 at 02:10 AM.  Reply With Quote

c++, c++ array, c++ beginner #### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
• 