Minimum number of transactions so everyone has paid the same

Question

On a road trip, N people pay for fuel. Each pays a different amount. At the end of the trip, calculate the minimum number of transactions so that each person has paid the same amount.

e.g. on the road trip, these people pay for fuel

• Dave - $50
• John - $25
• George - $5
• Barry - $0

After the road trip:

• Barry pays Dave $20
• George pays John $5
• George pays Dave $10

---

Added: The output of the program should list the transactions.

Bonus points if the solution is written in Visual Basic.

Answer 1

Python, 308 Characters

I chose not to go after the bonus because the last time I used VB was over a decade ago, and I am still suffering from the PTSD ;-)

I didn't try and golf this very much because I'm not sure if that's the goal. This code is guaranteed to return a solution with the minimum number of transactions.

def t(p):
 a=sum(p)/float(len(p))
 q=[([],p)]
 l=len(p)
 r=range(l)
 while q:
  n=q.pop(0)
  g=1
  for i in r:
   d=n[1][i]-a
   if d>0:
    g=0
    for j in r:
     if n[1][j]<a:
      v=min(d,a-n[1][j])
      y=list(n[1])
      y[i]-=v
      y[j]+=v
      if i!=j:q+=[(n[0]+[(j,i,v)],y)]
  if g:return n[0]

Usage

The t function takes a list of the amounts that each person paid. Using the example from the question:

> print t([50,25,5,0])
[(2, 0, 15.0), (3, 0, 15.0), (3, 1, 5.0)]

So the solution is for person 2 (George) to pay person 0 (Dave) $15 and for person 3 (Barry) to pay 0 (Dave) $15 and also to pay 1 (John) $5.