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