出道题。perfectPermutation - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

出道题。perfectPermutation

出道题。perfectPermutation# JobHunting - 待字闺中

t*r2015-03-03 08:03

1 楼

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 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.

t*r2015-03-03 08:03

2 楼

我的代码：
很糟糕，大数据过不去
应该可以用bitmap 优化一下今天懒得弄了
package topcoder;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
//B[0] = 0
//B[i] = A[B[i-1]], for every i between 1 and N-1, inclusive.
/*
* 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}
* */
public class PerfectPermutation {
private List> permRes = new LinkedList>();
public int reorder(int[] P){
getPermuation(P);
permRes.remove(0);
int ret = getMin();
return ret;
}

public int getMin(){
int minDiff = 51;
for(List perm : permRes){
List bArray = getBArray(perm);
int diffNums = getDiff(perm, bArray);
// System.out.println("diffNums is: "+diffNums);
if(diffNums < minDiff){
minDiff = diffNums;
}

}
return minDiff;
}

public int getDiff(List l1, List l2){
Collections.sort(l2);
Collections.sort(l1);
int ret = 0;
for(int i = 0; i < l1.size(); i++){
if(l1.get(i)!=l2.get(i)){
ret++;
}
}
return ret;
}
public List getBArray(List list){
List ret = new ArrayList();
ret.add(0);
for(int i = 1; i < list.size();i++){
ret.add(list.get(ret.get(i-1)));
}
return ret;
}
public void getPermuation(int[] p){
perm(p,0 );
}

private void perm(int[] num, int idx){
for(int i = idx; i < num.length; i++){
int temp = num[i];
num[i] = num[idx];
num[idx] = temp;
perm(num, idx + 1);
temp = num[i];
num[i] = num[idx];
num[idx] = temp;
}
if(idx == num.length-1){

permRes.add(convert(num));
}
}
private List convert(int[] num){
List res = new ArrayList<>();
for(int i = 0; i < num.length; i++){
res.add(num[i]);
}
return res;
}

public static void main(String[] args){
PerfectPermutation pp = new PerfectPermutation();
// int[] p = {2,0,1};
// int ret = pp.reorder(p);
// System.out.println(ret); //0
//
//
// int[] p2 = {2,0,1,4,3};
// int ret2 = pp.reorder(p2);
// System.out.println(ret2); //2

int[] p3 = {0, 5, 3, 2, 1, 4};
int ret3 = pp.reorder(p3);
System.out.println(ret3); //3

}
}

x*y2015-03-03 08:03

3 楼

build a directed graph based on the input P, such that node i is connected
to node P[i]. Then, the minimum difference is (# of connected components - 1
).

T*72015-03-03 08:03

4 楼

import java.util.*;
public class PerfectPermutation {
public int reorder(int[] permutation) {
int result = 0;
int n = permutation.length;
boolean visit[] = new boolean[n];
for (int i = 0; i < n; ++ i) {
if (!visit[i]) {
int j = i;
do {
j = permutation[j];
System.out.println(j);
visit[j] = true;
} while (j != i);
for(int ii = 0; ii < visit.length; ii++){
System.out.print(visit[ii] + ";");
}
System.out.println();
result ++;
}
}
return result == 1? 0: result;
}

public static void main(String[] args){
PerfectPermutation pp = new PerfectPermutation();
int[] p = {2,0,1};
int ret = pp.reorder(p);
System.out.println("result: " + ret); //0

int[] p2 = {2,0,1,4,3};
int ret2 = pp.reorder(p2);
System.out.println("result: " + ret2); //2

int[] p3 = {0, 5, 3, 2, 1, 4};
int ret3 = pp.reorder(p3);
System.out.println("result: " + ret3); //3

}
}