Как бы вы вычислили все возможные перестановки от 0 до N итеративно?

Можно ли использовать перестановку массива 1.9 в версии 1.9?

>> 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]]

Алгоритм перехода от одной перестановки к другой очень похож на сложение в начальной школе - когда происходит переполнение, «несите одну».

Вот реализация, которую я написал на 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;
}

Я использовал алгоритмы из здесь . На странице много полезной информации.

Править : Извините, они были рекурсивными. Урай опубликовал в своем ответе ссылку на итерационный алгоритм.

Я создал пример PHP. Если вам действительно не нужно возвращать все результаты, я бы создал только итеративный класс, подобный следующему:

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

Обратите внимание, что он обрабатывает каждый массив PHP как индексированный массив.