"""
Idea from Brian Hayes:
http://bit-player.org/2009/computing-in-the-classroom

>There is a very simple algorithm for approximating the average. Have the students form random
pairs repeatedly; in each pair, both students replace the value on their ticket with the average
of the two values (in other words, they apply the "dot" operator). In this procedure the students
never actually calculate either N or the sum, but both of those quantities are conserved as
invariants of the computation. As the random process continues, all of the tickets eventually
converge on the same value, namely the overall average. Experiments suggest that about log2(N)
rounds of random coupling yield a reasonably good approximation.<

Python implementation by leonardo maffi, V.1.0, Apr 12 2009
"""

from random import shuffle, gauss
from math import log, ceil

try:
    import psyco
    psyco.full()
except:
    pass


def approx_avg(input_data):
    def random_pairs(n):
        indexes = range(n)
        shuffle(indexes)
        for i in xrange(0, (n // 2) * 2, 2):
            yield indexes[i], indexes[i+1]

    data = list(input_data)
    n = len(data)
    if not n:
        return

    nloops = int(ceil(log(n, 2)))
    # **************
    if n < 200:
        nloops += 8
    elif n < 2000:
        nloops += 3
    # **************

    for nloop in xrange(nloops):
        for i1, i2 in random_pairs(n):
            avg2 = (data[i1] + data[i2]) / 2.0
            data[i1] = data[i2] = avg2

    return nloops, data[0]


def main():
    n = 500
    avg1 = 3.2
    avg2 = avg1 + 3
    data = [(gauss(avg, 10) if n % 2 else gauss(avg2, 10) ) for _ in xrange(n)]
    if len(data) <= 300:
        print data
    print "# items:", n
    print "Specified averages:", avg1, avg2
    print "True average:", sum(data) / float(len(data))
    nloops, app_avg = approx_avg(data)
    print "N.loops, approximated average:", nloops, app_avg
    print "# pair-averages computed:", (n / 2.0) * nloops

if __name__ == "__main__":
    main()