TCS-TR-A-11-54

Date: Mon Oct 17 16:43:08 2011

Title: Counting Primitive Sorting Networks by PiDDs

Authors: Jun Kawahara, Toshiki Saitoh, Ryo Yoshinaka and Shin-ichi Minato

Contact:

First name: Jun
Last name: Kawahara
Address: ERATO Minato Project, Graduate School of Information Science and Technology, Hokkaido University, Kita 14, Nishi 9, Kita-ku, Sapporo, Hokkaido, 060-0814, Japan
Email: jkawahara@erato.ist.hokudai.ac.jp

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.