#!/usr/bin/env python3

# Kryger Permutation Counting
#
# Algorithm developed by Landon Kryger, May 2012

dice = 'abcdeecdabdbaececdabbecdadbcaeacbdeecdabbeacdeabdcdacebbacdedcaebacbdeabcdeedcbaedbcabeacdedcabbecadcdbaedcaebbadceedbcaeacbdadcebbadceceabdbadceedcba'

perms = {'': 1} # A dictionary tracking the counts for each permutation

# For each letter d in the dice string
for d in dice:

    # Find permutations in the dictionary that don't yet have this die
    for p in list(filter(lambda f: f.count(d) == 0, perms.keys())):
        np = d + p # The new permutation is the one found plus this die

        perms[np] = perms.get(np, 0) + perms[p] # This is the dynamic programming step


# Print each permutation count, sorted by permutation
for p in sorted(perms.keys(), key=lambda p: str(len(p)) + p):
    print("%-5s -> %d" % (p, perms[p]))

# Output:
#       -> 1
# a     -> 30
# b     -> 30
# c     -> 30
# d     -> 30
# e     -> 30
# ab    -> 450
# ac    -> 450
# ad    -> 450
# ae    -> 450
# ba    -> 450
# bc    -> 450
# bd    -> 450
# be    -> 450
# ca    -> 450
# cb    -> 450
# cd    -> 450
# ce    -> 450
# da    -> 450
# db    -> 450
# dc    -> 450
# de    -> 450
# ea    -> 450
# eb    -> 450
# ec    -> 450
# ed    -> 450
# abc   -> 4512
# abd   -> 4540
# abe   -> 4504
# acb   -> 4516
# acd   -> 4462
# ace   -> 4530
# adb   -> 4454
# adc   -> 4512
# ade   -> 4470
# aeb   -> 4524
# aec   -> 4476
# aed   -> 4500
# bac   -> 4472
# bad   -> 4506
# bae   -> 4472
# bca   -> 4516
# bcd   -> 4472
# bce   -> 4538
# bda   -> 4454
# bdc   -> 4532
# bde   -> 4490
# bea   -> 4524
# bec   -> 4500
# bed   -> 4524
# cab   -> 4472
# cad   -> 4526
# cae   -> 4494
# cba   -> 4512
# cbd   -> 4496
# cbe   -> 4462
# cda   -> 4512
# cdb   -> 4532
# cde   -> 4542
# cea   -> 4476
# ceb   -> 4500
# ced   -> 4476
# dab   -> 4506
# dac   -> 4526
# dae   -> 4530
# dba   -> 4540
# dbc   -> 4496
# dbe   -> 4486
# dca   -> 4462
# dcb   -> 4472
# dce   -> 4482
# dea   -> 4500
# deb   -> 4524
# dec   -> 4476
# eab   -> 4472
# eac   -> 4494
# ead   -> 4530
# eba   -> 4504
# ebc   -> 4462
# ebd   -> 4486
# eca   -> 4530
# ecb   -> 4538
# ecd   -> 4482
# eda   -> 4470
# edb   -> 4490
# edc   -> 4542
# abcd  -> 33510
# abce  -> 34500
# abdc  -> 34830
# abde  -> 34200
# abec  -> 33810
# abed  -> 34170
# acbd  -> 33930
# acbe  -> 33420
# acdb  -> 33660
# acde  -> 33810
# aceb  -> 34200
# aced  -> 33840
# adbc  -> 33000
# adbe  -> 32850
# adcb  -> 33510
# adce  -> 33660
# adeb  -> 33660
# adec  -> 32940
# aebc  -> 33540
# aebd  -> 33900
# aecb  -> 33960
# aecd  -> 33120
# aedb  -> 33600
# aedc  -> 34380
# bacd  -> 32760
# bace  -> 33780
# badc  -> 34020
# bade  -> 33390
# baec  -> 32970
# baed  -> 33330
# bcad  -> 34380
# bcae  -> 33900
# bcda  -> 33510
# bcde  -> 33960
# bcea  -> 33960
# bced  -> 33960
# bdac  -> 33450
# bdae  -> 33510
# bdca  -> 33660
# bdce  -> 33960
# bdea  -> 33600
# bdec  -> 33240
# beac  -> 34020
# bead  -> 34560
# beca  -> 34200
# becd  -> 33480
# beda  -> 33660
# bedc  -> 34740
# cabd  -> 33930
# cabe  -> 33390
# cadb  -> 33450
# cade  -> 33690
# caeb  -> 34020
# caed  -> 33660
# cbad  -> 34020
# cbae  -> 33510
# cbda  -> 33000
# cbde  -> 33540
# cbea  -> 33540
# cbed  -> 33540
# cdab  -> 34020
# cdae  -> 34380
# cdba  -> 34830
# cdbe  -> 34020
# cdea  -> 34380
# cdeb  -> 34740
# ceab  -> 32970
# cead  -> 33840
# ceba  -> 33810
# cebd  -> 33540
# ceda  -> 32940
# cedb  -> 33240
# dabc  -> 34020
# dabe  -> 33900
# dacb  -> 34380
# dace  -> 34590
# daeb  -> 34560
# daec  -> 33840
# dbac  -> 33930
# dbae  -> 33930
# dbca  -> 33930
# dbce  -> 34260
# dbea  -> 33900
# dbec  -> 33540
# dcab  -> 32760
# dcae  -> 33090
# dcba  -> 33510
# dcbe  -> 32760
# dcea  -> 33120
# dceb  -> 33480
# deab  -> 33330
# deac  -> 33660
# deba  -> 34170
# debc  -> 33540
# deca  -> 33840
# decb  -> 33960
# eabc  -> 33510
# eabd  -> 33930
# eacb  -> 33900
# eacd  -> 33090
# eadb  -> 33510
# eadc  -> 34380
# ebac  -> 33390
# ebad  -> 33900
# ebca  -> 33420
# ebcd  -> 32760
# ebda  -> 32850
# ebdc  -> 34020
# ecab  -> 33780
# ecad  -> 34590
# ecba  -> 34500
# ecbd  -> 34260
# ecda  -> 33660
# ecdb  -> 33960
# edab  -> 33390
# edac  -> 33690
# edba  -> 34200
# edbc  -> 33540
# edca  -> 33810
# edcb  -> 33960
# abcde -> 204780
# abced -> 207164
# abdce -> 211392
# abdec -> 203188
# abecd -> 200646
# abedc -> 213030
# acbde -> 202466
# acbed -> 201464
# acdbe -> 201024
# acdeb -> 207952
# acebd -> 204828
# acedb -> 200866
# adbce -> 200732
# adbec -> 193484
# adcbe -> 193974
# adceb -> 200970
# adebc -> 197494
# adecb -> 199546
# aebcd -> 195516
# aebdc -> 207476
# aecbd -> 205066
# aecdb -> 200352
# aedbc -> 200332
# aedcb -> 206258
# bacde -> 198078
# baced -> 200878
# badce -> 202732
# badec -> 194488
# baecd -> 192020
# baedc -> 204304
# bcade -> 205132
# bcaed -> 203634
# bcdae -> 204552
# bcdea -> 206258
# bcead -> 207578
# bceda -> 199546
# bdace -> 204718
# bdaec -> 198466
# bdcae -> 199606
# bdcea -> 200352
# bdeac -> 200192
# bdeca -> 200866
# beacd -> 199380
# beadc -> 213076
# becad -> 211384
# becda -> 200970
# bedac -> 203838
# bedca -> 207952
# cabde -> 204174
# cabed -> 202796
# cadbe -> 196286
# cadeb -> 203838
# caebd -> 204114
# caedb -> 200192
# cbade -> 201270
# cbaed -> 199064
# cbdae -> 197958
# cbdea -> 200332
# cbead -> 205382
# cbeda -> 197494
# cdabe -> 206000
# cdaeb -> 213076
# cdbae -> 209814
# cdbea -> 207476
# cdeab -> 204304
# cdeba -> 213030
# ceabd -> 199822
# ceadb -> 198466
# cebad -> 203952
# cebda -> 193484
# cedab -> 194488
# cedba -> 203188
# dabce -> 210932
# dabec -> 203952
# dacbe -> 203672
# daceb -> 211384
# daebc -> 205382
# daecb -> 207578
# dbace -> 206994
# dbaec -> 199822
# dbcae -> 204076
# dbcea -> 205066
# dbeac -> 204114
# dbeca -> 204828
# dcabe -> 192444
# dcaeb -> 199380
# dcbae -> 197194
# dcbea -> 195516
# dceab -> 192020
# dceba -> 200646
# deabc -> 199064
# deacb -> 203634
# debac -> 202796
# debca -> 201464
# decab -> 200878
# decba -> 207164
# eabcd -> 197194
# eabdc -> 209814
# eacbd -> 204076
# eacdb -> 199606
# eadbc -> 197958
# eadcb -> 204552
# ebacd -> 192444
# ebadc -> 206000
# ebcad -> 203672
# ebcda -> 193974
# ebdac -> 196286
# ebdca -> 201024
# ecabd -> 206994
# ecadb -> 204718
# ecbad -> 210932
# ecbda -> 200732
# ecdab -> 202732
# ecdba -> 211392
# edabc -> 201270
# edacb -> 205132
# edbac -> 204174
# edbca -> 202466
# edcab -> 198078
# edcba -> 204780

