Skip to content

Instantly share code, notes, and snippets.

@pohatu

pohatu/freqofsums.py

Created October 15, 2013 06:27
Show Gist options
  • Save pohatu/6987348 to your computer and use it in GitHub Desktop.
Save pohatu/6987348 to your computer and use it in GitHub Desktop.
Download ZIP
Calculates the frequency of sums for n samples of digits from 1-n.
Raw
freqofsums.py
#!/usr/local/bin/python2.7
from collections import defaultdict
def freq_of_sums(a, b, v):
if (b == 0):
global freq
if freq.has_key(v):
freq[v]=freq[v]+1
else:
freq[v]=1
return
else:
for i in range(1, a+1):
freq_of_sums(a, b-1, v+i)
for i in range(1, 5):
global freq
freq=defaultdict(dict)
freq_of_sums(i, i, 0)
print freq
@pohatu
Copy link
Author

pohatu commented Oct 15, 2013

running this for n larger than 5 may take an extremely long time! It is at least O(n^n), maybe worse.

@pohatu
Copy link
Author

pohatu commented Oct 15, 2013

defaultdict(, {1: 1})
defaultdict(, {2: 1, 3: 2, 4: 1})
defaultdict(, {3: 1, 4: 3, 5: 6, 6: 7, 7: 6, 8: 3, 9: 1})
defaultdict(, {4: 1, 5: 4, 6: 10, 7: 20, 8: 31, 9: 40, 10: 44, 11: 40, 12: 31, 13: 20, 14: 10, 15: 4, 16: 1})
defaultdict(, {5: 1, 6: 5, 7: 15, 8: 35, 9: 70, 10: 121, 11: 185, 12: 255, 13: 320, 14: 365, 15: 381, 16: 365, 17: 320, 18: 255, 19: 185, 20: 121, 21: 70, 22: 35, 23: 15, 24: 5, 25: 1})

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment