Tuesday, October 2, 2007

Ranking and unranking permutations of multiset

Few years ago I started to play with my toy Cube21 programaticaly. I will probably write another article about that later. For that toy needed to get index of permutation of multiset (set with repetitions). I searched internet and was unable to find any algorithm which could do that. Best match I have found those days was Myrvold&Ruskey's Ranking of permutation. Very nice algo, but I needed multiset, so I developed one.

So, now I'm playing with toy again and decided to share my ranking algorithm with community.

This is C# class with two methods which are inverse. First will give you index of permutation, second permutation on index. You should initialize instance of class for particular multiset. Order of permutations is lexicographic. Also note, that this implementation operates on int data type, so it should be rewritten for bigger permutations.

Myrvold&Ruskey were able to create linear time algo (with number of set members). I tried hard, but for multiset I was unable to reach better time than circa O(n*(t/2)), where n is number of members and t is number of types of members (or members without repetitions).

I'm interested to learn more about topic, so please share your thoughts. Or if you have faster algo, please, let me know.

There is also zip file with whole VS solution.

Update More detailed explanation.

No comments: