Ray Jinzhu Chen, PhD, Former Full Professor

The abstract (first page) of the accepted software

• R. J. Chen, K. S. Reschke and H. Hu, "Design and Analysis of  a Tree-Backtracking Algorithm for Multiset and Pure Permutations  ," International Workshop on Combinatorial Algorithms ( IWOCA 2012 ), Kalasalingam University, India, LNCS 7643, pp. 288-292 , July 19-21, 2012. Our open source soltion code

Design and Analysis of a Tree-Backtracking Algorithm for Multiset and Pure Permutations

Ray Jinzhu Chen¹, Kevin Scott Reschke², Hailong Hu³

¹ Endign, Dublin, OH USA

rchen@dataverify.com

²Department of Computer Science, Stanford University, Stanford, CA, USA

³Software School, Xiamen University, Xiamen, China

Abstract. A tree-backtracking-based technique, permutation tree generation with Anterior-items-in-an-array for Remaining Distinct Elements (ARDE), is introduced for multiset and pure permutations. We analyze the algorithm at the assembly level and obtain its time formula for pure permutations. We mathematically prove that our time formula is 11.5% faster than the corresponding formula of the previous fastest algorithm for pure permutations for any length N > 3. We also offer related source codes and executable files on our website for others to use.