7-7 排列的字典序问题 (20 分)

旧城等待， 2023-10-11 16:51 172阅读 0赞

n个元素 \{1，2, …，n\} 有n!个不同的排列。将这 n! 个排列按字典序排列， 并编号为 0，1，…，n!-1 。每个排列的编号为其字典序值。例如，当n=3时，6个不同排列的字典序值如下：

<table> 
 <thead> 
  <tr> 
   <th>字典序值</th> 
   <th>0</th> 
   <th>1</th> 
   <th>2</th> 
   <th>3</th> 
   <th>4</th> 
   <th>5</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>排列</td> 
   <td>123</td> 
   <td>132</td> 
   <td>213</td> 
   <td>231</td> 
   <td>312</td> 
   <td>321</td> 
  </tr> 
 </tbody> 
</table>

#### 输入格式: ####

第一行是元素个数n(1<n<=8)，接下来的1行是n个元素\{1,2,...,n\}的一个排列。题目不会给出最后一个排列。

#### 输出格式: ####

第一行输出计算出的排列的字典序值，第二行输出按字典序排列的下一个排列。

#### 输入样例: ####

3
    2 3 1

结尾无空行

#### 输出样例: ####

3
    3 1 2

结尾无空行

代码实现：

#include <bits/stdc++.h>
    using namespace std;
    
    int a[12],goal[12];
    int k;
    
    bool check(int a[],int b[]){
    	for(int i = 1;i<=k;i++){
    		if(a[i]!=b[i])
    			return true;
    	}
    	return false;
    }
    
    int main ()
    {
        int con = 0;
        cin>>k;
        for(int i = 1;i<=k;i++){
        	a[i] = i;
        	cin>>goal[i];
        }
        while(check(a,goal)){
        	next_permutation(a+1,a+k+1);
        	con++;
        }
        
        cout<<con<<endl;
        next_permutation(a+1,a+k+1);
        for(int i = 1;i<=k;i++)	{
        	cout<<a[i];
        	if(i!=k) cout<<" ";
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，172人围观）

还没有评论，来说两句吧...

相关阅读

相关 SWUST OJ 541: 排列的字典序问题

题目描述 n个元素\{1,2,…, n \}有n!个不同的排列。将这n!个排列按字典序排列，并编号为0，1，…，n!-1。每个排列的编号为其字典序值。例如，当n=3时，6

谁践踏了优雅/ 2024年04月01日 09:41/ 0 赞/ 216 阅读

相关排列的字典序问题

n个元素有n!个不同的排列。将这n!个不同的排列按字典序排列，并编号为0,1,2,…,n!-1。现在给定n个元素及一个排列，求这个序列的字典序值，和字典序排列的下一

迈不过友情╰/ 2023年10月18日 12:26/ 0 赞/ 28 阅读

相关全排列的生成算法:字典序法

全排列的生成算法:字典序法全排列的生成算法对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。字典序法按照字典序求下一个排列的算法生成

r囧r小猫/ 2023年10月17日 15:33/ 0 赞/ 33 阅读

相关 7-7 排列的字典序问题 (20 分)

n个元素 \{1，2, …，n\} 有n!个不同的排列。将这 n! 个排列按字典序排列，并编号为 0，1，…，n!-1 。每个排列的编号为其字典序值。例如，当n=3时，6个不

旧城等待，/ 2023年10月11日 16:51/ 0 赞/ 173 阅读

相关 sort如果按字典序排列的细节

暗藏玄只因这个题，乍一看，之前写过但是发现漏掉了好多细节 [P1012 \[NOIP1998 提高组\] 拼数 - 洛谷 | 计算机科学教育新生态 (luogu.co

系统管理员/ 2023年09月23日 23:02/ 0 赞/ 171 阅读

相关字典序算法与下一个排列问题算法推导

字典序算法一.字典序基础二.字典序算法相关下一个排列问题算法推导算法过程求字典序全排列递归方法

柔情只为你懂/ 2022年12月20日 03:16/ 0 赞/ 277 阅读

相关数据结构之字典序全排列

字典序法中，对于数字1、2、3……n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345，排列12345在前，排

痛定思痛。/ 2022年09月24日 05:15/ 0 赞/ 395 阅读

相关字典序排列（借助于TreeSet实现）

> 给出一个字符串S（可能又重复的字符），按照字典序从小到大，输出S包括的字符组成的所有排列。例如：S = “1312”， > 输出为： > 1123 > 1132

ゝ一世哀愁。/ 2022年07月25日 21:26/ 0 赞/ 302 阅读

相关递归与分治——字典序排列

问题描述： n个元素\{1,2,..., n \}有n!个不同的排列。将这n!个排列按字典序排列，并编号为0，1，…，n!-1。每个排列的编号为其字典序值。例如，当

古城微笑少年丶/ 2022年06月09日 10:30/ 0 赞/ 392 阅读

相关按字典序算法全排列

一、简介 [原文][Link 1] 按照字典里的排序方法：先比较第一个字符 i 和 b b<i b是第2个，i是第9个 2 < 9

梦里梦外;/ 2021年09月14日 02:40/ 0 赞/ 566 阅读