Content deleted Content added
created page |
No edit summary |
||
Line 1:
In computational [[combinatorics]], a '''loopless algorithm''' or '''loopless imperative algorithm''' is an [[imperative programming|imperative]] [[algorithm]] which 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.|month=July|year=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|url=http://dx.doi.org/10.1145/321765.321781}}</ref><ref>{{cite book|author=[[Donald Knuth|Knuth, D.]]|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.]]|month=February|year=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 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=[[Richard Bird (computer scientist)|Bird, R.]]|year=2006|month=July|title=Loopless functional algorithms|url=http://dx.doi.org/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.]]|month=September|year=2005|series=Master's thesis|oclc=63162239}}</ref> The standard [[subroutine|function]] ''unfoldr'' is a right-associative [[Richard Bird (computer scientist)|Bird]] [[anamorphism|unfold]].<ref name="bird06"/>
| |||