fix cycle generation

The current cycle generation did not consider permutations of a
combination of vertices.
Make all Functions return Iterators to reduce the needed memory size.

1 files changed, 38 insertions, 16 deletions

diff --git a/minimize.py b/minimize.py
index 1252475..70fd738 100755
--- a/minimize.py
+++ b/minimize.py
@@ -5,11 +5,11 @@ import math
 import typing as T
 
 Cycle = tuple
-Cycles = list[Cycle]
+Cycles = T.Iterable[Cycle]
 
 
 def gen_cycles(vertices: set) -> Cycles:
-    """Generate all cycles possible in the vertices set
+    """Iterate all cycles possible in the vertices set
 
     The vertices set is expected to contain the vertices of a fully connected
     bidirectional graph. Like the balance used by geldschieberbot.
@@ -17,19 +17,18 @@ def gen_cycles(vertices: set) -> Cycles:
     The nature of the graph makes the cycle generation easy. All possible cycles
     are simply all possible subsets with at least 3 elements.
     """
-    cycles = []
     for length in range(3, len(vertices) + 1):
-        for subset in set(itertools.combinations(vertices, length)):
-            cycles.append(subset)
-    return cycles
+        for subset in itertools.combinations(vertices, length):
+            yield from itertools.permutations(subset, length)
 
 
 def test_gen_cycles():
     """Test the cycle generation by comparing the number of generated cycles"""
     vertices = {1, 2, 3, 4}
     lenghts = range(3, len(vertices) + 1)
-    num_cycles = sum(math.comb(len(vertices), x) for x in lenghts)
-    assert len(gen_cycles(vertices)) == num_cycles
+    num_cycles = sum(
+        math.perm(x) * math.comb(len(vertices), x) for x in lenghts)
+    assert len(list(gen_cycles(vertices))) == num_cycles
 
 
 Balance = dict[T.Any, dict[T.Any, int]]
@@ -80,12 +79,21 @@ def test_has_same_flow_direction():
 
 def find_money_cicles(balance: Balance, cycles: Cycles) -> Cycles:
     """Find all cycles with the same money flow in a balance"""
-    found = []
     for cycle in cycles:
         if has_same_flow_direction(balance, cycle):
-            found.append(cycle)
+            yield cycle
 
-    return found
+
+def exclude_dead_ends(balance: Balance) -> T.Iterable[str]:
+    """Return all vertices that are no dead ends"""
+    for vert, edges in balance.items():
+        last_edge = None
+        for edge in edges.values():
+            if last_edge and (last_edge < 0 < edge or last_edge > 0 > edge):
+                yield vert
+
+            if edge:
+                last_edge = edge
 
 
 MinimizeSuggestion = tuple[Cycle, int]
@@ -101,8 +109,9 @@ def minimize(balance: Balance) -> list[MinimizeSuggestion]:
     suggestions: list[MinimizeSuggestion] = []
 
     while True:
-        cycles = find_money_cicles(new_balance,
-                                   gen_cycles(set(new_balance.keys())))
+        relevant_vertices = set(exclude_dead_ends(new_balance))
+        cycles = list(
+            find_money_cicles(new_balance, gen_cycles(relevant_vertices)))
         if not cycles:
             return suggestions
         deltas = []
@@ -152,9 +161,25 @@ def test_minimize():
     suggestions = minimize(balance)
     assert len(suggestions) == 0
 
+    # yapf: disable
+    balance = {'A': {'B': 10, 'C': 0, 'D': -10},
+               'B': {'A': -10, 'C': 10, 'D': 0},
+               'C': {'A': 0, 'B': -10, 'D': 10},
+               'D': {'A': 10, 'B': 0, 'C': -10}}
+    # yapf: enable
+
+    suggestions = minimize(balance)
+    assert len(suggestions) == 1
+    cycle, delta = suggestions[0]
+    assert abs(delta) == 10
+    assert 'A' in cycle and 'B' in cycle and 'C' in cycle and 'D' in cycle
+
 
 def main():
     """Entry point listing minimize steps of a particular state file"""
+    import json
+    import argparse
+
     parser = argparse.ArgumentParser()
     parser.add_argument('state_file', default='state.json', nargs='?')
     args = parser.parse_args()
@@ -164,7 +189,4 @@ def main():
 
 
 if __name__ == '__main__':
-    import json
-    import argparse
-
     main()