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;
}