#
# program to produce all permutations of a list
#
# Matt Bishop, MHI 289I, Fall 2021
#
#
# this is the list to be permuted
#
data = [ 'a', 'b', 'c'  ]
#
# this function does the permutation
#
def perm(lst):

    # base cases: if list is empty or
    # has 1 element, return it as a list
    # so it can be appended to the list
    # of permutations
    if len(lst) == 0:
        return [ ]
    if len(lst) == 1:
        return [ lst ]

    # this will hold the permuted lists of lst
    intlst = [ ]

    # move each element in the list to the front
    # and permute the rest of the list; for each
    # permutation, prepend the front element and
    # save the result in the list of permutations
    for i in range(len(lst)):
        
        # drop the i-th element; this gives you
        # the rest of the list to be permuted
        remlst = lst[:i] + lst[i+1:]
        
        # generate the permutations of the rest
        # for each permutation, prepend the one
        # you held back and add it to the list of
        # permutations
        for p in perm(remlst):
            intlst.append([ lst[i] ] + p)

    # return the list of permutations
    return intlst

#
# this deletes any duplicates
# it copies the elements into a new list after
# checking whether the element is already in
# the list; if it is, do not copy it
def deldup(lst):

    # start the new list
    newlst = [ ]

    # walk down the list, checking as above
    for i in lst:
        if i not in newlst:
            newlst.append(i)

    # return the new list with no duplicates
    return newlst

#
# compute the list of permutations,
# deleting any duplicates
#
uselst = deldup(perm(data))

#
# now print the results
#
for p in uselst:
    print(p)