遞推遞歸與排列組合

遞推遞歸與排列組合

說明

排列組合

排列組合問題在暴力枚舉的情況一般有3種情況

我們在此記個數為N

  • 情況一：列印n個數的全排列:
\[N = n!
\]

  • 情況二：列印n個數中任意m個數的全排列
\[N = A_{n}^{m} = \frac{n!}{(n-m)!}
\]

  • 情況三：列印n個數中任意m個數的組合
\[N = C_{n}^{m} = \frac{n!}{m!(n-m)!}
\]

遞推與遞歸

遞推是按照一定的規律來計算序列中的每個項，通常是通過計算前面的一些項來得出序列中的指定項的值。其思想是把一個複雜的龐大的計算過程轉化為簡單過程的多次重複，該演算法利用了電腦速度快和不知疲倦的機器特點。

所謂遞歸，實際上是一種把大問題逐步縮小成最小同類問題的過程，其中最小問題的解是已知的，往往是所給條件。

比較兩者，可清楚的發現遞歸是逆向的遞推。遞推是從最小問題出發一步步向前求解，遞歸則是從最大問題開始不斷去調用自己達到最小問題的解然後再逐層歸來。

所以一般來講遞推的效率大於遞歸，並且在遞歸中問題的n是在計算前就已經知道的，而遞推可以在求解中確定。

我們以斐波那契數列距離，其數學遞推公式如下(無論遞推還是遞歸，一般都從遞推公式開始分析)

\[\begin{cases}f(n) = f(n-1) + f(n-2)
\\f(1) = f(2) = 1
\\n>2,n\in {N}^{+}

\end{cases}
\]

接下來我們利用程式碼來分別示範一遍兩種方法

  • 斐波那契——遞歸
#include <iostream>
#include <ctime>

using namespace std;
//由於數列發散快，使用int類型當n較大時可能會溢出，此處僅為舉例
int func_fib(unsigned int n)
{
    if(n==0)    //儘管遞推公式給出n不會等於零，但為了以防萬一添加了n為0的情況
        return 0;
    if(n==1 || n==2)
        return 1;
    else
        return func_fib(n-1) + func_fib(n-2);
}

int main()
{
    unsigned int n = 0;
    cout << "請輸入所求斐波那契數列項的項數n: " << endl;
    cin >> n;
    
    //輸出結果和所用時間，單位：時鐘單位
    clock_t start,end;
    start = clock();    //開始
    cout << func_fib(n) << endl;
    end = clock();      //結束
    cout << "計算所用時間為: " << (double)(end-start) << endl;
    
    return 0;
}
  • 斐波那契——遞推
#include <iostream>
#include <ctime>

using namespace std;

//同樣，n過大會溢出
int func_fib(unsigned n)
{
    int fib = 0;
    int fib_n = 1;
    for(int i=0; i<n; i++)
    {
        int temp = fib_n;
        fib_n = fib + fib_n;
        fib = temp;
    }
    return fib;
}

int main()
{
    cout << "請輸入所求斐波那契數列項的項數n: " << endl;
    unsigned int n;
    cin >> n;
    
    //輸出結果和所用時間
    clock_t start,end;
    start = clock();    //開始
    cout << func_fib(n) << endl;
    end = clock();      //結束
    cout << "計算所用時間為:" << (double)(end-start) << endl;
    
    return 0;
}

演算法

我們對上述排列組合對三種情況寫程式碼

情況一

輸出全排列

STL方法：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

//輸出序列
void printSequence(vector<int> num)
{
    vector<int>::iterator it;   //迭代器
    cout << "當前序列: ";
    //遍歷
    for(it=num.begin(); it!=num.end(); it++)
        cout << *it << " ";
    cout << endl;
}

int main()
{
    /*
     * 注意，使用sort()與alogrithm需要包含algorithm頭文件
     */
    
    //初始化序列
    vector<int> num{2,1,5,3,4};
    //排序（正序）
    sort(num.begin(), num.end());
    //輸出全排列
    do{
        printSequence(num);
    }while(next_permutation(num.begin(), num.end()));
    
    return 0;
}

遞歸方法:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void printSequence(vector<int> num)
{
    vector<int>::iterator it;   //迭代器
    cout << "當前序列: ";
    //遍歷
    for(it=num.begin(); it!=num.end(); it++)
        cout << *it << " ";
    cout << endl;
}

/*
 *這裡num必須用引用。
 *否則迭代器指向的num是原實例，而傳入的num是拷貝的實例，輸出結果都是原序列。
 *詳細情況可以調用下方的test嘗試下(該函數已被注釋)
 */
void Perm(vector<int> &num, vector<int>::iterator begin, vector<int>::iterator end)
{
    if(begin == end-1)
        printSequence(num); //列印，此處還可以統計個數
    else{
        vector<int>::iterator it;
        for(it=begin; it<end; it++)
        {
            swap(*begin, *it);
            Perm(num, begin+1, end);
            swap(*begin, *it);
        }
    }
}

//void test(vector<int> num, vector<int>::iterator it)
//{
//    num[0] = 10;
//    cout << *it << " " << num[0] << endl;
//}

