next_permutation

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

template<typename Iter>

bool next_permutation(Iter first, Iter last) {

    if (first == last)

        return false;

    Iter i = first;

    i+=1;

    if(i==last)

        return false;

    i=last;

    i-=1;

        

    for(;;) {

        Iter ii = i;

        i-=1;

        if(*i < *ii) {

            Iter j = last;

            while(!(*i < *--j)) {

            }

            std::iter_swap(i, j);

            std::reverse(ii, last);

            return true;

        }

        if(i==first) {

            std::reverse(first, last);

            return false;

        }

    }

}

밑에 나오는 문자열의 바로 다음 순열을 구해보자 

8342666411

[8342] [666411] 의 2부분으로 나누어 진다.

꼬리 부분은 단순감소하는 부분이고, 머리 부분은 8342 이다.

꼬리 부분은 역순으로 되어 있고, 이들 원소들을 바꾸어서는 그 다음 순열을 구할 수가 없다.

다음 순열을 구하기 위해서는 머리 부분을 (최소로) 증가 사켜야 한다.

꼬리부분 중에서 머리 부분의 가장 끝 수인 2보다 큰 수중에서 가장 작은 수를 찾는다.

즉 꼬리부분의 끝에서 부터 앞으로 가면서 2보다 큰 수를 찾으면 4를 찾을 수 있다. 

이제 2와 4을 바꾸어 준다.

[8344] [666211]

머리 부분이 증가했기 때문에, 더 큰 순열이 구해졌다.

꼬리 부분을 최소로 해 주어야 최소 큰 순열을 구할 수 있다.

[8344] [112666]

머리과 꼬리를 합치면

8344112666 

이 된다.

따라서 8342666411 의 다음 순열은 8344112666 이 된다.

What’s happening here?

It’s clear from this paper analysis that the algorithm is of linear complexity. 

Essentially, it walks up and down the tail of the list, comparing and swapping. 

But why does it work?

Let xs be the range (first, last). As described above, divide this range into 

prefix and suffix subranges, head and tail, where tail is the longest monotonically 

decreasing tail of the range.

If the head of the range is empty, then the range xs is clearly at its lexicographical maximum.

Otherwise, tail is a lexicographical maximum of the elements it contains, 

and xs is therefore the largest permutation which starts with the subrange head. 

What will the head of the next permutation be? We have to swap the final item in head 

with the smallest item of tail which exceeds it: the definition of tail guarantees 

at least one such item exists. Now we want to permute the new tail to be at a its 

lexicographical minimum, which is a matter of sorting it from low to high.

Since tail is in reverse order, finding the smallest item larger than head[-1] is 

a matter of walking back from the end of the range to find the first such items; 

and once we’ve swapped these items, tail remains in reverse order, so a simple 

reversed will sort it.

As an example consider finding the next permutation of:

8342666411

The longest monotonically decreasing tail is 666411, and the corresponding head is 8342.

8342 666411

666411 is, by definition, reverse-ordered, and cannot be increased by permuting its elements. 

To find the next permutation, we must increase the head; a matter of finding the smallest 

tail element larger than the head’s final 2.

8342 666411

Walking back from the end of tail, the first element greater than 2 is 4.

8342  666411

Swap the 2 and the 4

8344 666211

Since head has increased, we now have a greater permutation. To reduce to the next permutation, 

we reverse tail, putting it into increasing order.

8344 112666

Join the head and tail back together. The permutation one greater than 8342666411 is 8344112666.