Implementation: Algorithm for a special distribution Problem

Question

We are given a number x, and a set of n coins with denominations v₁, v₂, …, v_n.

The coins are to be divided between Alice and Bob, with the restriction that each person's coins must add up to at least x.

For example, if x = 1, n = 2, and v₁ = v₂ = 2, then there are two possible distributions: one where Alice gets coin #1 and Bob gets coin #2, and one with the reverse. (These distributions are considered distinct even though both coins have the same denomination.)

I'm interested in counting the possible distributions. I'm pretty sure this can be done in O(nx) time and O(n+x) space using dynamic programming; but I don't see how.

Answer 1

Count the ways for one person to get just less than x, double it and subtract from the doubled total number of ways to divide the collection in two, (Stirling number of the second kind {n, 2}).

For example,

{2, 3, 3, 5}, x = 5

i  matrix
0  2: 1
1  3: 1 (adding to 2 is too much)
2  3: 2
3  N/A (≥ x)

3 ways for one person to get
less than 5.

Total ways to partition a set
of 4 items in 2 is {4, 2} = 7

2 * 7 - 2 * 3 = 8

The Python code below uses MBo's routine. If you like this answer, please consider up-voting that answer.

# Stirling Algorithm
# Cod3d by EXTR3ME
# https://extr3metech.wordpress.com
def stirling(n,k):
  n1=n
  k1=k
  if n<=0:
    return 1
  elif k<=0:
    return 0   
  elif (n==0 and k==0):
    return -1
  elif n!=0 and n==k:
    return 1
  elif n<k:
    return 0
  else:
    temp1=stirling(n1-1,k1)
    temp1=k1*temp1
    return (k1*(stirling(n1-1,k1)))+stirling(n1-1,k1-1)

def f(coins, x):
  a = [1] + (x-1) * [0]

  # Code by MBo
  # https://stackoverflow.com/a/53418438/2034787
  for c in coins:
      for i in xrange(x - 1, c - 1, -1):
          if a[i - c] > 0:
              a[i] = a[i] + a[i - c]

  return 2 * (stirling(len(coins), 2) - sum(a) + 1)

print f([2,3,3,5], 5) # 8
print f([1,2,3,4,4], 5) # 16

Answer 2

If sum of all coins is S, then the first person can get x..S-x of money.

Make array A of length S-x+1 and fill it with numbers of variants of changing A[i] with given coins (like kind of Coin Change problem).

To provide uniqueness (don't count C1+C2 and C2+C1 as two variants), fill array in reverse direction

A[0] = 1
for C in Coins:
    for i = S-x downto C:
        if A[i - C] > 0:
             A[i] = A[i] + A[i - C] 
             //we can compose value i as i-C and C

then sum A entries in range x..S-x

Example for coins 2, 3, 3, 5 and x=5.
S = 13, S-x = 8

Array state after using coins in order:

0 1 2 3 4 5 6 7 8  //idx
1   1
1   1 1   1
1   1 2   2 1   1 
1   1 2   3 1 1 3  

So there are 8 variants to distribute these coins. Quick check (3' denotes the second coin 3):

2 3      3' 5
2 3'     3 5
2 3 3'   5  
2 5      3 3'
3 3'     2 5
3 5      2 3'
3' 5     2 3
5        2 3 3'

Answer 3

You can also solve it in O(A * x^2) time and memory adding memoization to this dp:

solve(A, pos, sum1, sum2):
    if (pos == A.length) return sum1 == x && sum2 == x
    return solve(A, pos + 1, min(sum1 + A[pos], x), sum2) + 
           solve(A, pos + 1, sum1, min(sum2 + A[pos], x))

print(solve(A, 0, 0, 0))

So depending if x^2 < sum or not you could use this or the answer provided by @Mbo (in terms of time complexity). If you care more about space, this is better only when A * x^2 < sum - x