next_number

http://wordaligned.org/articles/next-permutation

주어진 수에 대해서 현재 숫자들만 사용해서 다음에 나오는 수를 구한다.

이런 수가 없다면 0을 추가해서 다음에 나오는 수를 구해준다.

1의 다음 수는 1만 사용해서는 구할 수가 없다. 따라서 0을 추가해 준다. 

이때 0이 아닌 수 다음 수에 0을 삽입한다. 1 다음에 나오는 수는 10이 된다.

다음 수를 발견할 때 사용되는 알고리즘(함수)가 next_permutation 함수이다. 

The Next Number Problem

Suppose you have a fixed list of digits chosen from the range 1..9. 

What numbers can you make with them? You’re allowed as many zeros 

as you want. Write the numbers in increasing order.

Exactly this puzzle came up in the recent Google Code Jam programming contest:

You are writing out a list of numbers. Your list contains all numbers with 

exactly Di digits in its decimal representation which are equal to i, 

for each i between 1 and 9, inclusive. You are writing them out in ascending order.

For example, you might be writing every number with two ‘1’s and one ‘5’. 

Your list would begin 115, 151, 511, 1015, 1051.

Given N, the last number you wrote, compute what the next number in the list will be.

The competition has closed now, but if you’d like to give it a go sample input files 

can be found on the website, where you can also upload your results and have them checked.

Here’s a short section from a trial I ran on my computer. 

Input numbers are in the left-hand column: 

the corresponding output numbers are in the right-hand column.

50110812884911623516 → 50110812884911623561

82454322474161687049 → 82454322474161687094

82040229261723155710 → 82040229261723157015

43888989554234187388 → 43888989554234187838

76080994872481480636 → 76080994872481480663

31000989133449480678 → 31000989133449480687

20347716554681051891 → 20347716554681051918

#include <algorithm>

#include <iostream>

using namespace std;

/*

 Given a string of digits, shift any leading '0's

 past the first non-zero digit and insert an extra zero.

 

 Examples:

  

 123 -> 1023

 008 -> 8000

 034 -> 3004

*/

void insert_a_zero(string & number) {

    size_t nzeros = number.find_first_not_of('0');

    number = number.substr(nzeros);

    number.insert(1, nzeros + 1, '0');

}

/*

 Outline solution to the 2009 code jam Next Number problem.

 

 Given a string representing a decimal number, find the next

 number which can be formed from the same set of digits. Add

 another zero if necessary. Repeat for all such strings read

 from standard input.

*/

int main() {

    string number;

    while(cin >> number) {

        if (!next_permutation(number.begin(), number.end())) {

            insert_a_zero(number);

        }

        cout << number << '\n';

    }

    return 0;

}