# Generating order combinations **URL:** \ **Category:** Factual Questions\ **Created:** [December 11, 2007, 8:09pm UTC](https://boards.straightdope.com/t/generating-order-combinations/429647 "2007-12-11T20:09:06Z")\ **Posts on this page:** 8\ **Page:** 1
**Author:** ![VunderBob](https://avatars.discourse-cdn.com/v4/letter/v/839c29/32.png) [@VunderBob](https://boards.straightdope.com/u/VunderBob)\ **Post date:** [December 11, 2007, 8:09pm UTC](https://boards.straightdope.com/t/generating-order-combinations/429647/1 "2007-12-11T20:09:06Z")
Is there either a simple formula or multistep algorithm that can generate a set of all possible unique orderings of _n_ digits? I can do it manually for up to four digits, but I get way confused once _n_ is 5 or bigger, and I want to set up a 2d array as a function of _n_. ---
**Author:** ![Squink](https://avatars.discourse-cdn.com/v4/letter/s/b5e925/32.png) [@Squink](https://boards.straightdope.com/u/Squink)\ **Post date:** [December 11, 2007, 8:40pm UTC](https://boards.straightdope.com/t/generating-order-combinations/429647/2 "2007-12-11T20:40:36Z")
Counting? ---
**Author:** ![sturmhauke](https://avatars.discourse-cdn.com/v4/letter/s/e47c2d/32.png) [@sturmhauke](https://boards.straightdope.com/u/sturmhauke)\ **Post date:** [December 11, 2007, 8:43pm UTC](https://boards.straightdope.com/t/generating-order-combinations/429647/3 "2007-12-11T20:43:15Z")
It’s just n factorial (represented as n!), which is n \* (n-1) \* (n-2) \* … \* 1. ---
**Author:** ![VunderBob](https://avatars.discourse-cdn.com/v4/letter/v/839c29/32.png) [@VunderBob](https://boards.straightdope.com/u/VunderBob)\ **Post date:** [December 11, 2007, 11:38pm UTC](https://boards.straightdope.com/t/generating-order-combinations/429647/4 "2007-12-11T23:38:30Z")
[QUOTE=sturmhauke] It’s just n factorial (represented as n!), which is n \* (n-1) \* (n-2) \* … \* 1. [/QUOTE] No, I’m trying to generate the actual order combinations, not count them. 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1 ---
**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\ **Post date:** [December 11, 2007, 11:44pm UTC](https://boards.straightdope.com/t/generating-order-combinations/429647/5 "2007-12-11T23:44:32Z")
There are lots of ways for enumerating all permutations (Knuth’s forthcoming _The Art of Computer Programming, Vol. 4A_ talks at great length about combinatorial enumeration). One conceptually simple way is to initialize an array with n placeholders (say, zeroes) and then recursively place each digit 1, …, n in an empty space. That is (in Python, which is hopefully somewhat readable as pseudocode): ```auto def place(p,n,k): if k>n: # p is a permutation; do something with it print p return for i in range(0,n): if p*==0: p* = k place(p,n,k+1) p* = 0 return p = [0]*n place(p,n,1) ``` This is inefficient in a couple of ways: First, it has to keep looking through the array p for empty places; second, when it completes the permutation it uses an n-nested recursive stack to maintain its state for iteration. This is not a problem if you want to save the whole array of permutations, but means that iterating in constant memory requires that you put the loop block inside place() (or call it from there), which is an ugly way of iterating. A nicer way starts with an array [1,…,n] and iterates by permuting elements of the existing array; this requires no state beyond the current permutation, so it gives more elegant implementations. One way to do this is to find the reverse-sorted tail of the array (the elements at the end of the array which are in decreasing order), reverse it, and swap the element preceding this tail with the smallest of the tail elements larger than it: ```auto def nextperm(p): i = len(p) while i>1: i -= 1 if p*>p[i-1]: break pt = p[i:] pt.reverse() p[i:] = pt p1 = filter(lambda x:x>p[i-1],pt) if len(p1)==0: return 0 p1 = p1[0] p[p.index(p1)] = p[i-1] p[i-1] = p1 return 1 p = range(1,n+1) while 1: # use permutation p print p if not nextperm(p): break ``` There are more efficient ways, but this is maybe enough to give a general idea. ---
**Author:** ![Derleth](https://avatars.discourse-cdn.com/v4/letter/d/b9e5f3/32.png) [@Derleth](https://boards.straightdope.com/u/Derleth)\ **Post date:** [December 12, 2007, 3:55pm UTC](https://boards.straightdope.com/t/generating-order-combinations/429647/6 "2007-12-12T15:55:20Z")
**Omphaloskeptic** , your pseudocode looks a lot like Python. 🙂 ---
**Author:** ![Bytegeist](https://avatars.discourse-cdn.com/v4/letter/b/9dc877/32.png) [@Bytegeist](https://boards.straightdope.com/u/Bytegeist)\ **Post date:** [December 12, 2007, 4:59pm UTC](https://boards.straightdope.com/t/generating-order-combinations/429647/7 "2007-12-12T16:59:06Z")
Robert Sedgewick wrote a comparative paper (downloadable as a PDF from [here](http://portal.acm.org/citation.cfm?id=356692)) on generating permutations. It’s from 1977, but should still be useful now. From the abstract: > [@](#): > > This paper surveys the numerous methods that have been proposed for permutation enumeration by computer. The various algorithms which have been developed over the years are described in detail, and implemented in a modern ALGOL-like language. ---
**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\ **Post date:** [December 13, 2007, 7:28pm UTC](https://boards.straightdope.com/t/generating-order-combinations/429647/8 "2007-12-13T19:28:56Z")
[QUOTE=Derleth] **Omphaloskeptic** , your pseudocode looks a lot like Python. 🙂 [/QUOTE] _We’ve secretly replaced the fine pseudocode we usually serve with executable Python scripts. Let’s see if anyone can tell the difference!_