TCS-TR-A-11-50Date: Mon Feb 21 10:16:09 2011 Title: PiDD: A New Decision Diagram for Manipulating Sets of Permutations Authors: Shin-ichi Minato Contact:
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 |