PTA数据结构习题2.8 输出全排列 (20分)_WWIandMC的博客-程序员秘密

技术标签： PTA

习题2.8 输出全排列 (20分)

请编写程序输出前n个正整数的全排列（n<10），并通过9个测试用例（即n从1到9）观察n逐步增大时程序的运行时间。

输入格式:

输入给出正整数n（<10）。

输出格式:

输出1到n的全排列。每种排列占一行，数字间无空格。排列的输出顺序为字典序，即序列a₁,a₂,⋯,a_n排在序列b₁,b₂,⋯,b_n之前，如果存在k使得a₁=b₁,⋯,a_k=b_k并且 a_k+1 < b_k+1。

输入样例：

输出样例：

全排列字典序算法

全排列生成算法
所谓字典序，就是将元素按照字典的顺序（a-z，1-9）进行排列。strcmp就是以字典序来比较字符串。

字典序算法步骤

设P是集合
${1,2,......n-1,n\}$
的一个全排列：P₀P₁…P_j-1P_jP_j+1…P_n

集合必须按照递增顺序排列好

从下标n开始递减，找出第一个比右边数字小的数字序号i
$P_i<P_{i+1}$
在P_i右边的数字里，找到所有比P_j大的数字中最小的数字P_k，即
$k=\min\{i|P_i>P_j,i>j\}$
交换P_i，P_j
将i右边的序列P_i+1P_i+2…P_n逆置，变为P_nP_n-1…P_i+1

C++代码如下

#include <iostream>
#include <cstdio>

int
fact( int n );

void
dictSeq( int a[], int n );

void
reverse( int a[], int n, int j );

void
swaq( int &a, int &b );

void
print_array( int a[], int n );

int
main( void )
{
    
	int *a;
	int n;
	scanf("%d", &n);
	a = new int[n];
	for( int i = 0; i < n; i++ ){
    
		a[i] = i+1;
	}

	int total = fact(n);	//全排列个数等于n!
	print_array( a, n );	//初始序列算一种排列, 在交换之前单独输出

	for( int i = 1; i < total; i++ ){
    	//让dictSeq执行total-1次, 输出除初始序列之后的所有可能
		dictSeq( a, n );
	}

	return 0;
}

void
dictSeq( int a[], int n )
{
    
	int i;
	for( i = n-1; i > 0; i-- ){
    
		if( a[i-1] < a[i] ){
    
			i--;
			break;	
		}
	}
	
	int min_j = i + 1;
    int min = a[min_j];
	for( int j = min_j; j < n; j++ ){
    
		if( a[j] > a[i] && min > a[j] ){
    
			min = a[j];
			min_j = j;
		}
	}
	swaq( a[min_j], a[i] );
	reverse( a, n, i );
	print_array( a, n );
}

void
reverse( int a[], int n, int i )
{
    
	int left = i + 1, right = n - 1;
	while( left < right ){
    
		swaq( a[left++], a[right--]);
	}
}

int
fact( int n )
{
    
	int fact = 1;
	do{
    
		fact *= n--;
	}while( n > 0 );
	
	return fact;
}

void
swaq( int &a, int &b )
{
    
	int temp;
	temp = a;
	a = b;
	b = temp;
}

void
print_array( int a[], int n )
{
    
	for( int i = 0; i < n; i++ ){
    
		printf("%d", a[i]);
	}
	printf("\n");
}

本文链接：https://blog.csdn.net/WWIandMC/article/details/107719933

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Bert使用的激活函数：gelu---高斯误差线性单元_bert的激活函数_eunicechen的博客-程序员秘密

Bert Transfromer结构中使用了这个激活函数---gelu（Gaussian error linear units，高斯误差线性单元），Gelu在论文中已经被验证，是一种高性能的神经网络激活函数，因为GELU的非线性变化是一种符合预期的随机正则变换方式（这句话，说实话，我翻译自原论文，具体怎么理解呢？我自己是如下理解的）。激活函数的作用：给网络模型加入非线性因子，这...

AndroidStudio 中如何导入和删除jar包_大道至簡的博客-程序员秘密

一、添加jar包的步骤：1、将jar包拷贝添加到 libs目录，libs文件夹在 app文件夹下（没有libs目录就自己手动创建个，app/libs ）如图：2、然后再右键单击项目，点击 Open Module Settings，在Dependencies中点“+”号，选择添加对应的jar文件，如图：这样就

BZOJ 2705 [SDOI2012]Longge的问题_Orion_Rigel的博客-程序员秘密

欧拉函数

DataGrid小技巧_JOHNCOOLS的博客-程序员秘密

//添加删除确认对话框：private void DataGrid1_ItemDataBound( ){ switch(e.Item.ItemType) { case ListItemType.Item: case ListItemType.AlternatingItem: case ListItemType.EditItem: ImageButt

Faster R-CNN源码阅读之四：Faster R-CNN/lib/rpn_msr/generate_anchors.py_子为空的博客-程序员秘密

一、介绍本demo由Faster R-CNN官方提供，我只是在官方的代码上增加了注释，一方面方便我自己学习，另一方面贴出来和大家一起交流。该文件中的函数主要都是与anchor的生成相关，即给定纵横比和尺寸等一定的参数，生成符合条件的若干个anchor(s)。二、代码以及注释# -*- coding:utf-8 -*-# -----------------------...

[HDU2588]GCD（数论）_数论 gcd题目 hdu分类_Clove_unique的博客-程序员秘密

最典雅的友谊被矜持的水笔描画着，越描越淡。