递归与分治－－排列问题

本程序主要是将一个数组中的元素进行全排列。其递归定义如下：
当n=1时，Perm(R) = (r)，其中r是集合R中惟一的元素。
当n>1时，Perm(R)由(r1)Perm(R1)...(rn)Perm(Rn)构成。



#include

#define LEN 4

/* output the array */
void pfarr( const int arr[], const int len )
{
  int i = 0;
  for (i=0; i    {
      printf( "%d ", arr[i] );
    }
  printf( "\n" );
}

void swap( int arr[], int i, int j )
{
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}


void Perm( int arr[], const int len, int index )
{
  int i = 0;
 
  if (index == len)
    {
      pfarr( arr, len );
    }
  else
    {
      for (i=index; i    {
      swap( arr, i, index );
      Perm( arr, len, index+1 );
      swap( arr, i, index );
    }
     
    }
}

int main(int argc, char * argv[])
{
  int arr[LEN];
  int i = 0;
  for (i=0; i    {
      arr[i] = i+1;
    }
 
  Perm( arr, LEN, 0 );

  return 0;
}