# Maximum PC

 It is currently Tue Apr 21, 2015 11:10 am

 All times are UTC - 8 hours

 Page 1 of 1 [ 4 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Ambiguous PermutationsPosted: Sat Jul 02, 2005 9:44 pm
 Bitchin' Fast 3D Z8000*

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
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++)

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.

Top

 Post subject: Posted: Wed Jul 06, 2005 7:33 pm
 Bitchin' Fast 3D Z8000*

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
No one?! Oh come on!!!!

Top

 Post subject: Posted: Fri Jul 08, 2005 11:46 am
 Team Member Top 100

Joined: Fri Sep 17, 2004 5:35 pm
Posts: 1176
Too long for me to read :-p

Top

 Post subject: Posted: Fri Jul 08, 2005 12:52 pm
 Bitchin' Fast 3D Z8000*

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Kybo_Ren wrote:
Too long for me to read :-p

Man... I figured you'd be chomping at the bit to unleash a seriously fast C++ version of this too.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 4 posts ]

 All times are UTC - 8 hours

#### Who is online

Users browsing this forum: No registered users and 2 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Maximum FAQs    Forum Rules, Posting Guidelines & Announcements    The Good, The Bad & The Banned    FAQs Help/Do It Yourself    PC Building Lab    The Help Desk    PC Modding    Education & Certification Hardware    Nuts & Bolts    Portable Talk    Appraisals, Deals & Bargains (oh my!) OS/Software/Programming    Windows Parlor    Alt.OS.Abode    Games Arena    Programmers' Paradise Networking/Internet    Internet Truckstop    Network Nook In/Out    Magazine and Book Feedback    Forum & Website Feedback    Dog Pound Team Maximum PC Folding at Home    Team Maximum PC - Folding at Home - FIND CURES TO DISEASES    Team MPC - Folding Gauntlets