"""Finite authored Algorithm R and exhaustive 60-branch small probability check."""
from collections import Counter
from fractions import Fraction
from itertools import product,combinations
import json,platform,random
def reservoir(items,k,rng):
 if type(k) is not int or not 0<=k<=8:raise ValueError('integer k in 0..8')
 bag=[];trace=[]
 for j,item in enumerate(items,1):
  if j>32:raise ValueError('authored stream limit32')
  m=None
  if j<=k:bag.append(item)
  elif k:
   m=rng.randrange(j)
   if m<k:bag[m]=item
  assert len(bag)<=k
  trace.append({'position':j,'draw_zero_based':m,'retained_positions':[x['position'] for x in bag]})
 return bag,trace
class Choices:
 def __init__(self,choices):self.choices=iter(choices)
 def randrange(self,n):
  x=next(self.choices);assert 0<=x<n;return x
def demo():
 items=[{'position':i,'content':'same' if i in [2,3] else 'row'+str(i)} for i in range(1,6)]
 bag,trace=reservoir(iter(items),2,random.Random(37));counts=Counter()
 for choices in product(range(3),range(4),range(5)):
  out,_=reservoir(iter(items),2,Choices(choices));counts[tuple(sorted(x['position'] for x in out))]+=1
 assert sum(counts.values())==60 and set(counts)==set(combinations(range(1,6),2)) and set(counts.values())=={6}
 probabilities=[{'subset':list(key),'branches':n,'probability':str(Fraction(n,60))} for key,n in sorted(counts.items())]
 small,_=reservoir(iter(items[:1]),2,random.Random(37));assert small==items[:1]
 assert reservoir(iter([]),2,random.Random(37))[0]==[] and reservoir(iter(items),0,random.Random(37))[0]==[]
 rejects=[]
 for k in [-1,True,9]:
  try:reservoir(iter(items),k,random.Random(37))
  except ValueError:rejects.append(repr(k))
  else:raise AssertionError('bad k accepted')
 return {'runtime':platform.python_version(),'N5_k2_seed37':{'selected':bag,'trace':trace},'exhaustive60':probabilities,'short_stream_returns_available':small,'rejected_k':rejects,'scope':'Tiny finite exact check, not proof for all N, representativeness, class balance, independence or distributed sampling. Row positions distinguish equal content.'}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))