Skip to content

Instantly share code, notes, and snippets.

@fogleman
Created March 19, 2016 22:02
Show Gist options
  • Save fogleman/f1bd39296f916f6df94e to your computer and use it in GitHub Desktop.
Save fogleman/f1bd39296f916f6df94e to your computer and use it in GitHub Desktop.
Permutations of Rides & Vehicles
import itertools
import math
# https://www.wolframalpha.com/input/?i=1,6,90,2520,113400
# a(n) = (2n)! / 2^n
# https://oeis.org/A000680
def f(n):
return math.factorial(2 * n) / (2 ** n)
def brute():
for n in range(6):
x = range(n) * 2
p = list(itertools.permutations(x))
q = set(p)
print n, len(p), len(q)
def formulaic():
# 33 rides => more permutations than # of atoms in universe
for n in range(20):
print n, f(n)
def g(nrides, nvehicles):
vehicles = range(nvehicles)
r = 0
for assignment in itertools.product(vehicles, repeat=nrides):
p = 1
for vehicle in vehicles:
p *= f(assignment.count(vehicle))
# print assignment, p
r += p
return r
# 2 vehicles: https://oeis.org/A034405
def main():
values = []
for rides in range(1, 9):
for vehicles in [2]:
result = g(rides, vehicles)
print vehicles, rides, result
values.append(result)
print ','.join(map(str, values))
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment