Here is an unoptimized example using python to illustrate an algorithm
that is easy to understand.
# recursive function, li contains a list
def perm(li):
# anything to do? (recursive termination test)
if li:
# iteration scratchpad to construct lists to return
temp=[]
# create an index number for each item in the list, and loop
through each index
for i in range(len(li)):
# (this is where the magic happens) generate permutations for each
# combination that does not include the current index number
for l in perm(li[:i]+li[i+1:]):
# concatenate index item to each of the combinations
temp.append([li[i]]+l)
# return lists when above is complete for each index
return temp
return [[]] # terminal case
the harder to read implementation of the same algorithm in python is
def perm(li):
if li:
return [[li[i]]+l for i in range(len(li)) for l in perm(li[:i]+li[i+1:])]
return [[]]
Sample values:
>>> perm([0,1,2,3])
[[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2],
[0, 3, 2, 1], [1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0],
[1, 3, 0, 2], [1, 3, 2, 0], [2, 0, 1, 3], [2, 0, 3, 1], [2, 1, 0, 3],
[2, 1, 3, 0], [2, 3, 0, 1], [2, 3, 1, 0], [3, 0, 1, 2], [3, 0, 2, 1],
[3, 1, 0, 2], [3, 1, 2, 0], [3, 2, 0, 1], [3, 2, 1, 0]]
>>> perm(range(3))
[[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
>>> perm(['x','y','z'])
[['x', 'y', 'z'], ['x', 'z', 'y'], ['y', 'x', 'z'], ['y', 'z', 'x'],
['z', 'x', 'y'], ['z', 'y', 'x']]
This example was just meant to illustrate an easily understood
algorithm to do it. Hopefully you can follow the logic okay in the
first example.
~ Daniel
-----------------------------------------------------------------------
This list is provided as an unmoderated internet service by Networked
Knowledge Systems (NKS). Views and opinions expressed in messages
posted are those of the author and do not necessarily reflect the
official policy or position of NKS or any of its employees.
This archive was generated by hypermail 2.1.3 : Fri Aug 01 2014 - 20:37:07 EDT