fork(1) download
copy 
  1. # Split a value x into n approximately equal values with the remainder
  2. # distributed so the sum of the result array is equal to x.
  3.  
  4. # Add one to each result while remainder is non-zero.
  5. # @note Larger values are always toward the front.
  6.  
  7. def split_1(value, interval):
  8.     assert interval > 0
  9.     result = []
  10.     q, r = divmod(value, interval)
  11.     for _ in range(interval):
  12.         if r == 0:
  13.             result.append(q)
  14.         else:
  15.             result.append(q + 1)
  16.             r -= 1
  17.     return result
  18.  
  19. # Recursive split.
  20. # @note One value tends to repeat followed by alternation.
  21.  
  22. def split_2(value, interval):
  23.     if interval <= 0:
  24.         return []
  25.     x = round(value / interval)
  26.     return [x] + split_2(value - x, interval - 1)
  27.  
  28. def rounddiv(a, b):
  29.     return (a + b//2) // b # round half toward +INF
  30.  
  31. def split_2(value, interval):
  32.     assert interval > 0
  33.     result = []
  34.     v = value
  35.     i = interval
  36.     for _ in range(interval):
  37.         x = rounddiv(v, i)
  38.         v = v - x
  39.         i = i - 1
  40.         result.append(x)
  41.     return result
  42.  
  43. # Minimize error on r/t (Bresenham).
  44. # @note Fairly uniform distribution of remainder.
  45.  
  46. def split_3(value, interval):
  47.     assert interval > 0
  48.     result = []
  49.     q, r = divmod(value, interval)
  50.     t = interval - r
  51.     e = 0
  52.     for _ in range(interval):
  53.         if e < t:
  54.             result.append(q)
  55.             e += r
  56.         else:
  57.             result.append(q + 1)
  58.             e -= t
  59.     return result
  60.  
  61. # Main.
  62.  
  63. from timeit import timeit
  64.  
  65. def _test(n, f):
  66.     def check(v, i):
  67.         a = f(v, i)
  68.         ok = len(a) == i
  69.         ok = ok and sum(a) == v
  70.         t = v // i
  71.         ok = ok and all(x == t or x == t+1 for x in a)
  72.         return ok
  73.  
  74.     for v in range(-2*n, 2*n+1):
  75.         for i in range(1, n+1):
  76.             assert check(v, i), f'bad match at {v},{i}'
  77.  
  78. def _show(n, f):
  79.     for i in range(n+1):
  80.         a = f(i, n)
  81.         print(a, sum(a) == i)
  82.  
  83. def _time(n, f):
  84.     def g():
  85.         for v in range(-n, n+1):
  86.             for i in range(1, n+1):
  87.                 f(v, i)
  88.     print('Elapsed: {:.6f}s'.format(timeit(g, number=1)))
  89.  
  90. # ..
  91.  
  92. n = 10
  93. _test(n, split_1)
  94. _test(n, split_2)
  95. _test(n, split_3)
  96.  
  97. n = 5
  98. m = 100
  99. _show(n, split_1)
  100. _time(m, split_1)
  101. _show(n, split_2)
  102. _time(m, split_2)
  103. _show(n, split_3)
  104. _time(m, split_3)
  105.  
  106. n = 100
  107. m = 15
  108. print(split_1(n, m))
  109. print(split_2(n, m))
  110. print(split_3(n, m))
Success #stdin #stdout 0.43s 14120KB
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.050364s
[0, 0, 0, 0, 0] True
[0, 0, 0, 1, 0] True
[0, 1, 0, 1, 0] True
[1, 1, 0, 1, 0] True
[1, 1, 1, 1, 0] True
[1, 1, 1, 1, 1] True
Elapsed: 0.198435s
[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.099216s
[7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6]
[7, 7, 7, 7, 7, 7, 6, 7, 6, 7, 6, 7, 6, 7, 6]
[6, 7, 7, 6, 7, 7, 6, 7, 7, 6, 7, 7, 6, 7, 7]
https://ideone.com/3fJiEn
language:
Python 3 (python  3.12)
created:
2 days 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!