How to distribute a value into vector

[Ramees219]

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

[monarch_dodra]

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?

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.

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

[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,

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 + ")";
}

[Ramees219]

#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