xiwal

commit

ffb400a789b9abb5ba727e96ec4df66aa549eafe

parent

555ff4935ee4dad738d61af2d25668e81f10e0fd

Author

Tobias Bengfort <tobias.bengfort@posteo.de>

Date

2026-01-28 09:46

optimize permutations

- faster because there is less allocations (?)
- skip some permutations based on their lowest possible score

Diffstat

1 files changed, 36 insertions, 13 deletions

diff --git a/xiwal/scheme.py b/xiwal/scheme.py

@@ -1,5 +1,4 @@
    1     1 import functools
    2    -1 import itertools
    3     2 import math
    4     3 
    5     4 from . import lch
@@ -41,16 +40,40 @@ def distance(color, i):
   41    40     return d ** 4 * c, c
   42    41 
   43    42 
   44    -1 def score(colors):
   45    -1     sum_score = 0
   46    -1     sum_chroma = 0
   47    -1 
   48    -1     for i, color in enumerate(colors):
   49    -1         score, chroma = distance(color, i)
   50    -1         sum_score += score
   51    -1         sum_chroma += chroma
   52    -1 
   53    -1     return sum_score / sum_chroma
   -1    43 def get_best_subset(colors, n):
   -1    44     # perf: skip some permutations based on their lowest possible score
   -1    45     pos = 0
   -1    46     indices = [0] * n
   -1    47     dists = [0] * n
   -1    48     weights = [1] * n
   -1    49     best_score = math.inf
   -1    50     best_colors = None
   -1    51     while True:
   -1    52         dists[pos], weights[pos] = distance(colors[indices[pos]], pos)
   -1    53         score = sum(dists) / sum(weights)
   -1    54 
   -1    55         if score < best_score and pos + 1 == n:
   -1    56             best_score = score
   -1    57             best_colors = [colors[i] for i in indices]
   -1    58 
   -1    59         if score < best_score and pos + 1 < n:
   -1    60             pos += 1
   -1    61         else:
   -1    62             indices[pos] += 1
   -1    63 
   -1    64         while True:
   -1    65             if indices[pos] == len(colors):
   -1    66                 if pos == 0:
   -1    67                     return best_colors
   -1    68                 indices[pos] = 0
   -1    69                 dists[pos] = 0
   -1    70                 weights[pos] = 1
   -1    71                 pos -= 1
   -1    72                 indices[pos] += 1
   -1    73             elif indices[pos] in indices[:pos]:
   -1    74                 indices[pos] += 1
   -1    75             else:
   -1    76                 break
   54    77 
   55    78 
   56    79 def scheme(colors, dominant):
@@ -76,6 +99,6 @@ def scheme(colors, dominant):
   76    99 def colors2scheme(colors):
   77   100     colors = [lch.from_hex(c) for c in colors]
   78   101     dominant = colors[0]
   79    -1     colors = min(itertools.permutations(colors, 6), key=score)
   80    -1     s = scheme(colors, dominant)
   -1   102     subset = get_best_subset(colors, 6)
   -1   103     s = scheme(subset, dominant)
   81   104     return [lch.to_hex(c) for c in s]