【蓝桥】排列序数

题目

题目描述

如果用 a b c d 这 4 个字母组成一个串,有 4!=24 种,如果把它们排个序,每个串都对应一个序号:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
abcd 0
abdc 1
acbd 2
acdb 3
adbc 4
adcb 5
bacd 6
badc 7
bcad 8
bcda 9
bdac 10
bdca 11
cabd 12
cadb 13
cbad 14
cbda 15
cdab 16
cdba 17
...

现在有不多于 10 个两两不同的小写字母,给出它们组成的串,你能求出该串在所有排列中的序号吗?

输入描述

输入一行,一个串。

输出描述

输出一行,一个整数,表示该串在其字母所有排列生成的串中的序号。注意:最小的序号是 0。

输入输出样例

示例

输入

1
bdca

输出

1
11

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 256M

解题

源码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
string s, olds;
cin >> s;
olds = s;
sort(s.begin(), s.end());
int count = 0;
do
{
if (s == olds)
{
cout << count << endl;
break;
}
count++;
} while (next_permutation(s.begin(), s.end()));
return 0;
}

Python

1
2
3
4
5
6
7
8
9
10
from itertools import *
s = input()
a = list(s)
a.sort()
count = 0
for i in permutations(a):
b=''.join(i)
if b==s:
print(count)
count+=1

总结

C++版

  1. 全排列遍历,相等就输出
  2. oj有问题无法提交

Python版

  1. 全排列遍历,相等就输出
  2. oj有问题无法提交