HW8 Counting

.gitignore

/.idea/
__pycache__/
/*.txt

coats.py

#!/usr/bin/env python3
from collections import defaultdict
from itertools import permutations, combinations
from math import factorial as fact
from typing import Tuple, List, Sequence, Optional, Dict
from unittest import TestCase

def choose(n, r):
    return fact(n) // fact(r) // fact(n - r)


def is_derangement(ordering: Sequence[int]):
    for i, value in enumerate(ordering):
        if i == value:
            return True
    return False


def num_derangements(n: int, precomputed: Optional[Dict[int, int]]=None):
    if n == 0:
        return 1
    if n == 1:
        return 0
    if precomputed is None:
        precomputed: Dict[int, int] = {}
    current = precomputed.get(n, None)
    if current is not None:
        return current
    previous = precomputed.get(n - 1, None)
    if previous is None:
        previous = num_derangements(n - 1, precomputed)
    offset = 1 if n % 2 == 0 else -1
    current = n * previous + offset
    precomputed[n] = current
    return current


class Test(TestCase):

    def test_num_derangements(self):
        known = dict(enumerate([1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932]))
        cache = {}
        for n in sorted(known.keys()):
            with self.subTest():
                expected = known[n]
                actual = num_derangements(n, cache)
                self.assertEqual(expected, actual)

def main():
    cache = {}
    total = 0
    d = num_derangements
    m = 10
    ten_factorial = fact(10)
    ev = 0
    for n in range(0, m + 1):
        count = choose(m, n) * d(m - n, cache)
        print(f"n={n}: {count}")
        total += count
        ev += n * (count / ten_factorial)
    print(f"total = {total}")
    print(f"  10! = {fact(10)}")
    print(f" E[C] = {ev}")
    return 0


if __name__ == '__main__':
    exit(main())

coins.py

#!/usr/bin/env python3

"""Calculates probabilities of ranges of success event counts in Bernouilli trials."""

import argparse
from math import factorial as fact

def choose(n, r):
    return fact(n) // fact(r) // fact(n - r)


def accumulate(min_successes: int, max_successes: int, n: int, p: float):
    assert min_successes <= max_successes
    assert min_successes >= 0
    assert max_successes <= n
    total = 0
    q = 1 - p
    for k in range(min_successes, max_successes + 1):
        this_trial = choose(n, k) * (p ** k) * (q ** (n - k))
        total += this_trial
        print(f"{total:.4f} cumulative; C({n},{k}) * {p}^{k} * {q}^{n - k} = {this_trial:.4f}")
    return total


def main():
    parser = argparse.ArgumentParser()
    parser.add_argument("min_successes", type=int)
    parser.add_argument("max_successes", type=int)
    parser.add_argument("-n", "--trials", type=int, default=10)
    parser.add_argument("-p", "--probability-success", type=float, default=0.5)
    args = parser.parse_args()
    accumulate(args.min_successes, args.max_successes, args.trials, args.probability_success)
    return 0


if __name__ == '__main__':
    exit(main())

ex632.py

#!/usr/bin/env python3
from collections import defaultdict
from itertools import permutations, combinations
from math import factorial as fact
from typing import Tuple


def choose(n, r):
    return fact(n) // fact(r) // fact(n - r)


class Event(object):

    def __init__(self, name, predicate):
        self.name = name
        self.predicate = predicate

    def __call__(self, ordering):
        return self.predicate(ordering)

    def __str__(self):
        return self.name

A = Event('A', lambda x: x[3] == 'b')
B = Event('B', lambda x: x.find('b') > x.find('c'))
C = Event('C', lambda x: 'def' in x)


def And(events: Tuple[Event, Event]) -> Event:
    x, y = events
    return Event(f"{x} and {y}", lambda q: x(q) and y(q))


# noinspection PyPep8Naming
def main():
    orderings = permutations('abcdefg')
    n = 0
    events = [A, B, C] + list(map(And, combinations([A, B, C], 2)))
    counts = defaultdict(int)
    with open('abcdef.txt', 'w') as ofile:
        for ordering in map(lambda x: ''.join(x), orderings):
            print(ordering, file=ofile)
            n += 1
            for event in events:
                if event(ordering):
                    counts[str(event)] += 1
    for event in sorted(counts.keys()):
        count = counts[event]
        print(f"|{event}| = {count}")
    print(f"C(4,2) = {choose(4, 2)}")
    print(f"C(7,2) = {choose(7, 2)}")
    print(f"C(7,2) * 5! = {choose(7, 2) * fact(5)}")
    print(f"7! = {fact(7)}")
    return 0


if __name__ == '__main__':
    exit(main())