Permutations of a list
Find all the permutations of a list. For example, given the list [1,2, 3] compute all of [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1],[3, 1, 2], [3, 2, 1]].
The reasoning here goes like this. Suppose I know how to compute all the permutations of a list that start with the element at position k. Then the list of all permutations can be obtained by calling that function with k = 0, ..., N-1 where N is the length of the list. How do you compute the permutations of a list that start with the element at position k? Well, you compute all the permutations of the reduced list that doesn't contain the kth element and prepend them all with the kth element.
Python
def take(k, lst):
'''The list slice, lst[0:k].
>>> print (str(take(0, [1, 2, 3])))
[]
>>> print (str(take(1, [1, 2, 3])))
[1]
>>> print (str(take(2, [1, 2, 3])))
[1, 2]
>>> print (str(take(3, [1, 2, 3])))
[1, 2, 3]
>>> print (str(take(4, [1, 2, 3])))
[1, 2, 3]
'''
if(k <= 0):
return []
if(len(lst) == 0):
return []
return [lst[0]]+take(k-1, lst[1:])
def drop(k, lst):
'''The list slice, lst[k:].
>>> print (str(drop(0, [1, 2, 3])))
[1, 2, 3]
>>> print (str(drop(1, [1, 2, 3])))
[2, 3]
>>> print (str(drop(2, [1, 2, 3])))
[3]
>>> print (str(drop(3, [1, 2, 3])))
[]
>>> print (str(drop(4, [1, 2, 3])))
[]
'''
if(k <= 0):
return lst
if(len(lst)==0):
return []
return drop(k-1, lst[1:])
def find_all_permutations(lst):
'''Find all permutations of a list.
>>> print (str(find_all_permutations([1, 2, 3])))
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
'''
def find_k_permutations(k, lst):
'''Find all permutations of the given list that start with the
element at index k.
'''
x = lst[k]
listp=take(k, lst)+drop(k+1, lst)
ps=find_all_permutations(listp)
s = list (map (lambda perm : [x] + perm, ps))
return s
def loop(k, acc, lst):
if(k == len(lst)):
return acc
else:
return loop(k+1, acc + find_k_permutations(k, lst), lst)
return ([[]], loop(0, [], lst))[len(lst)!=0]
if __name__ == "__main__":
import doctest
doctest.testmod()
C++
#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
typedef std::vector<int> perm_t;
typedef std::vector<int>::iterator perm_iterator_t;
typedef std::vector<int>::const_iterator perm_const_iterator_t;
typedef std::vector<perm_t> perm_set_t;
typedef std::vector<perm_t>::iterator perm_set_iterator_t;
typedef std::vector<perm_t>::const_iterator perm_set_const_iterator_t;
//-- print functions
void print_perm (perm_t const& s)
{
std::cout << "[";
std::ostream_iterator<int> out_it (std::cout, ", ");
std::copy (s.begin(), s.end(), out_it);
std::cout << "],";
}
void print_perm_set (perm_set_t const& ts)
{
std::cout << "[";
perm_set_const_iterator_t begin=ts.begin (), end = ts.end ();
perm_set_const_iterator_t t=begin;
while (t != end)
{
print_perm (*t);
++t;
}
std::cout << "]";
}
//-- take, drop
perm_t take (int k, perm_t const& lst)
{
if (k <= 0)
{
return perm_t ();
}
if (lst.size() == std::size_t (0))
{
return perm_t ();
}
perm_t t = take (k-1, perm_t (++(lst.begin()), lst.end()));
perm_t res (t.size()+1);
res[0] = lst[0];
for (std::size_t i = 0; i < t.size (); ++i)
res [i+1] = t[i];
return res;
}
perm_t drop (int k, perm_t const& lst)
{
if (k <= 0)
{
return lst;
}
if (lst.size () == 0)
{
return perm_t ();
}
return drop (k - 1, perm_t (++(lst.begin()), lst.end()));
}
//-- helpers
perm_set_t find_all_permutations (perm_t const& lst);
//Prepend x to a perm.
struct prepend
{
int x;
prepend (int x) : x (x)
{}
perm_t operator ()(perm_t const& p) const
{
perm_t r (p.size() + 1);
r[0] = x;
for (std::size_t i = 0; i < p.size(); ++i)
r[i + 1] = p[i];
return r;
}
};
//Find all permutations of the given list that
//start with the element at index k.
perm_set_t find_k_permutations (int k, perm_t const& lst)
{
int x = lst[k];
perm_t left = take (k, lst);
perm_t right = drop (k + 1, lst);
perm_t listp;
std::copy (left.begin(), left.end(), std::back_inserter (listp));
std::copy (right.begin(), right.end(), std::back_inserter (listp));
perm_set_t ps = find_all_permutations (listp);
perm_set_t s;
std::transform (ps.begin(), ps.end(), std::back_inserter(s), prepend (x));
return s;
}
perm_set_t loop (int k, perm_set_t acc, perm_t lst)
{
if (k == lst.size())
return acc;
else
{
perm_set_t t = find_k_permutations (k, lst);
std::copy (t.begin (), t.end (), std::back_inserter (acc));
return loop (k+1, acc, lst);
}
}
perm_set_t find_all_permutations (perm_t const& lst)
{
if (lst.size() == 0)
{
perm_set_t res;
res.push_back (perm_t ());//The empty sequence.
return res;
}
return loop (0, perm_set_t (), lst);
}
//-- test
int main()
{
int data[] = {1, 2, 3};
perm_t input (data, data + sizeof(data)/sizeof(int));
print_perm_set (find_all_permutations (input));
return 0;
}
