題目及解題程序給在末尾，先來看看排列一個數(shù)組的方法。
給定一個數(shù)組 array[] = {3, 1, 2, 4, 0}; 這個給定的數(shù)組有目的性，即它符合 n * m 的規(guī)則，這里是 5 * 5（5個元素，5個連續(xù)且不同的值）。按我想到的一般的方法，就是使用循環(huán)來求出各種排列的可能，但這種方法不能確保每個元素只出現(xiàn)一次，且隨著元素個數(shù)的增長，循環(huán)深度將變得很深。繼續(xù)想下去，這種方法將會變得很復雜，這就要求我尋找另外一種方法。注意到每個元素并不相同，那么要使各個元素在每個位置上只出現(xiàn)一次，很明顯的一種方法就是“彩票機讀票法”。比如數(shù)據(jù)讀入口在第一個元素的位置，那么依次循環(huán)這個數(shù)組，每次使后面的元素向前移動一位，各個數(shù)字不就都讀到了嗎，這就像在打印機中滾動的紙。具體步驟如下：
31240
12403 <—rotate
第一位如此，那么后面的每一位也如此，也就是遞歸地處理后面的數(shù)字，每移動一位就以下一位為起點做相同的處理，直到所有數(shù)字循環(huán)了一遍，那排列的工作也就完成了。一個具體的實現(xiàn)如下：
/*
* @param r: 需要求其排列的向量
* @param iPos: 當前所進行到的位置
* 程序體中的注釋表示處于那個位置的向量都是一個新的且唯一的排列
*/
void rotate(vector<int>& r, int iPos) {
if(iPos == r.size() - 1)//是否循環(huán)完畢，調用函數(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ù)字開始新的位移
}
} 這種方法不要求數(shù)字式連續(xù)的，也不用事先規(guī)定好向量的長度。只是當向量長度到了一定的時候，運算時間會很長！其它方法未知……
topcoder 上的練習題如下：
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;
}
posted on 2009-12-19 20:53
崇文 閱讀(2107)
評論(0) 編輯 收藏 引用