題目及解題程序給在末尾，先來(lái)看看排列一個(gè)數(shù)組的方法。

     給定一個(gè)數(shù)組 array[] = {3, 1, 2, 4, 0}; 這個(gè)給定的數(shù)組有目的性，即它符合 n * m 的規(guī)則，這里是 5 * 5（5個(gè)元素，5個(gè)連續(xù)且不同的值）。按我想到的一般的方法，就是使用循環(huán)來(lái)求出各種排列的可能，但這種方法不能確保每個(gè)元素只出現(xiàn)一次，且隨著元素個(gè)數(shù)的增長(zhǎng)，循環(huán)深度將變得很深。繼續(xù)想下去，這種方法將會(huì)變得很復(fù)雜，這就要求我尋找另外一種方法。注意到每個(gè)元素并不相同，那么要使各個(gè)元素在每個(gè)位置上只出現(xiàn)一次，很明顯的一種方法就是“彩票機(jī)讀票法”。比如數(shù)據(jù)讀入口在第一個(gè)元素的位置，那么依次循環(huán)這個(gè)數(shù)組，每次使后面的元素向前移動(dòng)一位，各個(gè)數(shù)字不就都讀到了嗎，這就像在打印機(jī)中滾動(dòng)的紙。具體步驟如下：

31240
12403 <—rotate

     第一位如此，那么后面的每一位也如此，也就是遞歸地處理后面的數(shù)字，每移動(dòng)一位就以下一位為起點(diǎn)做相同的處理，直到所有數(shù)字循環(huán)了一遍，那排列的工作也就完成了。一個(gè)具體的實(shí)現(xiàn)如下：

/*
 * @param r:     需要求其排列的向量
 * @param iPos:  當(dāng)前所進(jìn)行到的位置
 * 程序體中的注釋表示處于那個(gè)位置的向量都是一個(gè)新的且唯一的排列
*/

void rotate(vector<int>& r, int iPos) {

    if(iPos == r.size() - 1)//是否循環(huán)完畢，調(diào)用函數(shù)時(shí) iPos 置0
        return;

    int iNextPos = iPos + 1;
    for(size_t i = iPos; i < r.size(); ++i) {
        if(i == 0) {
            //a different permutation, do something here
        }

        int t = r[iPos];
        for(size_t j = iPos; j < r.size() - 1; ++j)//循環(huán)前移
            r[j] = r[j + 1];
        r[r.size() - 1] = t;

        if(i != r.size() - 1) {
            //a different permutation, do something here
        }

        rotate(r, iNextPos);//從下一位數(shù)字開(kāi)始新的位移
    }
}

   這種方法不要求數(shù)字式連續(xù)的，也不用事先規(guī)定好向量的長(zhǎng)度。只是當(dāng)向量長(zhǎng)度到了一定的時(shí)候，運(yùn)算時(shí)間會(huì)很長(zhǎng)！其它方法未知……

   topcoder 上的練習(xí)題如下：

Problem Statement

A permutation A[0], A[1], ..., A[N-1] is a sequence containing each integer between 0 and N-1, inclusive, exactly once. Each permutation A of length N has a corresponding child array B of the same length, where B is defined as follows:
B[0] = 0
B[i] = A[B[i-1]], for every i between 1 and N-1, inclusive.
A permutation is considered perfect if its child array is also a permutation.  Below are given all permutations for N=3 with their child arrays. Note that for two of these permutations ({1, 2, 0} and {2, 0, 1}) the child array is also a permutation, so these two permutations are perfect.
Permutation        Child array
{0, 1, 2}        {0, 0, 0}
{0, 2, 1}        {0, 0, 0}
{1, 0, 2}        {0, 1, 0}
{1, 2, 0}        {0, 1, 2}
{2, 0, 1}        {0, 2, 1}
{2, 1, 0}        {0, 2, 0}
You are given a vector <int> P containing a permutation of length N. Find a perfect permutation Q of the same length such that the difference between P and Q is as small as possible, and return this difference. The difference between P and Q is the number of indices i for which P[i] and Q[i] are different.
Definition

