The generation of permutations through GDD


Dragan Janković, Milena Stanković




In this paper we consider the generation of permutations, i.e. all ordered $n$-tuples of different elements from the set $A_n=\{a_0,a_1,\ldots,a_{n-1}\}$ which is a combinatorial problem often occurring in practice. We give a method for the generation of all permutations of n given items through generalized decision diagrams. Each of $n!$ paths in the appropriate decision diagram maps into one of $n!$ permutations. The proposed method is suitable for generating all permutations for direct generation of only one permutation without generating and saving preceding permutations. Our method provides efficient hardware realization.