4

I'm looking to construct an algorithm which gives the arrangements with repetition of n sequences of a given step S (which can be a positive real number), under the constraint that the sum of all combinations is k, with k a positive integer.

My problem is thus to find the solutions to the equation:

x 1 + x 2 + ⋯ + x n = k where

0 ≤ x i ≤ b i and S (the step) a real number with finite decimal.

For instance, if 0≤xi≤50, and S=2.5 then xi = {0, 2.5 , 5,..., 47.5, 50}.

The point here is to look only through the combinations having a sum=k because if n is big it is not possible to generate all the arrangements, so I would like to bypass this to generate only the combinations that match the constraint.

I was thinking to start with n=2 for instance, and find all linear combinations that match the constraint.

ex: if xi = {0, 2.5 , 5,..., 47.5, 50} and k=100, then we only have one combination={50,50} For n=3, we have the combination for n=2 times 3, i.e. {50,50,0},{50,0,50} and {0,50,50} plus the combinations {50,47.5,2.5} * 3! etc...

If xi = {0, 2.5 , 5,..., 37.5, 40} and k=100, then we have 0 combinations for n=2 because 2*40<100, and we have {40,40,20} times 3 for n=3... (if I'm not mistaken)

I'm a bit lost as I can't seem to find a proper way to start the algorithm, knowing that I should have the step S and b as inputs.

Do you have any suggestions?

Thanks

neminem
  • 2,658
  • 5
  • 27
  • 36
Ouriel
  • 41
  • 1
  • So is `x_i` always 0 und `x_{i+1} = x_i + S`? I don't really understand the question to be honest, maybe you should clarify it a bit – Niklas B. Mar 03 '14 at 18:16
  • Or maybe a better question would be: What is the meaning of *S*? – Niklas B. Mar 03 '14 at 18:19
  • to make it less tedious, we assume x_i starts from 0 and indeed x_{i+1} = x_i + S. S is the step in the x_i sequence but as you wrote it we can indeed get rid of the step by dividing the x_i sequence over the step in order to have only x_i' that are integers. if x_i= {0, 2.5 , 5,..., 47.5, 50} then x_i'={0, 1 , 2,..., 19, 20} – Ouriel Mar 04 '14 at 11:04

2 Answers2

2

You can transform your problem into an integer problem by dividing everything by S: We want to find all integer sequences y1, ..., yn with:

(1) 0 ≤ yi ≤ ⌊b / S⌋

(2) y1 + ... + yn = k / S

We can see that there is no solution if k is not a multiple of S. Once we have reduced the problem, I would suggest using a pseudopolynomial dynamic programming algorithm to solve the subset sum problem and then reconstruct the solution from it. Let f(i, j) be the number of ways to make sum j with i elements. We have the following recurrence:

f(0,0) = 1
f(0,j) = 0  forall j > 0
f(i,j) = sum_{m = 0}^{min(floor(b / S), j)} f(i - 1, j - m)

We can solve f in O(n * k / S) time by filling it row by row. Now we want to reconstruct the solution. I'm using Python-style pseudocode to illustrate the concept:

def reconstruct(i, j):
    if f(i,j) == 0: 
        return
    if i == 0:
        yield []
        return
    for m := 0 to min(floor(b / S), j):
        for rest in reconstruct(i - 1, j - m):
             yield [m] + rest

result = reconstruct(n, k / S)

result will be a list of all possible combinations.

Niklas B.
  • 92,950
  • 18
  • 194
  • 224
  • Thanks Niklas. I'm not sure I get the formula for f(i,j), especially what is m? let's take a concrete example: if I take y_i={0, 1 , 2,..., 19, b / S=20} and sum(y_i)=k / S = 100/2.5 = 40, so for i=j=1 for example, I would get f(1,1) = sum(m=0)^min(20,1)*f(0,1-m) ? Whats is m? Also, does f(1,1) mean the number of ways to make sum 1 with 1 element i, i being the FIRST element of the sequence y_i, i.e y_1=0? in that case, f(1,1) should be 0, otherwise if i is any 1 element in the sequence, then f(1,1) should be equal to 1, it corresponds to y_2=1 – Ouriel Mar 04 '14 at 11:21
  • @Ouriel `m` is just the iteration variable of the loop. I used LaTeX-like syntax here, it means "the sum from m = 0 to m = min(floor(b/S), j)". `f(i,j)` is the number of ways to get to sum `j` using only the values `0`, `1`, ..., `i` – Niklas B. Mar 04 '14 at 18:12
  • hey Niklas, I used the following recurrence for b <= k : f(n,k,b) = f(n,k-1,b) + f(n-1,k,b). and if n > 0 and k > b { f = f - f(n-1,k-b-1,b) }, because if k>b I need to remove from all the arrangements, those that I included twice (inclusion-exclusion principle). It takes however some time to compute when n is large(n>=8)). For the part where you reconstruct the solution, I don't get how we can create ONLY the solutions constrained on sum=k knowing that we have just computed the number of ways to get sum j? not very familiar with Python. thx for the help:) – Ouriel Mar 07 '14 at 13:36
  • @Ouriel: It shouldn't take long to compute, `n = 8` is not large at all. But you have to be careful to use [dynamic programming](http://en.wikipedia.org/wiki/Dynamic_programming) using tables or memoization, so that you don't recompute results. For reconstruction, you just "execute" the recurrence like in backtracking, you just prune if your DP array says that the current branch has no solutions. So for example, you look at `(n,k)`, you check whether `f(n,k) = 0`. If it's not, you call `f(n,k-1)` and append `k` to the resulting lists. Then you call `f(n-1,k)` and append `k` to the results – Niklas B. Mar 07 '14 at 15:49
  • when you say "you call f(n,k-1) and append k to the resulting lists". I actually don't have any list from the recurrence I drew. The only thing I have when I call f(n,k), is the number of elements that satisfy: sum of each elements=k, but I don't have the elements itself (meaning I have a number of all combinations but not smthg like "(1,2,1)" for n=3, k=4 for example. So how do I create this resulting lists? – Ouriel Mar 07 '14 at 16:25
  • @Ouriel: Sorry, I meant you call `reconstruct(n,k-1)` recursively etc – Niklas B. Mar 07 '14 at 16:35
  • Which returns a list of all the possible solutions for the state `(n, k-1)` – Niklas B. Mar 07 '14 at 16:47
  • @ Niklas:I have tried to reconstruct the solutions from the recurrence but it is actually difficult to do so as, even though the recurrence is valid to find the number of solutions, it is not when we want to reconstruct the solutions. Indeed if I want to enumerate the solutions for the state(n,k), I cannot use the previous state (n,k-1) as the sum of the previous state (=k-1) wouldn't be the same than the current state (n,k). In order to reconstruct the solutions, I would assume that I need to keep my sum k constant and that n is the only variable that should be incremented. What do you think? – Ouriel Mar 17 '14 at 15:01
0

What you are describing sounds like a special case of the subset sum problem. Once you put it in those terms, you'll find that Pisinger apparently has a linear time algorithm for solving a more general version of your problem, since your weights are bounded. If you're interested in designing your own algorithm, you might start by reading Pisinger's thesis to get some ideas.

Since you are looking for all possible solutions and not just a single solution, the dynamic programming approach is probably your best bet.

Community
  • 1
  • 1
Peter G
  • 1,613
  • 10
  • 10
  • The weights are not bounded by a constant in OPs problem. They are bounded by *b*, which is part of the problem instance – Niklas B. Mar 03 '14 at 19:37