CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 19

Thread: How to distribute a value into vector

  1. #1
    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 ...

  2. #2
    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.

  3. #3
    Join Date
    Dec 2015
    Posts
    48

    Re: How to distribute a value into vector

    Quote Originally Posted by TubularX View Post
    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;

  4. #4
    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.

  5. #5
    Join Date
    Jun 2015
    Posts
    208

    Re: How to distribute a value into vector

    Quote Originally Posted by Ramees219 View Post
    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.

  6. #6
    Join Date
    Dec 2015
    Posts
    48

    Re: How to distribute a value into vector

    Quote Originally Posted by tiliavirga View Post
    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.

  7. #7
    Join Date
    Jun 2015
    Posts
    208

    Re: How to distribute a value into vector

    Quote Originally Posted by Ramees219 View Post
    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.

  8. #8
    Join Date
    Jun 2015
    Posts
    208

    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;
    }
    Last edited by tiliavirga; February 29th, 2016 at 06:45 AM.

  9. #9
    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.

  10. #10
    Join Date
    Jun 2015
    Posts
    208

    Re: How to distribute a value into vector

    Quote Originally Posted by Ramees219 View Post
    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.

  11. #11
    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.

  12. #12
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

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

  13. #13
    Join Date
    Jun 2015
    Posts
    208

    Re: How to distribute a value into vector

    Quote Originally Posted by monarch_dodra View Post
    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.

  14. #14
    Join Date
    Dec 2015
    Posts
    48

    Re: How to distribute a value into vector

    Quote Originally Posted by monarch_dodra View Post
    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

  15. #15
    Join Date
    Jun 2015
    Posts
    208

    Re: How to distribute a value into vector

    Quote Originally Posted by Ramees219 View Post
    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.

Page 1 of 2 12 LastLast

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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)