/*
Name: 有序全排列生成算法集锦
Copyright: 始发于goal00001111的专栏；
Description: 实现了五种有序全排列生成算法。
有关算法的分析讨论详见拙作《有序全排列生成算法》：
http://blog.csdn.net/goal00001111/archive/2008/11/18/3326619.aspx
*/
#include<iostream>
#include <time.h>
using namespace std;
void Permutation_1(long long n, long long m);//递归直接模拟法
void Permutation_2(long long n, long long m);//循环直接模拟法
void Permutation_3(long long n, long long m);//邻元素增值法
void Permutation_4(long long n, long long m);//设置中介数的字典序全排列生成法
void Permutation_5(long long n, long long m);//数学分析法
bool Try(long long a[], int left, int right, long long m, long long & s);
void MoveRight(long long a[], int left, int right);
void MoveLeft(long long a[], int left, int right);
bool IsRight(long long a[], int n);
void DiZeng(int dZ[], long long p[], int len, long long m);
void YingShe(int yShe[], int dZJ[], int len);
int Compare(long long p[], int n, long long m);
void Move(long long a[], int left, int pos);
void Reverse(long long a[], int left, int right);
int main()
{
long long m , n;
time_t startTime;
time_t endTime;
n = 12;
time(&startTime);
for(m=1000; m<10000001; m*=100)
Permutation_1(n, m); //递归直接模拟法
time(&endTime);
cout << "time 1 = " << difftime(endTime, startTime) << endl << endl;
time(&startTime);
for(m=1000; m<10000001; m*=100)
Permutation_2(n, m); //循环直接模拟法
time(&endTime);
cout << "time 2 = " << difftime(endTime, startTime) << endl << endl;
time(&startTime);
for(m=10; m<100001; m*=100)
Permutation_3(n, m); //邻元素增值法
time(&endTime);
cout << "time 3 = " << difftime(endTime, startTime) << endl << endl;
time(&startTime);
for(m=1000; m<10000001; m*=100)
Permutation_4(n, m); //设置中介数的字典序全排列生成法
time(&endTime);
cout << "time 4 = " << difftime(endTime, startTime) << endl << endl;
time(&startTime);
for(m=1000; m<10000001; m*=100)
Permutation_5(n, m); //数学分析法
time(&endTime);
cout << "time 5 = " << difftime(endTime, startTime) << endl << endl;
system("pause");
return 0;
}
////////////////////////////////////////////////////////////////////////
/*
函数名称：Permutation
函数功能：输出n个数的第m种全排列
输入变量：long long n：1，2，3，...，n共n个自然数（1<=n<=20）
long long m：第m种全排列（1<=m<=n!）
输出变量：无
*/
void Permutation_1(long long n, long long m)//递归直接模拟法
{
long long *a = new long long[n];//用来存储n个自然数
for (int i=0; i<n; i++)
{
a[i] = i + 1;
}
long long s = 0;//记录当前是第几个全排列
Try(a, 0, n-1, m, s);//递归查找并输出n个数的第m种全排列
delete []a;
}
/*
函数名称：Try
函数功能：递归查找并输出n个数的第m种全排列 ，找到第m种全排列返回true，否则返回false
输入变量：long long a[]：用来存储n个自然数，按照第m种全排列存储
int left：数组的左界
int right：数组的右界
long long m：第m种全排列（1<=m<=n!）
long long & s：记录当前是第几个全排列
输出变量：找到第m种全排列返回true，否则返回false
*/
bool Try(long long a[], int left, int right, long long m, long long & s)
{
if (left == right)//已经到达数组的右界，直接输出数组
{
s++;
if (s == m)//找到第m种全排列
{
cout << s << ": ";
for (int i=0; i<=right; i++)
{
cout << a[i] << ' ';
}
cout << endl;
return true;
}
}
else
{ //将当前最左边的元素与其后面的元素交换位置
//当i=left时，与自身交换，相当于不换，直接输出
for (int i=left; i<=right; i++)
{
MoveRight(a, left, i);
if (Try(a, left+1, right, m, s))
{
return true;
}
MoveLeft(a, left, i);
}
}
return false;
}
//将right位置的元素左移到left位置，其他元素按顺序右移
void MoveRight(long long a[], int left, int right)
{
long long temp = a[right];
for (int i=right; i>left; i--)
{
a[i] = a[i-1];
}
a[left] = temp;
}
//将left位置的元素右移到right位置，其他元素按顺序左移
void MoveLeft(long long a[], int left, int right)
{
long long temp = a[left];
for (int i=left; i<right; i++)
{
a[i] = a[i+1];
}
a[right] = temp;
}
//////////////////////////////////////////////////////////////////////////////
void Permutation_2(long long n, long long m)//循环直接模拟法
{
long long *a = new long long[n];//用来存储n个自然数
for (int i=0; i<n; i++) //存储全排列的元素值，并计算全排列的数量
{
a[i] = i + 1;
}
cout << m << ": "; //输出n个数的第m种全排列
int left, right;
long long temp;
for (int i=1; i<m; i++)
{
left = n - 2; //设置需要改变的元素的左边界，保证此时左边界右边的元素是一个递减排列
while (left >= 0 && a[left] > a[left+1])
left--;
right = n - 1;
while (a[right] < a[left])//找到左边界右边数组中比a[left]大的最小的元素，这个就是要取代a[left]的元素
right--;
temp = a[left]; a[left] = a[right]; a[right] = temp; //交换a[right]和a[left]
left++; //左边界增1，保证此时左右边界之间的元素是一个递减排列
right = n -1;
while (left < right)//逆置左右边界之间的元素，使其按增序排列
{
temp = a[left]; a[left] = a[right]; a[right] = temp;
left++;
right--;
}
}
for (int i=0; i<n; i++)
{
cout << a[i] << " ";
}
cout << endl;
delete []a;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////
void Permutation_3(long long n, long long m)//邻元素增值法
{
long long *a = new long long[n];//用来存储n个自然数
for (int i=0; i<n; i++) //存储全排列的元素值
{
a[i] = i + 1;
}
cout << m << " : ";
long long s = 1;
int pos;
while (s < m)
{
pos = n - 1; //最后一位加n-1
a[pos] = (a[pos] + pos);
while (pos > 0 && a[pos] > n)//若有进位，前一元素加1，直到没有进位为止
{
a[pos--] -= n;//大于n则取余数，实际上a[pos]一定比2*n小
a[pos] += 1; //前一元素加1
}
if (a[0] > n)//当第一个元素的值>n则结束
break;
if (IsRight(a, n))//若数组a中不存在重复元素，说明得到了一个正确的全排列
{
s++;
}
}
for (int i=0; i<n; i++)
cout << a[i] << ' ';
cout << endl;
delete []a;
}
bool IsRight(long long a[], int n)
{
for (int i=0; i<n; i++)
{
for (int j=i+1; j<n; j++)
{
if (a[i] == a[j])
return false;
}
}
return true;
}
////////////////////////////////////////////////////////////////////////////////////////
void Permutation_4(long long n, long long m)//设置中介数的字典序全排列生成法
{
int *a = new int[n];//用来存储n个自然数，也可以看成是初始全排列1234...n
for (int i=0; i<n; i++)
{
a[i] = i + 1;
}
long long s = 1;
long long *p = new long long[n];//用来存储各个全排列的值，p[i]=i!
for (int i=0; i<n; i++)
{
s *= a[i];
p[i] = s;
}
cout << m << ": "; //输出n个数的第m种全排列
int *diZ = new int[n-1]; //用来存储序号m的递增进进制数，设所有元素的初值为0
for (int i=0; i<n-1; i++)
{
diZ[i] = 0;
}
DiZeng(diZ, p, n-1, m-1);//获取序号m-1的递增进进制数
int *zhongJie = new int[n-1];
for (int i=0; i<n-1; i++)//设初始全排列的中介数为0
zhongJie[i] = 0;
YingShe(zhongJie, diZ, n);//将原中介数加上序号m-1的递增进进制数得到新的映射
//将映射还原，得到新的全排列b
int *b = new int[n];//用来存储新的全排列
for (int i=0; i<n-1; i++) //获取前n-1个数字
{
s = 0;
int j = 0;
while (s < zhongJie[i])
{
if (a[j] != -1)
s++;
j++;
}
while (a[j] == -1)
j++;
b[i] = a[j];
a[j] = -1; //用-1表示该位置已经被填充
}
for (int i=0; i<n; i++)//填充最后一个数字
{
if (a[i] != -1)
{
b[n-1] = a[i];
break;
}
}
for (int i=0; i<n; i++)
{
cout << b[i] << ' ';
}
cout << endl;
delete []a;
delete []b;
delete []p;
delete []diZ;
delete []zhongJie;
}
void YingShe(int yShe[], int dZJ[], int len)
{
int pos = len - 2;
int r = 0;
while (pos >= 0)
{
yShe[pos] += dZJ[pos] + r;
if (yShe[pos] >= len - pos)
{
yShe[pos] -= len - pos;
r = 1;
}
else
r = 0;
pos--;
}
}
void DiZeng(int dZ[], long long p[], int len, long long m)
{
int pos = 0;
while (m > 0)
{
while (m < p[len-1-pos])
{
dZ[pos++] = 0;
}
if (m == p[len-1-pos])
{
dZ[pos++] = 1;
while (pos < len)
dZ[pos++] = 0;
break;
}
else
{
dZ[pos] = m / p[len-1-pos];
m %= p[len-1-pos];
pos++;
}
}
}
/////////////////////////////////////////////////////////////////////////////
void Permutation_5(long long n, long long m)//数学分析法
{
long long *a = new long long[n];//用来存储n个自然数
for (int i=0; i<n; i++)
{
a[i] = i + 1;
}
long long s = 1;
long long *p = new long long[n];//用来存储各个全排列的值，p[i]=i!
for (int i=0; i<n; i++)
{
s *= a[i];
p[i] = s;
}
cout << m << ": "; //输出n个数的第m种全排列
while (m > 1)//通过判断m的值排列数组a的元素
{
//若m=1，什么也不做，直接输出数组
if (m == 2) //若只要求输出第2个排列，直接交换数组最后两个元素
{
long long temp = a[n-1];
a[n-1] = a[n-2];
a[n-2] = temp;
break; //跳出循环
}
else if (m > 2)
{
int pos = Compare(p, n, m);//查找pos，使得p[pos-1] < m <= p[pos]
int left = n - 1 - pos;//由于m<p[pos]，所以前n-1-pos个元素不必移动，故让数组的左界移至n-1-pos位
if (p[pos] == m)//如果p[pos] == m，直接逆置数组
{
Reverse(a, left, n-1);//逆置数组
break; //跳出循环
}
else
{
int r = m / p[pos-1] + left;//计算排列在left位的元素位置
m %= p[pos-1]; //改变m的值----这是本算法的关键！
if (m == 0)//如果m是p[pos-1]的倍数，将第r-1位元素移动到left位
{
Move(a, left, r-1);
Reverse(a, left+1, n-1);//逆置数组
}
else//否则将第r位元素移动到left位，并排列剩下的数组元素
{
Move(a, left, r);
}
}
}
}
for (int i=0; i<n; i++)
{
cout << a[i] << ' ';
}
cout << endl;
delete []a;
delete []p;
}
/*
函数名称：Reverse
函数功能：逆置数组
输入变量：long long a[]：逆置前的数组
int left：数组的左界
int right：数组的右界
输出变量：long long a[]：逆置后的数组
*/
void Reverse(long long a[], int left, int right)
{
while (left < right)
{
long long temp = a[left];
a[left++] = a[right];
a[right--] = temp;
}
}
/*
函数名称：Compare
函数功能：寻找使得p[pos-1] < m <= p[pos]的数组下标pos，确保m<=p[n-1]
输入变量：long long p[]：数组
int n：数组的长度
int m：用来比较的数m
输出变量：满足条件的数组下标pos
*/
int Compare(long long p[], int n, long long m)
{
for (int i=0; i<n; i++)//确保m<=p[n-1]
{
if (p[i] >= m)
{
return i;
}
}
}
/*
函数名称：Move
函数功能：将pos位的元素向左移动到left位，而left~（pos-1）位的元素则依次右移一位
输入变量：long long p[]：数组
int left：数组的左界
int pos：需要左移的位置
输出变量：满足条件的数组下标pos
*/
void Move(long long a[], int left, int pos)
{
long long temp = a[pos];//先将a[pos]存储起来
for (int i=pos; i>left; i--)//left~（pos-1）位的元素则依次右移一位
{
a[i] = a[i-1];
}
a[left] = temp;//pos位的元素移动到left位
}
//////////////////////////////////////////////////////////////////////////////////
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/Deutschester/archive/2009/06/24/4295684.aspx
分享到：
相关推荐
整数分拆以及等差数列多重约束条件下全排列的生成法，杜瑞卿，刘广亮，为了能够实现整数分拆有序和无序的全部排列和组合，以及任意等差数列的全排列生成及其在多重约束条件下的全排列生成，详细论证了
全排列算法有两个比较常见的实现：递归排列和字典序排列。 （1）递归实现 从集合中依次选出每一个元素，作为排列的第一个...这种方式实现得到的所有排列是按字典序有序的，这也是C++ STL算法next_permutation的思想
We have retired the initial release of Snowflake and working on open sourcing the next version based on Twitter-server, in a form that can run anywhere without requiring Twitter's own infrastructure ...
有序边表填充算法
从键盘输入数据，建立两个有序线性表(每个线性表的输入数据按由小到大次序输入来建立线性表，不必考虑排序算法)；输出建好的这两个有序线性表；将这两个有序线性表归并为一个有序线性表；输出归并后的有序线性表。 ...
计算机图形学有序边表填充算法.pdf计算机图形学有序边表填充算法.pdf计算机图形学有序边表填充算法.pdf计算机图形学有序边表填充算法.pdf计算机图形学有序边表填充算法.pdf
有序链表合并算法动态演示系统是在B/S模式下，在MyEclipse 7.5环境中开发出来的，主要用于教学，对提高教学质量有很大的帮助。
在 pycharm 加 pyqt5环境中开发，python实现有序边表算法。 有优美的 UI界面
Orere Dither Cre Algrithm - Rea：有序抖动算法的核心算法—读.doc
本文基于FCOM算法,将排序加权模式进行改进,提出一种特征加权的模糊C有序均值聚类算法(feature weighted fuzzy C-ordered-means clustering,FWFCOM)。为了验证算法的有效性,选取6个UCI数据集进行试验。结果表明,...
用单链表实现：已知单链表L为按值递增有序的，编写算法将数据元素e插入到顺序表L中，使之仍有序
void main(int argc,char* argv[]) { char arg[50]={0}; arg[0]= '\"'; strcpy(arg+1,argv[0]); int len=int(strlen(arg)); arg[len]= '\"';... HWND hWnd=FindWindow(NULL,arg);...//通过窗口句柄得到该窗口的...
分别采用数组与链表，“求两个集合的合并运算”与“两个有序表合并后仍然有序”，要求编程实现。 题目一 求两个集合的合并运算 题目二 求两个有序表合并算法
数据结构 两个有序线性表的归并算法 西南交通大学
静态查找表。实现有序表的折半查找算法 静态查找表。实现有序表的折半查找算法 静态查找表。实现有序表的折半查找算法静态查找表。实现有序表的折半查找算法
有序样品的聚类分析就是对有序样品进行分段的统计方法。对n个有序样品进行分割，就可能有2n-1种划分方法，这每一种分法成为一种分割。在所有的这些分割中，有一种分割使得各段内部之间差异性最小，而短语段之间差异...
利用有序搜索算法解决十五数码问题，利用Java实现。这是本人亲自编写的程序，为人工智能作业，有详细的说明和注释，并且有实验报告。
有序抖动半调图像的无损压缩算法.pdf 获得基本的图像压缩知识
实验2 直线的DDA生成算法 实验3 直线中点生成算法 实验4 直线Bresenham生成算法 实验5 中点画圆算法 实验6 中点画椭圆算法 实验7 多边形有序边表算法 实验8 边标志多边形填充算法 实验9 种子填充算法 实验10 直线的...