1.什麼是排列?
排列的任務是確定個不同的元素的排序的可能性。從下邊的示意圖可看出,3個不同顏色的彩球一共有6種不同的排列方式,因此有如下定理:“個不同的元素可以有種不同的排列方式,即的階乘。”因此上面的例子的算法是3 ! = 6。
為什麼是3的階乘呢?因為第一個位置有3種顏色可選,除去第一個位置,第二個位置就只有2種顏色可選了,確定好第一位置和第二個位置,第三個位置自動就確定下來了,故一共有3*2*1種可能就是3的階乘,6種可能。
2.計算機中的C++實現
這個其實是一個蠻難的問題,最普遍的是用遞歸實現,不過遞歸效率比較低。
// Perm.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using
namespace
std;
template
<
class
T>
inline
void
Swap(T& a, T& b)
{
// 交換a和b
T temp = a; a = b; b = temp;
}
template
<
class
T>
void
Perm(T list[],
int
k,
int
m)
{
//生成list [k:m ]的所有排列方式
int
i;
if
(k == m) {
//輸出一個排列方式
for
(i = 0; i <= m; i++)
cout << list [i];
cout << endl;
}
else
// 每次交換產生一個新排列
for
(i=k; i <= m; i++) {
Swap (list[k], list[i]);
Perm (list, k+1, m);
Swap (list[k], list[i]);
}
}
int
_tmain(
int
argc, _TCHAR* argv[])
{
int
a[3] = {1, 2, 3};
Perm(a,0,2);
system
(
"pause"
);
return
0;
}
結果如下:
老實說,這樣寫是能出結果,但是可能是我腦子不好使,竟然看不懂,遞歸的代碼特別不容易看懂。後面很努力地看了下,解釋如下:
數學中我們知道求1,2,3的排列,第一個位置有3中可能,即1,2,或者3。給人的感覺是物理的感覺,從1,2,3中,每次取一個。這樣在計算機中很難表達,在計算機中,有個簡便的處理手段,就是交換,跟自己包括後面所有的數交換一次就行了,即得到
1,2,3; // 1 跟 1交換
2,1,3; // 1 跟 2 交換 (又是從1,2,3開始,所以每次交換完都要交換回去,復原)
3,2,1 ;// 1 跟 3 交換 (又是從1,2,3開始,所以每次交換完都要交換回去,復原)
上面的代碼又有這樣的意思:總共的可能又變成 1 + (2, 3)的排列,2 + (1, 3)的排列, 3 + (2, 1)的排列。 那如何求 2,3的排列呢? 又是交換,2跟2交換,2跟3交換。 1,3 和 2,1是同樣道理。
這樣一共是3 * 2 共 6 種可能。
3.stl中的next_permutation
遞歸的效率是很低的,我們注意到Stl中有個叫next_permutation的函數,它可以返回下一個值,比如1,2,3。 它會返回1,3,2。1,3,2 究竟是什麼意思?它是怎麼實現的呢?
舉例一個較長的數組吧,1,5,4,7,6,3。 我們把它看成一個六位數,就是154763。 那麼下一個值,由1,3,4,5,6,7 這 6個數字組成且比 154763 大,那麼就是156347。然後再求156347的下一個值就是156374,不斷往下求,也能得到所有的排列組合。
1,2,3 就是: 123 < 132 < 213 < 231 < 312 < 321。