全排列生成算法-递增进位制数-递减进位制数

/*****************递增递减算法*****************/
#include
#include
#include
#include
using namespace std;

int factorial(int n,int m)
{
int f = 1;
for(int i = m + 1; i <= n; i++)
{
f *= i;
}
return f;
}

int main()
{

int length;
int index = -1;
int way;
clock_t finish,start;
cout<<"请选择方法（1为递增，2为递减）："<cin>>way;
while(way != 1 && way != 2)
{
cout<<"输入错误，请选择方法（1为递增，2为递减）："<cin>>way;
}
cout<<"进位递增法"<cin>>length;
start = clock();
if(way == 1)
{
int maxIndex = factorial(length,1) - 1;
int *media = new int[length + 2];
int *result = new int[length + 1];
int *f = new int[length + 1];
for (int i = 0;i <= length; i ++)
{
f[i] = length + 1 - i;
result[i] = length + 1 - i;
media[i] = 0;
}
int l = length;
while(1)
{
//求中介数
media[2] ++;
int k = 2;
while(media[k] > k - 1)
{
media[k] = 0;
k ++;
media[k] ++;
}
if(k > length)
break;
l = k;
//求对应的排列

for(int i = 1; i <= l; i++)
{
result[f[i]] = 0;
}
for(int i = l; i > 0; i--)
{
int count = 0;
int flag = 1;

while(count < media[i])
{
if(result[flag] == 0)
{
count ++;
}
flag ++;

}
while(result[flag] != 0)
{
flag ++;
}
result[flag] = i;
f[i] = flag;
}
//输出结果
/*for(int i = length; i > 0; i--)
{
cout<}
cout<*/
}
finish = clock();
printf("The time was: %f\n", (double)(finish - start) / CLOCKS_PER_SEC);
}
else
{
int maxIndex = factorial(length,1) - 1;
int *media = new int[length + 1];
int *result = new int[length + 1];
int *f = new int[length + 1];
int *temp = new int[length + 1];
for (int i = 0;i <= length; i ++)
{
f[i] = length + 1 - i;
result[i] = length + 1 - i;
temp[i] = 0;
}
while(1)
{

//求对应的排列
int m;
for(m = length; f[m] == m ;m--)
{
temp[length + 1 - m] = m;

}
if(m == 0) break;
if(m < length)
{
for(int i = 1; i <= m; i ++)
{
result[length + 1 - i] = result[m + 1 - i];
f[result[length + 1 - i]] = length + 1 - i;
}
}
for(int i = m+1; i<= length; i++)
{
result[length + 1 - i] = temp[length + 1 - i];
f[result[length + 1 - i]] = length + 1 - i;
}
int t = result[f[m]];
result[f[m]] = result[f[m] + 1];
result[f[m] + 1] = t;

f[result[f[m]]] = f[m] ;
f[m] ++;
//输出结果
/*
for(int i = length; i > 0; i--)
{
cout<}
cout<for(int i = length; i > 0; i--)
{
cout<}
cout<*/
}
finish = clock();
print

f("The time was: %f\n", (double)(finish - start) / CLOCKS_PER_SEC);
}

system("pause");
return 0;
}