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


  • 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:

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