Generating Permutations without Recursion: Ord-Smith’s Algorithm

[This page is auto-generated; please prefer to read the article’s PDF Form.]

[Prev] [Up]

Ord-Smith’s Algorithm

void ordsmith_nonrecur()
{
  int I[N-1], s;

  for(s = 0; s < N-1; s++)
    I[s] = 0;

  print();

  s = N-2;

  while(s >= 0)
  {
    if(I[s] < N-s-1)
    {
      I[s]++;

      /* Setup Block */
      REVERSE(s+1, N-1);
      SWAP(s, s+I[s]);

      print();
      s = N-2;
    }
    else
    {
      I[s] = 0;
      s = s-1;
    }
  }
}

■

References

[1] R. Sedgewick. Permutation Generation Methods. ACM Comput. Surv., Vol 9 (2) (1977), 137–164.

[2] Nitin Verma. Generating Permutations with Recursion.
https://mathsanew.com/articles/
permutations_with_recursion.pdf.

[3] Nitin Verma. Maintaining the Stack for Recursion.
https://mathsanew.com/articles/own_stack_for_recursion.pdf.

[Prev] [Up]