Class:
PerfectPermutation
Method:
reorder
Parameters:
vector <int>
Returns:
int
Method signature:
int reorder(vector <int> P)
(be sure your method is public)

Constraints
-
P will contain between 1 and 50 elements, inclusive.
-
P will contain each integer between 0 and N-1, inclusive, exactly once, where N is the number of elements in P.
Examples

0)
{2, 0, 1}
Returns: 0
P is a perfect permutation, so we can use the same permutation for Q. The difference is then 0 because P and Q are the same.

1)
{2, 0, 1, 4, 3}
Returns: 2
Q might be {2, 0, 3, 4, 1}.

2)
{2, 3, 0, 1}
Returns: 2
Q might be {1, 3, 0, 2}.

3)
{0, 5, 3, 2, 1, 4}
Returns: 3

4)
{4, 2, 6, 0, 3, 5, 9, 7, 8, 1}
Returns: 5

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

#include <iostream>
#include <vector>
#include <cstddef>
#include <limits>
#include <cassert>

#include <boost\assign.hpp>    // for vector +=

using namespace std;

class PerfectPermutation {
public:
    int  reorder(const vector<int>& P, vector<int>& result);
    bool isPerfect(const vector<int>& P);

private:
    int  difference(const vector<int>& P, const vector<int>& Q);
    void rotate(const vector<int>& src, vector<int>& r, int level, int& nMin, vector<int>& out);
};

int PerfectPermutation::difference(const vector<int>& P, const vector<int>& Q) {

    size_t cDiff = P.size();
    assert(cDiff == Q.size());

    for(size_t i = 0; i < P.size(); ++i) {
        if(P[i] == Q[i])
            cDiff--;
    }

    return cDiff;
}

bool PerfectPermutation::isPerfect(const vector<int>& A) {

    int Bi = 0, Bi_1 = 0;
    vector<bool> vb(A.size());
    vb[0] = true;

    for(size_t i = 1; i < A.size(); ++i) {
        if(vb[Bi = A[Bi_1]])
            return false;
        else
            vb[Bi] = true;

        Bi_1 = Bi;
    }

    return true;
}

void PerfectPermutation::rotate(const vector<int>& src, vector<int>& r, int level, int& nMin, vector<int>& out) {

    if(level == r.size() - 1)
        return;

    int in = level + 1;
    for(size_t i = level; i < r.size(); ++i) {
        if(i == 0 && isPerfect(r)) {
            nMin = min(difference(src, r), nMin);
            out = r;
        }

        int t = r[level];
        for(size_t j = level; j < r.size() - 1; ++j)
            r[j] = r[j + 1];
        r[r.size() - 1] = t;

        if((i != r.size() - 1) && isPerfect(r)) {
            nMin = min(difference(src, r), nMin);
            out = r;
        }

        rotate(src, r, in, nMin, out);
    }
}

int PerfectPermutation::reorder(const vector<int>& P, vector<int>& result) {

    if(P.size() == 1 || isPerfect(P))
        return 0;

    int nMin = numeric_limits<int>::max();

    vector<int> Q(P);

    rotate(P, Q, 0, nMin, result);

    return nMin == numeric_limits<int>::max() ? -1 : nMin;
}
int main() {

    using namespace boost::assign;

    PerfectPermutation pp;

    vector<int> P;
    P += 2, 0, 1, 4, 3;
    vector<int> result(P.size());

    cout << "Is a perfect Permutation :                    " << (pp.isPerfect(P) ? "Yes" : "No") << endl;
    cout << "Difference between before reorder and after : " << pp.reorder(P, result) << endl;
    assert(pp.isPerfect(result));
    cout << "One answer might be :                         ";
    for(size_t i = 0; i < result.size(); ++i)
        cout << result[i] << " ";
    cout << endl;

    return 0;
}