Complexity calculation for sorting a list of N items by flipping a coin.

coin_flips.py

# How many coin flips does it take to randomly shuffle a list of length N?

# My guess is to start with a list of all possible permutations, e.g.

# ABC
# ACB
# BAC
# BCA
# CAB
# CBA

# Then run binary search on that list using coin flips.
# In the case of an odd N, flip to determine what side of the middle
# number you divide the list on <-- not sure if that's completely random.

# So n_flips is bound by log(N!) <= n_flips <= 2log(N!)

from __future__ import division

from collections import Counter
import random
import math

import bunch


def flip():
    return random.choice([0,1])


def flip_n(n):
    return [flip() for i in range(n)]


def combos(n):
    return math.factorial(n)


def cut_list(n):

    if n % 2 == 0:
        return n//2
    else:
        return n//2 + flip()


def mean(num_list):

    return sum(x for x in num_list) / len(num_list)


def flip_to_find(n):

    x = combos(n)

    flip_count = 0
    while x > 1:

        flip_count += 1

        if x % 2 == 0:
            x = x//2
        else:
            x = x//2 + flip()
            flip_count += 1


    return flip_count


stats = []

for n in range(1, 25):
    flips = [flip_to_find(n) for _ in range(10000)]

    stats.append(
        bunch.Bunch(
            n=n,
            f_avg=mean(flips),
            f_max=max(flips),
            f_min=min(flips),
            log_2=math.log(combos(n), 2),
        )
    )

for s in stats:
    print '{n} | min: {f_min} | max: {f_max} | avg: {f_avg} | log_2: {log_2}'.format(**s)