大人数で旅行を楽しんだあとに待っているのは耐え難き精算・送金処理だ。 次回から楽をするためにも、送金回数を最小化する制約で精算表を作る方法を考えよう。

tl;dr

アイディアは「最も支払わなかった人が最も支払った人に払えるだけ払う ⇢ 債権を再計算して繰り返す」

1. 全員の出費を算出（払い過ぎは正、払わなさすぎは負の数）
2. 降順でソート（出費過多が先頭）
3. リストの最後（最大債務者, 出費=L）がリストの最初（最大債権者, F）に を支払ってバランス(負債)を再計算
4. 全員のバランスが 0 になるまで 2-3 を繰り返す

実験

実際にコードを書いて本当に望んでいる結果が得られるのかを検証する。

split-bill.js
const history = [
  {
    amount: 121,
    payer: "A",
    involves: ["A", "B", "C"],
  },
  {
    amount: 98,
    payer: "B",
    involves: ["A", "B", "C"],
  },
  {
    amount: 10,
    payer: "C",
    involves: ["A", "B", "C"],
  },
  {
    amount: 10,
    payer: "C",
    involves: ["A", "B"],
  },
  {
    amount: 50,
    payer: "C",
    involves: ["A"], // meaning C lent A 50
  },
];

// calculate balance sheet
const init = { balance: 0, consumption: 0 };
Map.prototype.fetch = function (id) {
  return (
    this.get(id) || this.set(id, Object.assign({ name: id }, init)).get(id)
  );
};

const data = new Map();

for (const { payer, amount, involves } of history) {
  const record = data.fetch(payer);
  record.balance += amount;
  const debt = Math.ceil(amount / involves.length);
  // actual payer should not owe extra debt coming from rounded up numbers
  const payerDebt = amount - debt * (involves.length - 1);
  for (const debtor of involves.map((i) => data.fetch(i))) {
    const cost = Math.round(amount / involves.length);
    debtor.balance -= cost;
    debtor.consumption += cost;
  }
}

console.log(data);

// calculate transaction table
const transaction = [];
let paidTooMuch, paidLess;
while (true) {
  for (const [_, tbl] of data) {
    if (tbl.balance >= (paidTooMuch?.balance || 0)) {
      paidTooMuch = tbl;
    }
    if (tbl.balance <= (paidLess?.balance || 0)) {
      paidLess = tbl;
    }
  }

  if (paidLess.balance == 0 || paidTooMuch.balance == 0) break;

  const amount = Math.min(paidTooMuch.balance, Math.abs(paidLess.balance));

  transaction.push({
    sender: paidLess.name,
    receiver: paidTooMuch.name,
    amount,
  });

  paidTooMuch.balance -= amount;
  paidLess.balance += amount;
}

console.log("Settled");

console.log("\n# Transaction table");
for (const ev of transaction) {
  console.log(`${ev.sender} owes ${ev.receiver} ¥${ev.amount}`);
}

console.log("\n# History");
for (const { payer, amount, involves } of history) {
  if (involves.length === 1) {
    console.log(`${payer} lent ¥${amount} to ${involves[0]}`);
  } else {
    console.log(`${payer} paid ¥${amount} for ${involves.join(", ")}`);
  }
}

console.log("\n# Expenses");
for (const [_, { name, consumption }] of data) {
  console.log(`${name} virtually paid ¥${consumption} in total`);
}

historyに支払い履歴を書き込んで実行すると、「送金表」「履歴」「実質支払総額」が得られる。

# Transaction table

A owes B ¥10
C owes B ¥6

# History

A paid ¥121 for A, B, C
B paid ¥98 for A, B, C
C paid ¥10 for A, B, C
C paid ¥10 for A, B
C lent ¥50 to A

# Expenses

A virtually paid ¥131 in total
B virtually paid ¥81 in total
C virtually paid ¥76 in total

旅行中、A と B は 1 回、C は 3 回支払いを建て替えた。そのうち 3 回は普通の割り勘だが、他 2 回はそれぞれ「C が A と B の分を建て替えた」「C が A の分を建て替えた(=C が A に金を貸した)」である。

このようなケースで一件ずつナイーブに精算しようとすると、合計 12 回のお金のやり取りが発生することになる。しかし負債を同額の債権で打ち消す操作を繰り返して最適化した結果、たった 2 回お金のやり取りをするだけで全員分の精算を完了できることがわかった。

プログラムに落とし込むことができたら、あとはスプレッドシートのマクロにするなりスマホのアプリにするなり自由だ。面倒なことは全部コンピューターにやらせよう！