C++全排列：一種新的全排列方法（使用單向連結清單實作）

一種使用單向連結清單實作的全排列方法。

通過一個極簡版的單向連結清單，實作全排列，并能指定輸出特定一種排列情況。

代碼示例為“對 A B C D E F ……”進行全排列，可以在此基礎之上擴充為其它全排列應用。

實作代碼：

//chain.h
//添加函數 int factorialFun(int n);
//添加函數 int * outRangeIndex(int row);
//連結清單節點
struct node
{
	int data;
	node * next;
	node(int a):data(a),next(NULL){}
};
//連結清單
class chain
{
public:
	int lengthChain;
	node * nodeHead;
	chain():lengthChain(0),nodeHead(NULL){}
	chain(const chain &c)//複制構造函數
	{
		lengthChain = c.lengthChain;
		if (c.nodeHead != NULL)
		{
			node * pHc = c.nodeHead;
			nodeHead = new node(pHc->data);
			pHc = pHc->next;

			node * pH = nodeHead;
			while (pHc != NULL)
			{
				pH->next = new node(pHc->data);
				pH = pH->next;
				pHc = pHc->next;
			}
		}
		else
			nodeHead = NULL;
	}
	~chain()
	{
		if (nodeHead != NULL)
		{
			node * pH = nodeHead;
			nodeHead = NULL;
			while (pH != NULL)
			{
				node * pDel = pH;
				pH = pH->next;
				delete pDel;
			}
		}
	}
	void addNode(int a);
	int delNode(int index);//删除索引為 index 的資料
	void showNode();

	int factorialFun(int n);
	int * outRangeIndex(int row);
};
           

//chain.cpp
//添加函數 int factorialFun(int n);
//添加函數 int * outRangeIndex(int row);
#include <iostream>
#include "chain.h"

//添加資料
void chain::addNode(int a)
{
	node * p = new node(a);

	if (nodeHead == NULL || nodeHead->data >= a)//從小到大排序
	{
		p->next = nodeHead;
		nodeHead = p;
	} 
	else
	{
		node * pH = nodeHead;
		while (pH->next != NULL && pH->next->data < a)//從小到大排序
			pH = pH->next;
		p->next = pH->next;
		pH->next = p;
	}
	lengthChain++;
	return;
}
//删除索引為 index 的資料
int chain::delNode(int index)
{
	if (lengthChain <= 0 || index >= lengthChain || index < 0)
		return -1;

	int res;//傳回值，删除的資料
	if (index == 0)
	{
		node * pDel = nodeHead;
		nodeHead = nodeHead->next;
		res = pDel->data;
		delete pDel;
	}
	else
	{
		node * pH = nodeHead;
		while (index > 1)//這裡需要 >1，因為要得到前面的那個節點的指針
		{
			pH = pH->next;
			index--;
		}
		node * pDel = pH->next;
		pH->next = pH->next->next;
		res = pDel->data;
		delete pDel;
	}
	lengthChain--;
	return res;
}
//顯示連結清單
void chain::showNode()
{
	using namespace std;
	if (nodeHead != NULL)
	{
		node * pH = nodeHead;
		while (pH != NULL)
		{
			cout << " " << pH->data;
			pH = pH->next;
		}
		cout << endl;
		cout << "lengthChain == " << lengthChain << endl;
	}
	else
		cout << "This chain is empty!" << endl;
	return;
}
//階乘
int chain::factorialFun(int n)
{
	if (n <= 0)
		return 1;
	return n * factorialFun(n-1);
}
//輸出指定全排列，外部需要 delete
int * chain::outRangeIndex(int row)
{
	int nMax = lengthChain;
	int * rangeOut = new int[nMax];
	int maxRow = factorialFun(nMax);
	if (row < 0)
		row = 0;
	else if (row >= maxRow)
		row = maxRow - 1;

	int index;
	for (int i = nMax-1; i >= 0; i--)
	{
		int factorial = factorialFun(i);
		index = row / factorial;
		rangeOut[nMax-1-i] = delNode(index);
		row = row % factorial;
	}

	return rangeOut;
}
           

//4_1_allRange_1
#include <iostream>
#include "chain.h"

int main()
{
	using namespace std;
	int n;
	cin >> n;//輸入要全排列的資料 個數 <=26

	char * ch = new char[n];
	for (int i = 0; i < n; i++)
		ch[i] = 65 + i;//輸入要全排列的資料，從 A 開始，A B C D E F ……

	chain c;//全排列的映射連結清單
	for (int i = 0; i < n; i++)
		c.addNode(i);


	//隻顯示一個特定的全排列 索引 rowIndex
	int rowIndex;
	cin >> rowIndex;
	chain d = c;//調用複制構造函數
	int * rangeOutD = d.outRangeIndex(rowIndex);
	for (int i = 0; i < n; i++)
		cout << " " << ch[rangeOutD[i]];//輸出要全排列的資料
	cout  << endl;
	delete [] rangeOutD;

	//顯示所有的全排列
	int kMax = c.factorialFun(n);//全排列 總數
	for (int k = 0; k < kMax; k++)
	{
		chain e = c;//調用複制構造函數
		int * rangeOut = e.outRangeIndex(k);
		for (int i = 0; i < n; i++)
			cout << " " << ch[rangeOut[i]];//輸出要全排列的資料
		cout  << endl;
		delete [] rangeOut;
	}

	delete [] ch;
	return 0;
}
           

還有一種通過遞歸的方法實作全排列，不過這種方法不友善輸出全排列當中某個特定排列的情況。

遞歸實作全排列代碼如下：

//allRange.h
class allRange
{
public:
	int lengthAllR;
	int step;
	int * allR;
	int * book;
	allRange():lengthAllR(0),step(0),allR(NULL),book(NULL){}
	allRange(int l)
	{
		if (l <= 0)
		{
			lengthAllR = 0;
			step = 0;
			allR = NULL;
			book = NULL;
		}
		else
		{
			lengthAllR = l;
			step = 0;
			allR = new int[lengthAllR];
			book = new int[lengthAllR];
			for (int i = 0; i < lengthAllR; i++)
			{
				allR[i] = -1;
				book[i] = 0;
			}
		}
	}
	allRange(const allRange &aR)
	{
		lengthAllR = aR.lengthAllR;
		step = aR.step;
		if (lengthAllR <= 0)
		{
			allR = NULL;
			book = NULL;
		}
		else
		{
			allR = new int[lengthAllR];
			book = new int[lengthAllR];
			for (int i = 0; i < lengthAllR; i++)
			{
				allR[i] = aR.allR[i];
				book[i] = aR.book[i];
			}
		}
	}
	~allRange()
	{
		if (allR != NULL)
		{
			delete [] allR;
			allR = NULL;
		}
		if (book != NULL)
		{
			delete [] book;
			book = NULL;
		}
	}

	void allRangeFun();
};
           

//allRange.cpp
#include <iostream>
#include "allRange.h"

//全排列算法
void allRange::allRangeFun()
{
	using namespace std;
	if (lengthAllR <= 0)
		return;

	if (step >= lengthAllR)
	{
		for (int i = 0; i < lengthAllR-1; i++)
			cout << allR[i] << " ";
		cout << allR[lengthAllR-1] << endl;
		return;
	}

	for (int i = 0; i < lengthAllR; i++)
	{
		if (book[i] == 0)
		{
			allR[step] = i;
			book[i] = 1;
			step++;
			allRangeFun();
			step--;
			book[i] = 0;
			allR[step] = -1;
		}
	}

	return;
}