fork download
copy 
  1. # interval.py (2.0)
  2. # Split a value x into approximately equal intervals with the remainder
  3. # distributed so the sum of the result sequence is equal to x.
  4.  
  5. # Increment while remainder is non-zero.
  6. # @note Remainder is always distributed at the front.
  7.  
  8. def split_1(value, interval):
  9.     assert interval > 0
  10.     result = []
  11.     q, r = divmod(value, interval)
  12.     for _ in range(interval):
  13.         if r == 0:
  14.             result.append(q)
  15.         else:
  16.             result.append(q + 1)
  17.             r -= 1
  18.     return result
  19.  
  20. # Recursive split.
  21. # @note One value tends to repeat followed by alternation.
  22.  
  23. def split_2(value, interval):
  24.     if interval <= 0:
  25.         return []
  26.     x = round(value / interval)
  27.     return [x] + split_2(value - x, interval - 1)
  28.  
  29. def split_2(value, interval):
  30.     assert interval > 0
  31.     result = []
  32.     v = value
  33.     i = interval
  34.     for _ in range(interval):
  35.         x = round(v / i)
  36.         v = v - x
  37.         i = i - 1
  38.         result.append(x)
  39.     return result
  40.  
  41. # Minimize error on r/t (Bresenham).
  42. # @note Uniform distribution of remainder (rear biased).
  43.  
  44. def split_3(value, interval):
  45.     assert interval > 0
  46.     result = []
  47.     q, r = divmod(value, interval)
  48.     t = interval - r
  49.     e = 0
  50.     for _ in range(interval):
  51.         if e < t:
  52.             result.append(q)
  53.             e += r
  54.         else:
  55.             result.append(q + 1)
  56.             e -= t
  57.     return result
  58.  
  59. # Minimize error on r/t (Bresenham).
  60. # @note Uniform distribution of remainder (symmetric).
  61.  
  62. def split_4(value, interval):
  63.     assert interval > 0
  64.     result = []
  65.     q, r = divmod(value, interval)
  66.     t = interval
  67.     e = t-r
  68.     for _ in range(interval):
  69.         e2 = 2*e
  70.         if e2 + r > 0:
  71.             e -= r
  72.         if e2 - t < 0:
  73.             result.append(q + 1)
  74.             e += t
  75.         else:
  76.             result.append(q)
  77.     return result
  78.  
  79. # Main.
  80.  
  81. from timeit import timeit
  82.  
  83. def _test(n, f):
  84.     def check(v, i):
  85.         a = f(v, i)
  86.         ok = len(a) == i
  87.         ok = ok and sum(a) == v
  88.         t = v // i
  89.         ok = ok and all(x == t or x == t+1 for x in a)
  90.         return ok
  91.  
  92.     for v in range(-2*n, 2*n+1):
  93.         for i in range(1, n+1):
  94.             assert check(v, i), f'bad match at {v},{i}'
  95.  
  96. def _show(n, f):
  97.     for i in range(n+1):
  98.         a = f(i, n)
  99.         print(a, sum(a) == i)
  100.  
  101. def _time(n, f):
  102.     def g():
  103.         for v in range(-n, n+1):
  104.             for i in range(1, n+1):
  105.                 f(v, i)
  106.     print('Elapsed: {:.6f}s'.format(timeit(g, number=1)))
  107.  
  108. def _main():
  109.     fs = [
  110.         split_1,
  111.         split_2,
  112.         split_3,
  113.         split_4
  114.     ]
  115.  
  116.     n = 10
  117.     for f in fs:
  118.         _test(n, f)
  119.  
  120.     n = 5
  121.     m = 100
  122.     for f in fs:
  123.         _show(n, f)
  124.         _time(m, f)
  125.  
  126.     n = 100
  127.     m = 15
  128.     for f in fs:
  129.         print(f(n, m))
  130.  
  131. if __name__ == '__main__':
  132.     _main()
Success #stdin #stdout 0.68s 14092KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[0, 0, 0, 0, 0] True
[1, 0, 0, 0, 0] True
[1, 1, 0, 0, 0] True
[1, 1, 1, 0, 0] True
[1, 1, 1, 1, 0] True
[1, 1, 1, 1, 1] True
Elapsed: 0.057807s
[0, 0, 0, 0, 0] True
[0, 0, 0, 0, 1] True
[0, 0, 1, 0, 1] True
[1, 0, 1, 0, 1] True
[1, 1, 1, 0, 1] True
[1, 1, 1, 1, 1] True
Elapsed: 0.306156s
[0, 0, 0, 0, 0] True
[0, 0, 0, 0, 1] True
[0, 0, 1, 0, 1] True
[0, 1, 0, 1, 1] True
[0, 1, 1, 1, 1] True
[1, 1, 1, 1, 1] True
Elapsed: 0.071120s
[0, 0, 0, 0, 0] True
[0, 0, 1, 0, 0] True
[0, 1, 0, 1, 0] True
[1, 0, 1, 0, 1] True
[1, 1, 0, 1, 1] True
[1, 1, 1, 1, 1] True
Elapsed: 0.165472s
[7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6]
[7, 7, 7, 7, 7, 6, 7, 6, 7, 6, 7, 6, 7, 6, 7]
[6, 7, 7, 6, 7, 7, 6, 7, 7, 6, 7, 7, 6, 7, 7]
[7, 6, 7, 7, 6, 7, 7, 6, 7, 7, 6, 7, 7, 6, 7]
https://ideone.com/8HGRUK
language:
Python 3 (python  3.12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!