HowManySandwichesInSalad.py

import timeit

# Starting from a particular crouton in the salad, traverse down to all other croutons
def myDFS(salad,crouton,length,paths,path=[]):
    if crouton in path:
        return
    path=path+[crouton]
    if len(path)==length:
        paths.append(path)
    else:
        for node in salad[crouton]:
            myDFS(salad,node,length,paths,path)

def calculate_sandiwches(croutons):
    # Create the connected salad of possible paths between croutons
    # e.g. (if there are four, crouton 1 could connect to croutons 0, 2, 3)
    salad = {}
    for i in range(croutons):
        temp = range(croutons)
        temp.pop(i)
        salad[i] = temp

    # Sandwich paths are length 1 to length croutons-1
    lengths = range(2, croutons+1)

    paths = []

    for length in lengths:
        for a in salad:
            myDFS(salad,a,length,paths)

    # Divide by 2 because we double count each path
    print len(paths) / 2


# How many croutons in our salad
croutons = 11

for i in range(croutons):
    start = timeit.default_timer()
    calculate_sandiwches(i)
    stop = timeit.default_timer()
    print('Time: ', stop - start)

# Code adapted from https://stackoverflow.com/questions/30989251/salad-theory-finding-all-possible-paths-of-n-length-with-some-constraints