Principle and implementation code of the whole permutation algorithm

A full permutation is a set of Numbers arranged in a certain order. If there are n of them, then the total permutation is n! A. This paper takes {1, 2, 3, 4, 5} as an example to illustrate how to write a recursive algorithm for all permutations.

1. First look at the last two Numbers, 4 and 5. They have a total permutation of 4, 5, and 5, 4, which is the total permutation of 5 starting with 4 and the total permutation of 4 starting with 5.

Since the whole arrangement of a number is itself, we get the above result.

2. Look at the last three Numbers: 3, 4, 5. The full order of them is 3, 4, 5, 3, 5, 4, 3, 5, 4, 5, 4, 5, 5, 3, 5, 3, 5, 4, 4, 3.

It's a combination of all permutations starting with 3 and 4 and 5, all permutations starting with 4 and 3 and 5 and all permutations starting with 5 and 3 and 4.

Thus, it can be inferred that p = {r1, r2, r3... Rn}, perm(p), pn = p - {rn}.

Therefore, perm(p) = r1perm(p1), r2perm(p2), r3perm(p3)... , rnperm (pn). When n = 1, perm of p} = r1.

To make it easier to understand, all the Numbers in the whole set are swapped with the first number, so that the full array of n-1 Numbers is always processed.

The algorithm is as follows:

#include <stdio.h> 

int n = 0; 

void swap(int *a, int *b) 
{   
  int m;   
  m = *a;   
  *a = *b;   
  *b = m; 
} 
void perm(int list[], int k, int m) 
{   
  int i;   
  if(k > m)   
  {     
    for(i = 0; i <= m; i++)       
      printf("%d ", list[i]);     
    printf("n");     
    n++;   
  }   
  else   
  {     
    for(i = k; i <= m; i++)     
    {       
      swap(&list[k], &list[i]);       
      perm(list, k + 1, m);       
      swap(&list[k], &list[i]);     
    }   
  } 
} 
int main() 
{   
  int list[] = {1, 2, 3, 4, 5};   
  perm(list, 0, 4);   
  printf("total:%dn", n);   
  return 0; 
}

Who has more efficient recursive and non-recursive algorithms, please post back.