fogleman/permutations.py

## 44 changes: 44 additions & 0 deletions permutations.py
@@ -0,0 +1,44 @@

    import itertools
import itertools

    import math
import math


    # https://www.wolframalpha.com/input/?i=1,6,90,2520,113400
# https://www.wolframalpha.com/input/?i=1,6,90,2520,113400

    # a(n) = (2n)! / 2^n
# a(n) = (2n)! / 2^n

    # https://oeis.org/A000680
# https://oeis.org/A000680

    def f(n):
def f(n):

        return math.factorial(2 * n) / (2 ** n)
    return math.factorial(2 * n) / (2 ** n)


    def brute():
def brute():

        for n in range(6):
    for n in range(6):

            x = range(n) * 2
        x = range(n) * 2

            p = list(itertools.permutations(x))
        p = list(itertools.permutations(x))

            q = set(p)
        q = set(p)

            print n, len(p), len(q)
        print n, len(p), len(q)


    def formulaic():
def formulaic():

        # 33 rides => more permutations than # of atoms in universe
    # 33 rides => more permutations than # of atoms in universe

        for n in range(20):
    for n in range(20):

            print n, f(n)
        print n, f(n)


    def g(nrides, nvehicles):
def g(nrides, nvehicles):

        vehicles = range(nvehicles)
    vehicles = range(nvehicles)

        r = 0
    r = 0

        for assignment in itertools.product(vehicles, repeat=nrides):
    for assignment in itertools.product(vehicles, repeat=nrides):

            p = 1
        p = 1

            for vehicle in vehicles:
        for vehicle in vehicles:

                p *= f(assignment.count(vehicle))
            p *= f(assignment.count(vehicle))

            # print assignment, p
        # print assignment, p

            r += p
        r += p

        return r
    return r


    # 2 vehicles: https://oeis.org/A034405
# 2 vehicles: https://oeis.org/A034405

    def main():
def main():

        values = []
    values = []

        for rides in range(1, 9):
    for rides in range(1, 9):

            for vehicles in [2]:
        for vehicles in [2]:

                result = g(rides, vehicles)
            result = g(rides, vehicles)

                print vehicles, rides, result
            print vehicles, rides, result

                values.append(result)
            values.append(result)

        print ','.join(map(str, values))
    print ','.join(map(str, values))


    if __name__ == '__main__':
if __name__ == '__main__':

        main()
    main()