pagat

帮助您分账的库；用于学习目的，非生产就绪。

安装

[dependencies]
pagat = "0.0.2"

概念

此crate具有以下概念

• Person：参与分账的人；
• Money：用于货币计算的i32，使用两位小数表示分（100 = $1.00）
• Payment：某人支付的款项，可能涉及多达N个人
  • 也许你和所有人都坐了出租车，但D没有，所以你可以将这笔款项记录在B和C上
• Obligation：记录某个人需要支付另一个人一定金额的款项
  • 这是作为图求解器输出的记录

使用方法及示例

请参阅测试以了解不同的用例。

工作原理

它使用有向图来表示谁需要支付给谁多少钱。然而，这种表示方式没有得到很好的优化，并且需要很多人支付给别人并跟踪金钱，这违背了库的目的。

求解器通过优化这种连接，使得支付次数尽可能少，乐观地可以做到N-1次支付，其中N是涉及的人数。

在实现上，求解器执行了四个遍历。

第一次遍历

将双重连接的边减少到单一边连接。结果方向由边权重之差决定。如果结果是零，则删除两个边。

考虑以下示例，其中A需要支付B 10美元，而B需要支付A 20美元

┌─────┐     $10       ┌─────┐
│     ├──────────────►│     │
│ A   │               │ B   │
│     │◄──────────────┤     │
└─────┘     $20       └─────┘

在第一次遍历后，我们将只有B支付A 10美元

┌─────┐               ┌─────┐
│     │               │     │
│ A   │               │ B   │
│     │◄──────────────┤     │
└─────┘     $10       └─────┘

如果A和B支付相同，则删除两个连接。

第二次遍历

在第一次遍历之后，我们可以保证没有双重连接的边，然后可以进入第二次遍历。
通过选择一条边，我们检查该边的目标节点是否有一条边连接到另一个节点，而这个源边也连接到该节点。如果我们找到这样的边，我们就删除第一条边，并更新剩余边的权重（话虽如此）。让我们看看一个例子。

     ┌───┐       ┌───┐
     │   │ $25   │   │
     │ H ├──────►│ C │
     │   │       │   │
     └─┬─┘       └─┬─┘
       │           │
   $50 │   ┌───┐   │ $50
       │   │   │   │
       └──►│ A │◄──┘
           │   │
           └───┘

步骤如下

• 删除 H->C
• 将它的权重（$25）加到 H->A
• 从 H->C 减去它的权重（$25）

这样，得到的图是

   ┌───┐       ┌───┐
   │   │       │   │
   │ H │       │ C │
   │   │       │   │
   └─┬─┘       └─┬─┘
     │           │
 $75 │   ┌───┐   │ $25
     │   │   │   │
     └──►│ A │◄──┘
         │   │
         └───┘

这种优化的理由很简单：如果 H 和 C 都向同一个人 A 付款，那么 H 就不需要向 C 付款。
如果减法步骤得到的结果是负数，我们只需反转边的方向。

第三次遍历

如果 A 向 B 付款 10 美元，而 B 向 C 付款相同金额，我们可以将其减少到 A 直接向 C 付款 10 美元。更技术地说，如果有一条边 A --[X]--> B 和另一条边 B --[X]--> C，它可以减少到 A --[X]--> C。

第四次遍历

为了使事情更快一些，我们实际上并没有删除任何连接，而是将它们的权重设置为 0。正是在这一步，我们在所有其他三个步骤之后进行删除。

待办事项

• 改进 Rust 代码文档
• 添加适当的示例