-
March 1st, 2016, 02:50 AM
#16
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
-
March 1st, 2016, 03:27 AM
#17
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.
Is your question related to IO?
Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.
-
March 2nd, 2016, 08:12 AM
#18
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[0] = 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[0] = 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.
-
December 15th, 2017, 02:15 PM
#19
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) = [4][2][3] all the sequence must be inside this range
Last edited by Ramees219; December 15th, 2017 at 02:20 PM.
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|