This was a fairly easy problem from a recent Sphere programming contest. Most everyone here should be able to solve it - GamerFreak, take a break from the OS and do this one.
There are three different types of permutations:
Regular permutations. Examples...
1 2 3 4 5
3 2 5 4 1
4 3 1 5 2
Inverse Permutations. These are based on a regular permutation and tell you where the number at a given index is located in the regular permutation. Examples...
reg: 1 3 2 inv: 1 3 2
reg: 2 3 1 inv: 3 1 2
reg: 2 1 3 5 4 inv: 2 1 3 4 5
reg: 1 inv: 1
Ambiguous Permutations. These are permutations where the regular and inverse permutation are the same.
reg 1 2 3 inv 1 2 3 - ambiguous
reg 3 2 1 inv 3 2 1 - ambiguous
reg 1 3 2 inv 1 3 2 - ambiguous
reg 3 1 2 inv 2 3 1 - not ambiguous
Input file format:
3 - permutation size
1 2 3 - permutation
3 - permutation size
2 1 3 - permutation
0 - input terminator
Here is an example...
Code:
input:
4
1 4 3 2
5
2 3 4 5 1
1
1
7
6 3 7 2 1 4 5
5
4 1 3 2 5
5
1 3 5 4 2
5
2 5 3 1 4
5
2 5 1 3 4
0
output:
ambiguous
not ambiguous
ambiguous
not ambiguous
not ambiguous
not ambiguous
not ambiguous
not ambiguous
As I said, the problem isn't very hard. A simple brute force solution can be done in under 20 minutes. However, the contest imposed a pretty serious cpu time limit on the problem. The input file could have up to 50,000 permutations each of which were anywhere from 1 to 100000 in size which had to be processed in under 10 seconds (and these guys use some pretty old hardware to run their tests)! After fiddling with it for some time, I was able to reduce my orginal runtime by a factor of 7, but I still don't think it is quite fast enough for a successful contest submission.
On my work computer, I am able to process 100 permutations of 100,000 length in just under 4 seconds using basically a brute force algorithm (make that 3.1 seconds using the jvm -server flag). My work machine has the worlds worst virus scanner constantly runnign in the background, so I'm not sure about how good or bad that time is. I would be interested in seeing some other solutions and their times. Here is a bit of code to generate the permutations... note: this peice of code takes a little bit of time to generate the permutations.
Code:
import java.util.*;
/*
* GenerateAmiguousPermutations.java
*
* Created on July 2, 2005, 8:08 PM
*/
/**
*
* @author Larry Hignight
*/
public class GenerateAmbiguousPermutations {
public static void main(String[] args) {
if (args.length != 3) {
System.out.println("usage: number of permutations, maximum permutation size, minimum permutation size");
System.exit(-1);
}
int num = Integer.parseInt(args[0]);
int max = Integer.parseInt(args[1]);
int min = Integer.parseInt(args[2]);
for (int i = 0; i < num; i++) {
int size = max;
if (min != max) {
do {
size = (int) (Math.random() * max + 1);
} while (size < min);
}
ArrayList perm = createPermutation(size);
String s = perm.toString().replaceAll("[\\[\\],]","");
System.out.println(size);
System.out.println(s);
}
System.out.println("0");
System.exit(0);
}
public static ArrayList createPermutation(int size) {
ArrayList al = new ArrayList();
for (int i = 0; i < size; i++)
al.add(new Integer(i + 1));
Collections.shuffle(al);
return al;
}
}
Probably a better problem to reduce the variability in time due to the randomness of the permutation file generator would be a program that returns the number of ambiguous permutations for all permutations of a given length. Example...
n = 2
perms: 12, 21
inverse: 12, 21
return 2
n=3
perms: 123, 132, 213, 231, 312, 321
inverse: 123, 132, 213, 312, 231, 321
returns 4
Have fun.
Login
Register
FAQ
Search
© 2010 Future US, Inc. All rights reserved.