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

## Re: How to distribute a value into vector Originally Posted by tiliavirga 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,
Yes i noticed but in my latest #post 14 i need some change in the code
Now I only need 1 between 9 value in one row and total row equal = sum if we do this we can save time  Reply With Quote

2. ## 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
Again, you can just add 1 to every value. Also, the code provided has "int minimum = 1; // included" explicitly provided. Did you decide to stop reading after the first sentence? Originally Posted by Ramees219 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
I'm not sure my previous algorithm can be easily adapted. But at this point, you might as well just programmatically generate the combinations you want. With recursion, it's actually a pretty simple (and efficient) algorithm.

Code:
```#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>

int minimum = 1; // included
int maximum = 9; // included
int slots = 3;
int sum = 17;

template <typename ForwardIterator>
void increment(ForwardIterator first, ForwardIterator it, ForwardIterator last, int remainder) {
int free_slots = std::distance(it, last) - 1;
if (free_slots == 0) {
*it = remainder;
std::copy(first, last, std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
return;
}

auto low = std::max(minimum, remainder - free_slots * maximum);
auto high = std::min(maximum, remainder - free_slots * minimum);

auto next = std::next(it);
for (int i = low; i <= high; ++i) {
*it = i;
increment(first, next, last, remainder - i);
}
}

int main()
{
std::vector<int> vect(3, 0);
increment(vect.begin(), vect.begin(), vect.end(), sum);
}```
This will generate all the combinations you need, in an efficient manner (it won't backtrack on "bad" combinations). It also outputs in a "natural" order. Unlike the previous algorithm though, it needs to retain state. So if you want to operate on the results, you need to either store them all for later use, or pass in a callback object on generated results.
Last edited by monarch_dodra; March 1st, 2016 at 03:30 AM.  Reply With Quote

3. Banned  Join Date
Jun 2015
Posts
208

## Re: How to distribute a value into vector Originally Posted by tiliavirga 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.
Here it is now,

Code:
```void test2() {
int V=3;
int D=5;
assert(V>0 && D>=0);

std::vector<int> r(V,0);
r = D;
std::cout << tostring(r) << std::endl;

int h=0;
while (r[V-1] != D) {
const int t = r[h] - 1;
r[h] = 0;
r = t;
++r[++h];
if (t>0) h = 0;
//  h &= (t>0)-1; // branch free version of above if statement
std::cout << tostring(r) << std::endl;
}
}

inline std::string tostring(const std::vector<int>& v) {
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 + ")";
}```
Last edited by tiliavirga; March 4th, 2016 at 04:15 PM.  Reply With Quote

4. Member Join Date
Dec 2015
Posts
48

## Re: How to distribute a value into vector

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));
}```

hi i need a little help
how can i control each slot with a capacity value
example if the slots = 3,and sum= 8 then i like to add a capacity (array or vector) =  all the sequence must be inside this range
Last edited by Ramees219; December 15th, 2017 at 02:20 PM.  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
• 