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

旧城等待， 2023-10-11 16:51 67阅读 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 条评论，67人围观）

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

相关阅读

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

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

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

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

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

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

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

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

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

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

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

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

相关字典序问题

统计字典序的问题：只要你知道一个字符串的字典序列呢个位置：你要知道他前面有多少个，再加一即可使用两个函数：一个是统计长度为len的总个数，一个是统计一那个字母为首的长度为l

一时失言乱红尘/ 2022年10月10日 12:30/ 0 赞/ 191 阅读

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

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

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

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

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

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

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

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

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

相关 PageHelper 分页倒序排列

public ReturnJson selectPage(Integer pageNum, Integer pageSize, ZyBook zyBook) {

本是古典何须时尚/ 2022年02月19日 23:59/ 0 赞/ 405 阅读

相关按字典序算法全排列

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

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