The Next Permutation-白红宇

The Next Permutation

阅读量：6397 次

发布时间：2019-06-23

本文共 3458 字，大约阅读时间需要 11 分钟。

原题：

Description

For this problem, you will write a program that takes a (possibly long) string of decimal digits, and outputs the permutation of those decimal digits that has the next larger value (as a decimal number) than the input number.

For example:

123 -> 132

279134399742 -> 279134423799

It is possible that no permutation of the input digits has a larger value. For example, 987.

Input

The first line of input contains a single integer P, (1≤P≤ 1000), which is the number of data sets that follow. Each data set is a single line that contains the data set number, followed by a space, followed by up to 80 decimal digits which is the input value.

Output

For each data set there is one line of output. If there is no larger permutation of the input digits, the output should be the data set number followed by a single space, followed by the string BIGGEST.

If there is a solution, the output should be the data set number, a single space and the next larger

permutation of the input digits.

Sample Input

31 1232 2791343997423 987

Sample Output

1 1322 2791344237993 BIGGEST

分析：

stl之—— next_permutation

在标准库算法中,next_permutation应用在数列操作上比较广泛.这个函数可以计算一组数据的全排列.

示例源码：

[cpp]
#include<stdio.h>
#include<algorithm>
#include<iostream>
usingnamespace std;  
int main()  
{  
int a[] = {3,2,1};  
do
    {  
        cout << a[0] << " " << a[1] << " " << a[2] << endl;  
    }  
while (prev_permutation(a,a+3));  
return 0;  
}  

在STL中，除了next_permutation外，还有一个函数prev_permutation，两者都是用来计算排列组合的函数。前者是求出下一个排列组合，而后者是求出上一个排列组合。

源码：

[cpp]
#include<stdio.h>
#include<string.h>
#include<algorithm>
usingnamespace std;  
int main()  
{  
int p,n;  
int w=1;  
char a[100000],b[100000];  
    scanf("%d",&n);  
    getchar();  
while(n--)  
    {  
        scanf("%d %s",&p,a);  
        strcpy(b,a);  
        next_permutation(a,a+strlen(a));  
if(strcmp(b,a)<0)  
        {  
            printf("%d %s\n",w,a);  
            w++;  
        }  
else
        {  
            printf("%d BIGGEST\n",w);  
            w++;  
        }  
    }  
return 0;  
}  

2、A Big Dinner

Description

As is known to all, an ACM team consists of three members and to know more about each others, they often go to a restaurant to have a big dinner.

Each member ordered himself only one dish, and waited for it. However, the restaurant serves in a strange way. They cooked the meal in a random order. Besides, if some same dishes appear consecutively, the cooks will cook the dishes at the same time.

Given the ordered three dishes, can you output every possible order the restaurant severed.

Input

The first line of the input is T(1 <= T <= 100), which stands for the number of test cases you need to solve.

For each case, there are three integers(the integers are all positive and less than 10) in the single line, which stand for the dish ID for each person.

Output

Every case contains one line with three integer standing for the kinds of ordered dishes.

For every test case, you should output "Case #t:" in the first line, where t indicates the case number and counts from 1. Then output all the possible order the restaurant can serve in the ascending order.

Sample Input

2 1 2

1 7 5

Sample Output

Case #1:

1 2 2

2 1 2

2 2 1

Case #2:

1 5 7

1 7 5

5 1 7

5 7 1

7 1 5

7 5 1

源码：

[csharp]
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
usingnamespace std;  
int main()  
{  
int k;  
int a[100];  
int w=1;  
    scanf("%d",&k);  
while(k--)  
    {  
for(int i=0; i<3; i++)  
        {  
            scanf("%d",&a[i]);  
        }  
        sort(a,a+3);  
        printf("Case #%d:\n",w);  
do
        {  
            cout << a[0] << " " << a[1] << " " << a[2] << endl;  
        }  
while (next_permutation(a,a+3));  
        w++;  
    }  
return 0;  
}  