#
# program to produce all permutations of a list
#
# Matt Bishop, MHI 289I, Fall 2022
#
#
# this is the list to be permuted
#
data = [ 1, 2, 3, 4  ]
#
# this function does the permutation
#
def perm(L):

    # 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(L) == 0:
        return [ ]
    if len(L) == 1:
        return [ L ]

    # this will hold the permuted lists of L
    I = [ ]

    # 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(L)):
        
        # drop the i-th element; this gives you
        # the rest of the list to be permuted
        R = L[:i] + L[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 e in perm(R):
            P = [ L[i] ] + e
            I.append(P)

    # return the list of permutations
    return I

#
# 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)