Loopless algorithm: Difference between revisions

Revision as of 02:07, 14 March 2015

Latest revision as of 18:35, 13 August 2023

(2 intermediate revisions by 2 users not shown)

Line 1:

In computational [[combinatorics]], a '''loopless algorithm''' or '''loopless imperative algorithm''' is an [[imperative programming|imperative]] [[algorithm]] that generates successive combinatorial objects, such as [[partition of a set|partitions]], [[permutation]]s, and [[combination]]s, in [[constant time]] and the first object in [[linear time]].<ref name="ehrlich73">{{cite journal|author=Ehrlich, G.|date=July 1973|title=Loopless algorithms for generating permutations, combinations, and other combinatorial configuration|journal=[[Journal of the ACM]]|publisher=[[Association for Computing Machinery|ACM]]|___location=[[New York City|New York, N.Y.]]|volume=20|issue=3|pages=500–513|issn=0004-5411|doi=10.1145/321765.321781|doi-access=free}}</ref><ref>{{cite book|author=[[Donald Knuth|Knuth, D.]]|author-link=Donald Knuth|title=Volume 4, Fascicle 2: Generating All Tuples and Permutations|publisher=[[Addison–Wesley|Addison–Wesley Professional]]|___location=[[Upper Saddle River, New Jersey|Upper Saddle River, N.J.]]|date=February 2005|series=[[The Art of Computer Programming]]|isbn=0-201-85393-0}}</ref> The objects must be immediately available in simple form without requiring any additional steps.<ref name="ehrlich73"/>

A '''loopless functional algorithm''' is a [[functional programming|functional]] algorithm that takes the form ''unfoldr step • prolog'' where ''step'' takes constant time and ''prolog'' takes linear time in the size of the input.<ref name="bird06">{{cite conference|author=[[Bird, R.|author-link=Richard Bird (computer scientist)|Bird, R.]]|date=July 2006|title=Loopless functional algorithms|doi=10.1007/11783596|conference=International Conference on Mathematics of Program Construction (MPC 06)|publisher=[[Springer Science+Business Media|Springer]].|___location=[[Heidelberg]], [[Germany]]}}</ref><ref>{{cite book|author=Snape, J.|title=Loopless Functional Algorithms|publisher=[[University of Oxford]]|___location=[[Oxford]], [[United Kingdom|U.K.]]|date=September 2005|series=Master's thesis|oclc=63162239|url=https://wwwx.cs.unc.edu/~snape/publications/msc/}}</ref> The standard [[subroutine|function]] ''unfoldr'' is a right-associative [[Richard Bird (computer scientist)|Bird]] [[anamorphism|unfold]].<ref name="bird06"/>

==References==

{{reflistReflist}}

[[Category:Combinatorial algorithms]]

{{Combin-stub}}