#=======================================================================
# Author: Isai Damier
# Title: Permutation
# Project: geekviewpoint
# Package: algorithms
#
# Statement:
# Returns a list of all the permutations of the given set
#
# Sample Input: [1,2,3]
# Sample Output: [1,2,3]; [1,3,2]; [2,1,3]; [2,3,1]; [3,1,2]; [3,2,1]
#
# Description:
#
# Technical Details:
# One way of verifying the correctness of the result is to count the
# number of permutations returned. From arithmetics, we know that the
# number of permutations for a set is equal to the factorial of the
# size of the set: 3! = 6.
#
# This recursive algorithm is usually referred to as Heap's
# permutation, in honor of B. R. Heap.
#
# If a programmer simply wishes to print the permutations instead of
# returning them in a list, [code 2] should replace [code 1] below.
#
# [code 1]:
# if(1 == n)
# factorials.add(Arrays.copyOf(list, list.length));
#
# [code 2]:
# if 1 == n:
# for i in aList
# print("%s, ") % i
#
#=======================================================================
def permutation( aList ):
factorials = []
_permutation( aList, len( aList ), factorials )
return factorials
def _permutation( aList, n, factorials ):
if 1 == n:
factorials.append( list( aList ) )
else:
for i in range( n ):
_permutation( aList, n - 1, factorials )
if 0 == n % 2:
swap( aList, 0, n - 1 )
else:
swap( aList, i, n - 1 )
def swap( aList, x, y ):
t = aList[x]
aList[x] = aList[y]
aList[y] = t
import unittest
from algorithms import numbers as algorithm
class Test( unittest.TestCase ):
def testPermutation( self ):
expected = [[1, 2, 3], [2, 1, 3], [3, 2, 1], [2, 3, 1], [3, 1, 2],
[1, 3, 2]]
result = algorithm.permutation( [1, 2, 3] )
self.assertEquals( expected, result )
