随笔-14  评论-8  文章-0  trackbacks-0

     题目及解题程序给在末尾,先来看看排列一个数组的方法。

     给定一个数组 array[] = {3, 1, 2, 4, 0}; 这个给定的数组有目的性,即它符合 n * m 的规则,这里是 5 * 5(5个元素,5个连续且不同的值)。按我想到的一般的方法,就是使用循环来求出各种排列的可能,但这种方法不能确保每个元素只出现一次,且随着元素个数的增长,循环深度将变得很深。继续想下去,这种方法将会变得很复杂,这就要求我寻找另外一种方法。注意到每个元素并不相同,那么要使各个元素在每个位置上只出现一次,很明显的一种方法就是“彩票机读票法”。比如数据读入口在第一个元素的位置,那么依次循环这个数组,每次使后面的元素向前移动一位,各个数字不就都读到了吗,这就像在打印机中滚动的纸。具体步骤如下:

31240
12403 <—rotate

     第一位如此,那么后面的每一位也如此,也就是递归地处理后面的数字,每移动一位就以下一位为起点做相同的处理,直到所有数字循环了一遍,那排列的工作也就完成了。一个具体的实现如下:

/*
 * @param r:     需要求其排列的向量
 * @param iPos:  当前所进行到的位置
 * 程序体中的注释表示处于那个位置的向量都是一个新的且唯一的排列
*/
void rotate(vector<int>& r, int iPos) {

    if(iPos == r.size() - 1)//是否循环完毕,调用函数时 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)//循环前移
            r[j] = r[j + 1];
        r[r.size() - 1] = t;

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

        rotate(r, iNextPos);//从下一位数字开始新的位移
    }
}
   这种方法不要求数字式连续的,也不用事先规定好向量的长度。只是当向量长度到了一定的时候,运算时间会很长!其它方法未知……
   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 崇文 阅读(1813) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理