Constant Time Generation of Linear Extensions

摘要

Given a poset P, several algorithms have been proposed for generating all linear extensions of P. The fastest known algorithm generates each linear extension in constant time "on average". In this paper we give a simple algorithm which generates each linear extension in constant time "in worst case". The known algorithm generates each linear extension exactly twice and output one of them, while our algorithm generates each linear extension exactly once.