Implementation: Algorithm for a special distribution Problem

  • A+
Category:Languages

We are given a number x, and a set of n coins with denominations v1, v2, …, vn.

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 v1 = v2 = 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.

 


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 

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: