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

Thread: How to distribute a value into vector

  1. #16
    Join Date
    Dec 2015
    Posts
    48

    Re: How to distribute a value into vector

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

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

    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
    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 View Post
    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.

  3. #18
    Join Date
    Jun 2015
    Posts
    208

    Re: How to distribute a value into vector

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

  4. #19
    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) = [4][2][3] all the sequence must be inside this range
    Last edited by Ramees219; December 15th, 2017 at 02:20 PM.

Page 2 of 2 FirstFirst 12

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)