排列組合(permutation)

#include<stdio.h>

#include<string.h>

  

void swap( char *a, char *b )

{ //外部函式，互換元素資料

   char c;

   c=*a;

   *a=*b;

   *b=c;

}

//外部函式，印出所有元素排列

void fun( int a, int b, char element[] )

{

   int k;

   if ( b == 1 )//長度為一時，直接列印。

   {

      printf( "%c\n", element[ a ] );

   }

   else if ( b == 2 )

   {



      // 長度為二時 ，

      // 把之前遞迴的的元素列出，

      // 之後互換末兩位元素

      for ( k = 0; k < a; k++ ) {

         printf( "%c", element[ k ] );

  }  

   printf( "%c%c\n", element[ a ], element[ a + 1 ]);

    

      for ( k = 0 ; k < a; k++ ) {

         printf( "%c", element[ k ] );

  }  

   printf( "%c%c\n", element[ a + 1 ], element[ a ]);

    

   }

   else

   { //當長度大於3時利用下列遞迴

      for ( k = 0 ; k < b; k++)

      {

         //用swap使所有元素都能列於相對的第一位置上

         swap( &element[ a ], &element[ a + k ] );

         //printf( "a = %7d b=%7d\n", a, b );

   fun( a + 1, b - 1, element ); // 之後慢慢遞迴，使之成為simple case

   //printf( "a = %7d b=%7d\n", a, b );

         swap( &element[ a ], &element[ a + k ] ); // 然後再換回來



      }

   }

}





int main( void )

{

   char element[ 11 ]; //宣告變數element

   int len; //宣告變數len

  

 printf("請給定元素，至多10個>");

   scanf( "%s", element );// 把使用者給的值存回element

   len = strlen( element );// 查定element的長度

   //printf( " len = %d ", len );

 fun( 0, len, element);// 外部函數作用開始

   return(0);

}

參考於：網站


------------------------------------------------------------------------------------------------------------------------

版本2:





#include <stdlib.h>

#include <stdio.h>

#include <string.h>




void swap(int *a, int *b)

{

 *a ^= *b;

 *b ^= *a;

 *a ^= *b;

}




void fac(int data[], int num, int idx)

{

 //int *tmp_data, i;

 int i;

 

 // Print all element because we get one of result

 if(idx == (num)){

  int j = 0;

  for(; j < num; ++j) {

   printf("%d ", data[j]);

  }




  printf("\n");




  return;

 }




 fac(data, num, idx + 1);

 

 // Other results

 i = idx + 1;

 for(; i < num; ++i) {

  //printf("fuck\n");

  swap(&data[idx], &data[i]);

  fac(data, num, idx + 1);

  swap(&data[idx], &data[i]);

 }




 //free(tmp_data);

}




int main()

{

 int data[] = {1, 2, 3, 4};

 //int a = 9;

 //swap(&a, &a);

 int num = sizeof(data) / sizeof(int);

 fac(data, num, 0);

 //printf("%d, %d", a, a);

 return 0;

}