""" permute.py Generate the permutations of a list, using a backtracking tree search. This code is based on the ideas at geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string There are other trickier approaches to this classic task; see wikipedia.org/wiki/Heap%27s_algorithm and wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations . And python has a built-in library to do this sort of thing; see https://docs.python.org/3/library/itertools.html . Jim Mahoney | cs.bennington.collete | April 2022 | MIT License """ def swap(xs, i, j): (xs[i], xs[j]) = (xs[j], xs[i]) def permute(xs, i=0, result=[]): """ return permutations of a list xs """ if i == len(xs) - 1: result.append(list(xs)) else: for j in range(i, len(xs)): swap(xs, i, j) permute(xs, i+1) swap(xs, i ,j) return result if __name__ == '__main__': print('example: permute([1,2,3])') print(permute([1,2,3]))