How would you calculate all possible permutations of 0 through N iteratively?

Question

I need to calculate permutations iteratively. The method signature looks like:

int[][] permute(int n)

For n = 3 for example, the return value would be:

[[0,1,2],
 [0,2,1],
 [1,0,2],
 [1,2,0],
 [2,0,1],
 [2,1,0]]

How would you go about doing this iteratively in the most efficient way possible? I can do this recursively, but I'm interested in seeing lots of alternate ways to doing it iteratively.

Answer 1

I've used the algorithms from here. The page contains a lot of useful information.

Edit: Sorry, those were recursive. uray posted the link to the iterative algorithm in his answer.

I've created a PHP example. Unless you really need to return all of the results, I would only create an iterative class like the following:

<?php
class Permutator implements Iterator
{
  private $a, $n, $p, $i, $j, $k;
  private $stop;

  public function __construct(array $a)
  {
    $this->a = array_values($a);
    $this->n = count($this->a);
  }

  public function current()
  {
    return $this->a;
  }

  public function next()
  {
    ++$this->k;
    while ($this->i < $this->n)
    {
      if ($this->p[$this->i] < $this->i)
      {
        $this->j = ($this->i % 2) * $this->p[$this->i];

        $tmp = $this->a[$this->j];
        $this->a[$this->j] = $this->a[$this->i];
        $this->a[$this->i] = $tmp;

        $this->p[$this->i]++;
        $this->i = 1;
        return;
      }

      $this->p[$this->i++] = 0;
    }

    $this->stop = true;
  }

  public function key()
  {
    return $this->k;
  }

  public function valid()
  {
    return !$this->stop;
  }

  public function rewind()
  {
    if ($this->n) $this->p = array_fill(0, $this->n, 0);
    $this->stop = $this->n == 0;
    $this->i = 1;
    $this->j = 0;
    $this->k = 0;
  }

}

foreach (new Permutator(array(1,2,3,4,5)) as $permutation)
{
  var_dump($permutation);
}
?>

Note that it treats every PHP array as an indexed array.

Answer 2

The algorithm for stepping from one permutation to the next is very similar to elementary school addition - when an overflow occurs, "carry the one".

Here's an implementation I wrote in C:

#include <stdio.h>

//Convenience macro.  Its function should be obvious.
#define swap(a,b) do { \
        typeof(a) __tmp = (a); \
        (a) = (b); \
        (b) = __tmp; \
    } while(0)

void perm_start(unsigned int n[], unsigned int count) {
    unsigned int i;
    for (i=0; i<count; i++)
        n[i] = i;
}

//Returns 0 on wraparound
int perm_next(unsigned int n[], unsigned int count) {
    unsigned int tail, i, j;

    if (count <= 1)
        return 0;

    /* Find all terms at the end that are in reverse order.
       Example: 0 3 (5 4 2 1) (i becomes 2) */
    for (i=count-1; i>0 && n[i-1] >= n[i]; i--);
    tail = i;

    if (tail > 0) {
        /* Find the last item from the tail set greater than
            the last item from the head set, and swap them.
            Example: 0 3* (5 4* 2 1)
            Becomes: 0 4* (5 3* 2 1) */
        for (j=count-1; j>tail && n[j] <= n[tail-1]; j--);

        swap(n[tail-1], n[j]);
    }

    /* Reverse the tail set's order */
    for (i=tail, j=count-1; i<j; i++, j--)
        swap(n[i], n[j]);

    /* If the entire list was in reverse order, tail will be zero. */
    return (tail != 0);
}

int main(void)
{
    #define N 3
    unsigned int perm[N];

    perm_start(perm, N);
    do {
        int i;
        for (i = 0; i < N; i++)
            printf("%d ", perm[i]);
        printf("\n");
    } while (perm_next(perm, N));

    return 0;
}

Answer 3

see QuickPerm algorithm, it's iterative : http://www.freewebs.com/permute/quickperm.html

Edit:

Rewritten in Ruby for clarity:

def permute_map(n)
  results = []
  a, p = (0...n).to_a, [0] * n
  i, j = 0, 0
  i = 1
  results << yield(a)
  while i < n
    if p[i] < i
      j = i % 2 * p[i] # If i is odd, then j = p[i], else j = 0
      a[j], a[i] = a[i], a[j] # Swap
      results << yield(a)
      p[i] += 1
      i = 1
    else
      p[i] = 0
      i += 1
    end
  end
  return results
end

Answer 4

Is using 1.9's Array#permutation an option?

>> a = [0,1,2].permutation(3).to_a
=> [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]