How to distribute a value into vector

[Ramees219]

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

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

[Ramees219]

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;

[TubularX]

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.

[tiliavirga]

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.

[Ramees219]

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

[tiliavirga]

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.

[tiliavirga]

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.

#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;
}

[Ramees219]

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

[tiliavirga]

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,

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!

[tiliavirga]

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.

[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].

So for example, if you are trying to 3 numbers that sum to 3, you'd have:

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.

||** => 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:

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

[tiliavirga]

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.

[Ramees219]

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

[tiliavirga]

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,

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.