学步园

排列算法

从集合S(n)中，任取k(k≤n)个元素，按照一定的顺序(有序性)排成一列，叫做集合S的一个k-排列。
从集合S(n)中，取出的k-排列的总个数，叫做集合S的k-排列数。

排列符号：

这里介绍3种排列形式：
1.全排列。
2.不重复全排列。
3.选择排列。

1.全排列

从集合S(n)中，取出的所有的n-排列。规模数为nPn = n!。

1)交换_递归

代码中调用的函数Swap，功能为：交换两个元素

//交换 递归
//p:表示递归到第p层
typedef char ElemType;
void _full_prem_swap_recursion(ElemType *A, int N, int p)
{
	static int count = 1;
	if (p == N)
	{
		cout<<"["<<count<<"\t] = ";
		for (int i = 0; i < N; ++i)
		{
			cout<<A[i]<<" ";
		}
		cout<<endl;
		count++;
		return;
	}

	for (int i = p; i < N; ++i)
	{
		Swap(A[i], A[p]);//交换
		_full_prem_swap_recursion(A, N, p + 1);
		Swap(A[i], A[p]);//恢复
	}
}
void full_prem_swap_recursion(ElemType *A, int N)
{
	_full_prem_swap_recursion(A, N, 0);
}

输入：A B C

输出：

2)选择_递归

typedef char ElemType;

typedef struct stElemNode
{
	ElemType value;
	unsigned char num;
} ElemTypeEx;

template< class T > void SafeDelete( T*& pVal )
{
	delete pVal;
	pVal = NULL;
}

template< class T > void SafeDeleteArray( T*& pVal )
{
	delete[] pVal;
	pVal = NULL;
}

//全排列
//选择递归
void _full_prem_select_recursion(ElemTypeEx *A, int N, ElemType *choosed, int p)
{
	static int count = 1;
	if (p == N)
	{
		cout<<"["<<count<<"\t] = ";
		for (int i = 0; i < N; ++i)
		{
			cout<<choosed[i]<<" ";
		}
		cout<<endl;
		count++;
		return;
	}

	for (int i = 0; i < N; ++i)
	{
		if (A[i].num > 0)
		{
			--A[i].num; //可用次数减1
			choosed[p] = A[i].value;
			_full_prem_select_recursion(A, N, choosed, p+1); 
			++A[i].num; //可用次数恢复
		}
	}
}

void full_prem_select_recursion(const ElemType *A, int N)
{
	ElemTypeEx *A_Ex = new ElemTypeEx[N];

	for (int i = 0; i < N; ++i)
	{
		A_Ex[i].value = A[i];
		A_Ex[i].num = 1;
	}

	ElemType *choosed = new ElemType[N];

	_full_prem_select_recursion(A_Ex, N, choosed, 0);

	SafeDeleteArray(A_Ex);
	SafeDeleteArray(choosed);
	return;
}

输入：A B C

输出：

2.不重复全排列

集合S(m)中有相异元素n(1 <= n <= m)个，生成的排列中会有重复的，需要剔除。规模数为：

1)交换_递归

//不重复全排列
//交换 递归
//p:表示递归到第p层
typedef char ElemType;
void _unrepeat_prem_swap_recursion(ElemType *A, int N, int p)
{
	static int count = 1;
	if (p == N)
	{
		cout<<"["<<count<<"\t] = ";
		for (int i = 0; i < N; ++i)
		{
			cout<<A[i]<<" ";
		}
		cout<<endl;
		count++;
		return;
	}

	for (int i = p; i < N; ++i)
	{
		//减枝
		//如果A[i]与A[p...i-1]的任一元素相同,则表示这个待生成的序列是重复的,需要跳过
		bool find = false;
		for (int j = p; j < i; ++j)
		{
			if (A[i] == A[j])
			{
				find = true;
				break;
			}
		}
		if (find)
		{
			continue;
		}

		Swap(A[i], A[p]);//交换
		_unrepeat_prem_swap_recursion(A, N, p + 1);
		Swap(A[i], A[p]);//恢复
	}
}

