程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> C++全排列原理算法解析(百度迅雷筆試題)(五)

C++全排列原理算法解析(百度迅雷筆試題)(五)

編輯：C++入門知識

為什麼要接觸全排列

全排列在筆試面試中很熱門，因為它難度適中，既可以考察遞歸實現，又能進一步考察非遞歸的實現，便於區分出考生的水平。所以在百度和迅雷的校園招聘以及程序員和軟件設計師的考試中都考到了，因此本文對全排列作下總結幫助大家更好的學習和理解。對本文有任何補充之處，歡迎大家指出。

全排列原理解析

全排列是將一組數按一定順序進行排列，如果這組數有n個，那麼全排列數為n!個。待會以{1, 2, 3, 4, 5}為例說明如何編寫全排列的遞歸算法。

全排列算法解析

首先來看看題目是如何要求的（百度迅雷校招筆試題）。

用C++寫一個函數, 如 Foo(const char *str), 打印出 str 的全排列,
如 abc 的全排列: abc, acb, bca, dac, cab, cba

為方便起見，用123來示例下。123的全排列有123、132、213、231、312、321這六種。首先考慮213和321這二個數是如何得出的。顯然這二個都是123中的1與後面兩數交換得到的。然後可以將123的第二個數和每三個數交換得到132。同理可以根據213和321來得231和312。因此可以知道——全排列就是從第一個數字起每個數分別與它後面的數字交換。

根據上面的規律和算法分析以後來給出簡易代碼（貌似不太復雜，卻我感覺很繞，建議多DEBUG，因為我也是這樣分析的！）

#include 
using namespace std;

int n = 0;  

void cout1(int list[])
{
	for (int c = 0; c<=1; c++)
	{
		printf("%d ", list[c]);  
	}
	printf("\n");
}
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)   //k=0 m=1  ---1  :k =1:  k=2: 
	{          
		for(i = 0; i <= m; i++)              
			printf("%d ", list[i]);          
		printf("\n");         
		n++;     
	}     
	else     
	{         
		for(i = k; i <= m; i++)    //k=0,m=1 --1 :k =i =1:
		{             
			swap(&list[k], &list[i]);  
			// cout1(list);
			perm(list, k + 1, m);   //m =k =1:
			//1
			swap(&list[k], &list[i]);         
		}     
	} 
} 
int main() 
{     
	int list[] = {1, 2,3 };     
	perm(list, 0, 2);     
	printf("total:%d\n", n); 
	system("pause");
	return 0; 
}

運行效果如下：