Quantcast

Maximum PC

It is currently Wed Aug 20, 2014 12:56 pm

All times are UTC - 8 hours




Post new topic Reply to topic  [ 4 posts ] 
Author Message
 Post subject: Ambiguous Permutations
PostPosted: Sat Jul 02, 2005 9:44 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

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++)
            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. :)


Top
  Profile  
 
 Post subject:
PostPosted: Wed Jul 06, 2005 7:33 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

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


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

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


Top
  Profile  
 
 Post subject:
PostPosted: Fri Jul 08, 2005 12:52 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

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
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 4 posts ] 

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 7 guests


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

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group