split.gno

 1package ledger
 2
 3// Equal splits total into n parts that differ by at most one cent; the first
 4// total%n parts take the extra cent. A negative total (money received) splits
 5// the same way, every part negative.
 6func Equal(total int64, n int) []int64 {
 7	w := make([]int64, n)
 8	for i := range w {
 9		w[i] = 1
10	}
11	return Weighted(total, w)
12}
13
14// Weighted splits total in proportion to weights, all positive, by largest
15// remainder: each part is rounded down, then the cents left go to the largest
16// remainders, ties to the first. The parts always sum to total.
17func Weighted(total int64, weights []int64) []int64 {
18	neg := total < 0
19	if neg {
20		total = -total
21	}
22	var sum int64
23	for _, w := range weights {
24		sum += w
25	}
26	parts := make([]int64, len(weights))
27	rem := make([]int64, len(weights))
28	left := total
29	for i, w := range weights {
30		parts[i] = total * w / sum
31		rem[i] = total * w % sum
32		left -= parts[i]
33	}
34	for ; left > 0; left-- {
35		best := 0
36		for i := 1; i < len(rem); i++ {
37			if rem[i] > rem[best] {
38				best = i
39			}
40		}
41		parts[best]++
42		rem[best] = -1 // one extra cent at most per part
43	}
44	if neg {
45		for i := range parts {
46			parts[i] = -parts[i]
47		}
48	}
49	return parts
50}
51
52// Transfer is one payment that settles part of a group: From pays To.
53type Transfer struct {
54	From, To int
55	Amount   int64
56}
57
58// Settle returns the transfers that bring every balance to zero (balances
59// sum to zero; > 0 means the group owes that member). The largest debt pays
60// the largest credit, ties to the lower index, so each step clears at least
61// one member: at most n-1 transfers, in O(n²) for the few members of a group.
62func Settle(balances []int64) []Transfer {
63	bal := make([]int64, len(balances))
64	copy(bal, balances)
65	var out []Transfer
66	for {
67		cr, dr := -1, -1
68		for i, b := range bal {
69			if b > 0 && (cr < 0 || b > bal[cr]) {
70				cr = i
71			}
72			if b < 0 && (dr < 0 || b < bal[dr]) {
73				dr = i
74			}
75		}
76		if cr < 0 || dr < 0 {
77			return out
78		}
79		amt := bal[cr]
80		if -bal[dr] < amt {
81			amt = -bal[dr]
82		}
83		out = append(out, Transfer{From: dr, To: cr, Amount: amt})
84		bal[cr] -= amt
85		bal[dr] += amt
86	}
87}