TCS-TR-A-11-50

Date: Mon Feb 21 10:16:09 2011

Title: PiDD: A New Decision Diagram for Manipulating Sets of Permutations

Authors: Shin-ichi Minato

Contact:

  • First name: Shin-ichi
  • Last name: Minato
  • Address: Graduate School of Information Science and Technology, Hokkaido University, North 14 West 9, Sapporo, 060-0814, Japan.
  • Email: minato@ist.hokudai.ac.jp

Abstract. Permutations and combinations are a couple of basic concepts in elementary combinatorics. Permutations appear in various problems such as sorting, ordering, matching, coding, and many other real-life situations. While conventional SAT problems are discussed in combinatorial space, considering ``permutatorial'' SAT or CSPs is also an interesting and practical research topic. In this paper, we propose a new decision diagram ``PiDD,'' for compact and canonical representation of a {\em set of permutations}. Similarly to ordinary BDD or ZDD, PiDD has efficient algebraic set operations such as union, intersection, etc. In addition, PiDD has a special Cartesian product operation to generate all possible composite permutations for given two sets of permutations. This is a beautiful and powerful property of PiDDs. We present two application examples of PiDDs: designing permutation networks and analysis of Rubik's Cube. The experimental results show that PiDD-based method can explore billions of permutations in a feasible time and space, using simple algebraic operations for solving the problems.


©Copyright 2011 Authors