Permutations of a list

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;
}