brute force random combination

combinat.py

import functools
import collections
import random


@functools.lru_cache(maxsize=None)
def c(n, k):
    if k == 0 or k == n:
        return 1
    else:
        return c(n - 1, k) + c(n - 1, k - 1)


def combinat(ls, k):
    if k == 0:
        yield []
    elif k == len(ls):
        yield ls
    else:
        yield from combinat(ls[1:], k)
        for x in combinat(ls[1:], k-1):
            yield [ls[0]] + x


def random_combinat(ls, k):
    n = len(ls)
    if k == 0:
        return []
    elif k == n:
        return ls
    else:
        p1 = c(n-1, k-1)
        p2 = c(n-1, k)
        coin = random.randint(1, p1 + p2)
        if coin <= p1:
            return [ls[0]] + random_combinat(ls[1:], k-1)
        else:
            return random_combinat(ls[1:], k)


def main():
    ls = [1, 2, 3, 4, 5, 6]
    k = 3
    n_samples = 10000
    samples = [tuple(random_combinat(ls, k)) for _ in range(n_samples)]
    for k, v in collections.Counter(samples).items():
        print("{}:{}".format(k, v / n_samples))


if __name__ == "__main__":
    main()