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. In this talk, we present a new decision diagram "PiDD," for
compact and canonical representation of a set of permutations. PiDD has
efficient algebraic set operations such as union, intersection, and
especially, it 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 the data
structures and the basic operation algorithms for PiDDs. We also show
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. We also hope that PiDDs will be useful for designing and
analyzing a kind of cryptographic systems.
|