Date: Mon Oct 17 16:43:08 2011
Authors: Jun Kawahara, Toshiki Saitoh, Ryo Yoshinaka and Shin-ichi Minato
Abstract. A primitive sorting network is a fundamental computational model which is important both in mathematics and in engineering to operate permutations. In this paper, we propose an efficient method to count the number of ways to construct minimum primitive sorting networks. We developed PiDD vector, a new data structure to represent and manipulate multisets of permutations, based on PiDDs, which are recently proposed by Minato. We succeeded in calculating the number 2,752,596,959,306,389,652 for n=13, which has not been known in the past, where n is the width of the primitive sorting network.
©Copyright 2011 Authors