Permutations 列舉

Permutations

  

A permutation of a given set of items is a certain rearrangement of the elements. It can be shown that an array  of length  has  permutations. For example the array ['J','O','N'] has the following permutations:

1 2 3 4 5 6

['J', 'O', 'N'] ['J', 'N', 'O'] ['O', 'J', 'N'] ['O', 'N', 'J'] ['N', 'J', 'O'] ['N', 'O', 'J']

The backtracking algorithm applied here is fairly straight forward because the calls are not subject to any constraint. We are not backtracking from an unwanted result we are merely backtracking to return to a previous state without filtering out unwanted output. This is a elaborated a little bit more in the picture and code below:

diag

As shown in the diagram the algorithm is based on swapping. When implemented, the backtracking part is swapping back the items to their previous place after the permutation has been printed.

The following python code shows how this is done:

1 2 3 4 5 6 7 8 9 10 11

def permutation( list , start , end ): '''This prints all the permutations of a given list it takes the list,the starting and ending indices as input''' if (start == end ): print list else: for i in range(start , end + 1): list[a] , list[b] = list[b] , list[a] #The swapping swap( list , start , i ) permutation( list , start + 1 , end ) swap( list , start , i ) #Backtracking

# permutations 列舉法
import itertools
print (list(itertools.permutations([1,2,3,4], 2)))
print (list(itertools.permutations(['j','o','h','n'], 2)))
print (list(itertools.permutations(['j','o','n'], 3)))

=========== RESTART: F:/Python_APSC/b038-2.py ==============
[(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]
[('j', 'o'), ('j', 'h'), ('j', 'n'), ('o', 'j'), ('o', 'h'), ('o', 'n'), ('h', 'j'), ('h', 'o'), ('h', 'n'), ('n', 'j'), ('n', 'o'), ('n', 'h')]
[('j', 'o', 'n'), ('j', 'n', 'o'), ('o', 'j', 'n'), ('o', 'n', 'j'), ('n', 'j', 'o'), ('n', 'o', 'j')]
>>>