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 ...
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.
Re: How to distribute a value into vector
Quote:
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;
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.
Re: How to distribute a value into vector
Quote:
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.
Re: How to distribute a value into vector
Quote:
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
Re: How to distribute a value into vector
Quote:
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.
Re: How to distribute a value into vector
I've adapted my code to your problem now.
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;
}
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
Re: How to distribute a value into vector
Quote:
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!
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.
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));
}
Re: How to distribute a value into vector
Quote:
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.
Re: How to distribute a value into vector
Quote:
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
Re: How to distribute a value into vector
Quote:
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. :)
Re: How to distribute a value into vector
Quote:
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
Re: How to distribute a value into vector
Quote:
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?
Quote:
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.
Re: How to distribute a value into vector
Quote:
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 + ")";
}
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