int main()
{
    vector<int> num{1,2,3};
    Perm(num, num.begin(), num.end());
    
    return 0;
}

情況二

想要列印n個數中任意m個數的全排列其實很簡單，只需要在上述程式碼中稍作修改即可

列印序列函數printSequence

void printSequence(vector<int> num, vector<int>::iterator begin, vector<int>::iterator end)
{
	vector<int>::iterator it;   //迭代器
	cout << "當前序列: ";
	//遍歷
	for (it = begin; it != end; it++)
		cout << *it << " ";
	cout << endl;
}

獲取全排列的函數Perm(增加了計數功能，需傳入變數cnt)

/*
 *這裡num必須用引用。
 *否則迭代器指向的num是原實例，而傳入的num是拷貝的實例，輸出結果都是原序列。
 *詳細情況可以調用下方的test嘗試下(該函數已被注釋)
 *參數：num：原序列，begin：vector的begin迭代器， end：vector的end迭代器，m:從n個數中列印m個數的全排列中的m，cnt：用於統計最後全排列個數
 */
void Perm(vector<int>& num, vector<int>::iterator begin, vector<int>::iterator end, unsigned int m, int &cnt)
{
	if (begin == num.begin() + m)
	{
		printSequence(num, num.begin(), num.begin() + m); //列印
		++cnt;	//統計個數
	}
	else {
		vector<int>::iterator it;
		for (it = begin; it < end; it++)
		{
			swap(*begin, *it);
			Perm(num, begin + 1, end, m, cnt);
			swap(*begin, *it);
		}
	}
}

情況三

組合不同於排列，排列有序而組合無序。所以，我們先來研究其子集的生成。

我們按如下記集合A，其中n為其元素的個數

\[A = \left \{ x_0,x_1,x_2,…,x_{n-1} \right \}
\]

其子集有

\[\phi ,\left \{ x_0 \right \} ,\left \{ x_1 \right \},…,\left \{ x_0,x_1,…,x_{n-1}\right \}
\]

不妨設子集個數為N，則有

\[N = 2^{n}
\]

這個式子很容易跟二進位聯繫起來，我們不由得會去想子集跟二進位之間的關係

我們不妨構造一個n位的二進位數，每一位都對應集合中的一個元素，當子集中包含該元素，則對應的二進位數的該位上的值就為1否則為0，那麼每個子集都對應一個獨一無二的n位二進位數了。

以n=3時的集合為例，此時有

\[A = \left \{ x_0,x_1,x_2 \right \}
\]

則其子集與二進位數對應關係如下

子集 空集 x0 x1 x0,x1 x2 x2,x0 x2,x1 x2,x1,x0
二進位數 000 001 010 011 100 101 110 111

此外我們還需要知道:

  • 位運算
1<<n	//該位運算等價於2的n次冪
  • 與運算
\[10001 \& 101 = 10001 \& 00101 = 00001
\]

此處與運算僅舉例，當兩個二進位數位數不一致則再前面補0然後對應位置做與運算

接下來我們以列印集合{0,1,2,..,n-1}的子集為例，則有如下函數

void print_subset(int n)
{
	for (int i = 0; i < (1 << n); i++)	//從000到2^n-1對應的二進位，一共2^n個子集
	{
		//將每個子集都取出，對應數字i
		//在子集i的情況下，不斷嘗試取元素個數為j，其中每個元素的值跟其序號相同都為j
		for (int j = 0; j < n; j++)	//如果子集i中含多個數，此處的for則列印多個數，若i僅1個數此處for也只尋找並列印僅含的這一個數j
			if (i & (1 << j))		//將2的j次冪轉化為二進位形式，通過與運算，去測試僅包含一個十進位數j的集合是不是該子集的子集
				cout << j << " ";	//如果是，則說明子集i中包含十進位數j，此時列印j。
		cout << endl;
	}
}

那麼基礎知識已經介紹完了，我們回到情況三，對照子集對應二進位數的方法。我們知道一個子集對應唯一的一個二進位數，那麼一個有k個元素的子集它對應二進位數一定有k個1。所以找查子集的問題就變成了找查含k個1的二進位數。

這裡介紹個技巧(kk為一個名為kk的二進位數)

kk = kk & (kk-1)

它可以跳過0消除數中最後一個1，這樣我們執行此操作的次數就是二進位數中含1的個數

則針對情況三有如下程式碼

//列印n個數中取m個數的組合
void print_set(int n, int m)
{
	for (int i = 0; i < (1 << n); i++)
	{
		int cnt = 0, kk = i;
		while (kk)
		{
			kk = kk & (kk - 1);
			cnt++;
		}
		if (cnt == m)
		{
			for (int j = 0; j < n; j++)	//此處跟上方print_subset函數同理
				if (i & (1 << j))
					cout << j << " ";
			cout << endl;
		}
	}
}

參考

  • 羅永軍,郭衛斌. 演算法競賽入門到進階[M]. 北京 : 清華大學出版社,2019.
Tags:

VirMach 便宜 VPS

QNews

QNews