Permutation Generation Methods

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Permutation Generation Methods

Full text

Pdf (1.60 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 9 , Issue 2 (June 1977) table of contents

Pages: 137 - 164

Year of Publication: 1977

ISSN:0360-0300

Author

Robert Sedgewick

Program in Computer Science and Division of Applied Mathematics, Brown University, Providence, Rhode Island

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 45, Downloads (12 Months): 289, Citation Count: 7

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/356689.356692 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BOOTHROYD, J "PERM (Algorithm 6)," Computer Bulletin 9, 3 (Dec. 1965), 104
	2	BOOTHROYD, J. "Permutation of the elements of a vector (Algomthm 29)"; and "Fast permutation of the elements of a vector (Algorithm 30)," Computer J. 10 (1967), 310-312.
	3	P. Bratley, Algorithm 306: permutations with repetitions, Communications of the ACM, v.10 n.7, p.450-451, July 1967 [doi>10.1145/363427.363473]
	4	Cove, YOU, R R.; AND SULLrVAN, J. G. "Permutahon (Algorithm 71)," Comm. ACM 4, 11 (Nov 1961), 497.
	5	DERSHOWITZ, N. "A simplified loop-free algorithm for generating permutatlous," BIT 15 (1975), 158-164.
	6	Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
	7	DIJKSTRA, E. W "On a gauntlet thrown by David Gries," Acta Informatica 6, 4 (1976), 357.
	8	Richard Durstenfeld, Algorithm 235: Random permutation, Communications of the ACM, v.7 n.7, p.420, July 1964 [doi>10.1145/364520.364540]
	9	EAVES, B. C "Permute (Algorithm 130)," Comm. ACM 5, 11 (Nov. 1962), 551 (See also: remarks by R. J. Ord-Smith in Comm ACM 10, 7 (July, 1967), 452-3)
	10	Gideon Ehrlich, Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations, Journal of the ACM (JACM), v.20 n.3, p.500-513, July 1973 [doi>10.1145/321765.321781]
	11	Gideon Ehrlich, Algorithm 466: four combinatorial algorithm [G6], Communications of the ACM, v.16 n.11, p.690-691, Nov. 1973 [doi>10.1145/355611.362541]
	12	EWN, S. Algorthmic combinatorics, Macmillan, Inc., N.Y., 1973.
	13	FIKE, C T. "A permutation generation method," Computer J 18, 1 (Feb. 1975), 21-22.
	14	FISCHER, L. L.; AND KRAUSE, K. C, Lehrbuch der Combinationslehre und der Arithmetic, Dresden, 1812
	15	HALL, M.; ANDKNUTH, D.E. "Combinatorial analysis and computers," American Math. Monthly 72, 2 (Feb. 1965, Part II), 21-28.
	16	HEAP, B R. "Permutations by Interchanges," Computer J. 6 (1963), 293-4.
	17	HOWELL, J R. "Generation of permutations by addition,"Math. Comp 16 (1962), 243-44
	18	R. J. Ord-Smith, Remarks on algorithm 87, 102, 130, 202: generation of permutations in lexicographical order, Communications of the ACM, v.10 n.7, p.452-453, July 1967 [doi>10.1145/363427.363482]
	19	F. M. Ives, Permutation enumeration: four new permutation algorithms, Communications of the ACM, v.19 n.2, p.68-72, Feb. 1976 [doi>10.1145/359997.360002]
	20	JOHNSON, S.M. "Generation of permutations by adjacent transposition," Math. Comp. 17 (1963), 282-285.
	21	KNUTH, D.E. "Fundamental algorithms," in The art of computer programming 1, Addison- Wesley, Co., inc., Reading, Mass., 1968.
	22	KNUTH, D.E. "Seminumerlcal algorithms," in The art of computer programming 2, Addison-Wesley, Co., inc., Reading, Mass., 1969.
	23	KNUTH, D. E "Sorting and searching," in The art of computer programmtng 3, Addison- Wesley, Co., Inc, Reading, Mass, 1972
	24	Donald E. Knuth, Structured Programming with go to Statements, ACM Computing Surveys (CSUR), v.6 n.4, p.261-301, Dec. 1974 [doi>10.1145/356635.356640]
	25	B. E. Rodden, Letters to the editor: In defense of Langdon's algorithm, Communications of the ACM, v.11 n.3, p.150, March 1968 [doi>10.1145/362929.362965]
	26	LEHMER, D H. "Teaching combinatorial tricks to a computer," in Proc. of Symposium Appl. Math ,Combtnatortal Analysis, Vol. 10, American Mathematical Society, Providence, R.I, 1960, 179-193.
	27	LEHMER, D.H. "The machine tools of combinatories," in Applied combinatorial mathematws (E. F. Beckenbach, {Ed.}), John Wiley, & Sons, Inc., N Y, 1964
	28	LEHMER, D.H. "Permutation by adjacent interchanges," Amerwan Math. Monthly 72, 2 (Feb. 1965, Part II), 36-46.
	29	ORD-SMITH, R J. "Generation of permutation sequences Part 1," Computer J. 13, 3 (March 1970), 152-155.
	30	ORD-SMITH, R. J. "Generation of permutation sequences: Part 2," Computer J. 14, 2 (May 1971), 136-139.
	31	Lyle B. Smith, Remark on algorithm 178 [E4]: direct search, Communications of the ACM, v.12 n.11, p.638, Nov. 1969 [doi>10.1145/363269.363624]
	32	I. M. Leitch, Certification of algorithm 323 [G6]: generation of permutations in lexicographic order, Communications of the ACM, v.12 n.9, p.512, Sept. 1969 [doi>10.1145/363219.363230]
	33	PECK, J E. L; AND SCHRACK, G F "Permute (Algorithm 86)," Comm. ACM 5, 4 (April 1962), 208.
	34	PHmLmS, J. P.N. "Permutation of the elements of a vector in lexicographic order (Algorithm 28)," Computer J. 1O (1967), 310-311
	35	PLESZCZYNSKL S. "On the generation of permutations," Informatmn Processtng Letters 3, 6 (July 1975), 180-183.
	36	RIORDAN, J. An introduction to combinatortal analysis, John Wiley & Sons, Inc., N.Y., 1958.
	37	ROHL, J.S., "Programming improvements to Fike's algorithm for generating permutations," Computer J. 19, 2 (May 1976), 156
	38	ROBXNSON, C. L. "Permutation (Algorithm 317)," Comm. ACM 10, 11 (Nov. 1967), 729.
	39	T. W. Sag, Algorithm 242: Permutations of a set with repetitions, Communications of the ACM, v.7 n.10, p.585, Oct. 1964 [doi>10.1145/364888.364916]
	40	G. F. Schrack , M. Shimrat, Algorithm 102: Permutation in lexicographical order, Communications of the ACM, v.5 n.6, p.346, June 1962 [doi>10.1145/367766.368177]
	41	SHEN, M.-K "On the generation ofpermutatlons and combinations," BIT 2 (1962), 228- 231
	42	Mok-Kong Shen, Algorithm 202: generation of permutations in lexicographical order, Communications of the ACM, v.6 n.9, p.517, Sept. 1963 [doi>10.1145/367593.367601]
	43	SLOANE, N. J. A. A handbook of tnteger sequences, Academic Press, Inc, NY, 1973
	44	TOMPKIN8, C. "Machine attacks on problems whoso variables are permutations," in Proc Symposium zn Appl. Math., Numerwal Analysts, Vol 6, McGraw-Hill, Inc., N.Y., 1956, 195-211
	45	H. F. Trotter, Algorithm 115: Perm, Communications of the ACM, v.5 n.8, p.434-435, Aug. 1962 [doi>10.1145/368637.368660]
	46	WALKER, R. J "An enumerative technique for a class of combinatorial problems," in Proc Symposium in Appl. Math, Combtnatorial Analysts, Vol. 10, American Mathematical Society, Providence, R.I , 1960, 91
	47	WZLLS, M. B "Generation of permutations by transposition," Math Comp 15 (1961), 192- 195.
	48	WELLS, M. B. Elements of combtnatortal computtng, Pergamon Press, Elmsford, N.Y., 1971.
	49	WHITEHEAD, E. G. Combinatorial algorithms. (Notes by C. Frankfeldt and A. E. Kaplan) Courant Institute, New York Univ., 1973, 11-17.

CITED BY 7

	Robert L. Kruse, On teaching recursion, ACM SIGCSE Bulletin, v.14 n.1, p.92-96, February 1982
	Thomas W. Parsons, Surveyor's Forum: A Forgotten Generation of Permutations, ACM Computing Surveys (CSUR), v.9 n.4, p.315, Dec. 1977
	K. A. Redish , W. F. Smyth, Program style analysis: a natural by-product of program compilation, Communications of the ACM, v.29 n.2, p.126-133, Feb. 1986
	A. De Matteis , S. Pagnutti, Pseudorandom permutation, Journal of Computational and Applied Mathematics, v.142 n.2, p.367-375, 15 May 2002
	Jean-Luc Baril , Vincent Vajnovszki, Gray code for derangements, Discrete Applied Mathematics, v.140 n.1-3, p.207-221, 15 May 2004
	Hamdy S. Soliman , Mohammed Omari, Application of synchronous dynamic encryption system in mobile wireless domains, Proceedings of the 1st ACM international workshop on Quality of service & security in wireless and mobile networks, October 13-13, 2005, Montreal, Quebec, Canada
	Stephen Davies, "Why should i care?": making programming assignments relevant for non-majors, Journal of Computing Sciences in Colleges, v.23 n.3, p.90-97, January 2008