Generating order combinations

Factual Questions
1

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.

2

Counting?

3

It’s just n factorial (represented as n!), which is n * (n-1) * (n-2) * … * 1.

4

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

5

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):


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:


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.

6

Omphaloskeptic, your pseudocode looks a lot like Python. :slight_smile:

7

Robert Sedgewick wrote a comparative paper (downloadable as a PDF from here) on generating permutations. It’s from 1977, but should still be useful now.

From the abstract:

8

We’ve secretly replaced the fine pseudocode we usually serve with executable Python scripts. Let’s see if anyone can tell the difference!