void unrepeat_prem_swap_recursion(ElemType *A, int N)
{
	_unrepeat_prem_swap_recursion(A, N, 0);
}

输入：A A C D

输出：

2)选择_递归

//不重复全排列
//选择 递归
//p:表示递归到第p层
void _unrepeat_prem_select_recursion(ElemTypeEx *A, int N, int M, ElemType *choosed, int p)
{
	static int count = 1;
	if (p == M)
	{
		cout<<"["<<count<<"\t] = ";
		for (int i = 0; i < M; ++i)
		{
		cout<<choosed[i]<<" ";
		}
		cout<<endl;
		count++;
		return;
	}

	for (int i = 0; i < N; ++i)
	{
		if (A[i].num > 0)
		{
			--A[i].num; //可用次数减1
			choosed[p] = A[i].value;
			_unrepeat_prem_select_recursion(A, N, M, choosed, p+1); 
			++A[i].num; //可用次数恢复
		}
	}
}
//不重复全排列
void unrepeat_prem_select_recursion(const ElemType *A, int N)
{
	ElemTypeEx *A_Ex = new ElemTypeEx[Count_unrepeat(A,N)];
	int M = 0;
	Compress(A, N, A_Ex, M);

	ElemType *choosed = new ElemType[N];

	_unrepeat_prem_select_recursion(A_Ex, M, N, choosed, 0);

	SafeDeleteArray(A_Ex);
	SafeDeleteArray(choosed);
}

输入：A A C D

输出：

3.选择排列

从集合S(n)中，取出的所有的k-排列。规模数为nPk。

1)交换_递归

//选择排列 P(N, M)
//交换递归
//p:表示递归到第p层
typedef char ElemType;
void _select_prem_swap_recursion(ElemType *A, int N, int M, int p)
{
	static int count = 1;
	if (p == M)
	{
		cout<<"["<<count<<"\t] = ";
		for (int i = 0; i < M; ++i)
		{
			cout<<A[i]<<" ";
		} 
		cout<<endl;
		count++;
		return;
	}

	for (int i = p; i < N; ++i)
	{
		Swap(A[i], A[p]);//交换
		_select_prem_swap_recursion(A, N, M, p + 1);
		Swap(A[i], A[p]);//恢复
	}
}
void select_prem_swap_recursion(ElemType *A, int N, int M)
{
	_select_prem_swap_recursion(A, N, M, 0);
}

输入：A B C k = 2

输出：

2)选择_递归

//选择排列
//选择递归
//p:表示递归到第p层
typedef char ElemType;

typedef struct stElemNode
{
	ElemType value;
	unsigned char num;
} ElemTypeEx;

void _select_prem_select_recursion(ElemTypeEx *A, int N, int M, ElemType *choosed, int p)
{
	static int count = 1;
	if (p == M)
	{
		cout<<"["<<count<<"\t] = ";
		for (int i = 0; i < M; ++i)
		{
			cout<<choosed[i]<<" ";
		}
		cout<<endl;
		count++;
		return;
	}

	for (int i = 0; i < N; ++i)
	{
		if (A[i].num > 0)
		{
			--A[i].num; //可用次数减1
			choosed[p] = A[i].value;
			_select_prem_select_recursion(A, N, M, choosed, p+1); 
			++A[i].num; //可用次数恢复
		}
	}
}
void select_prem_select_recursion(const ElemType *A, int N, int M)
{
	ElemTypeEx *A_Ex = new ElemTypeEx[N];

	for (int i = 0; i < N; ++i)
	{
		A_Ex[i].value = A[i];
		A_Ex[i].num = 1;
	}

	ElemType *choosed = new ElemType[N];

	_select_prem_select_recursion(A_Ex, N, M, choosed, 0);

	SafeDeleteArray(A_Ex);
	SafeDeleteArray(choosed);
	return;
}

输入：A B C k = 2

输出：

常见的排列有以上三种，若有其他形式的排列，可以通过上面的三种组合出来。

如想了解常见的组合算法的实现，可以参考组合算法实现。