### Lexicographic permutations using Algorithm L (STL next_permutation in Python)

One of the more useful functions in the C++ Standard Library is next_permutation in <algorithm>. The STL function has a desirable property that almost every other permutation generating functions I’ve seen lack, namely lexicographic awareness of the elements being permuted.

A typical function will, given a sequence of elements such as (1, 1, 2, 2), permute on indices only. This will in our case give 4! permutations, which is often not what we want. The STL implementation will “correctly” generate only unique permutations, in our case 4! / 2!2!, and also generate them in the right order.

What’s special about most STL implementations is the use of a fairly unknown algorithm for finding permutations in lexicographic order. A canonical templated implementation is usually about 25 lines of code. It is also non-recursive and very fast.

Here’s a Python implementation of next_permutation with user-defined comparison. Use freely.

```
def next_permutation(seq, pred=cmp):
"""Like C++ std::next_permutation() but implemented as
generator. Yields copies of seq."""
def reverse(seq, start, end):
# seq = seq[:start] + reversed(seq[start:end]) + \
# seq[end:]
end -= 1
if end <= start:
return
while True:
seq[start], seq[end] = seq[end], seq[start]
if start == end or start+1 == end:
return
start += 1
end -= 1
if not seq:
raise StopIteration
try:
seq[0]
except TypeError:
raise TypeError("seq must allow random access.")
first = 0
last = len(seq)
seq = seq[:]
# Yield input sequence as the STL version is often
# used inside do {} while.
yield seq
if last == 1:
raise StopIteration
while True:
next = last - 1
while True:
# Step 1.
next1 = next
next -= 1
if pred(seq[next], seq[next1]) < 0:
# Step 2.
mid = last - 1
while not (pred(seq[next], seq[mid]) < 0):
mid -= 1
seq[next], seq[mid] = seq[mid], seq[next]
# Step 3.
reverse(seq, next1, last)
# Change to yield references to get rid of
# (at worst) |seq|! copy operations.
yield seq[:]
break
if next == first:
raise StopIteration
raise StopIteration
```

Example:

```
>>> for p in next_permutation([1, 1, 2, 2]):
print p,
[1, 1, 2, 2] [1, 2, 1, 2] [1, 2, 2, 1] [2, 1, 1, 2] [2, 1, 2, 1] [2, 2, 1, 1]
```

An important question is: how does the code work, and why? Not surprisingly, the man with the answers is Donald Knuth. This algorithm doesn’t appear to have a proper name, so Knuth simply calls it Algorithm L. This algorithm is described in *The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations*. Algorithm L works like this, using a slightly different explanation than Knuth that I hope will be easier to understand.

Algorithm L: Given a sequence of n elements a_{0}, a_{1}, …, a_{n-1} generate all permutations of the sequence in lexicographically correct order.

Step 1 (Step L2 in Knuth): Partition the sequence into two sequences a_{0}, a_{1}, …, a_{j} and a_{j+1}, a_{j+2}, …, a_{n-1} such that we have already generated all permutations beginning with a_{0}, a_{1}, …, a_{j}. This can by done by decreasing j from n-2 until a_{j} < a_{j+1}. If j = 0 we are done.

For example, the input sequence 1, 4, 3, 2 is split into the sequence 1 and the sequence 4, 3, 2. Obviously, there are no more lexicographic permutations beginning with 1 when the second sequence is in decreasing order.

Step 2a (Step L3 in Knuth): In the second sequence a_{j+1}, a_{j+2}, …, a_{n-1} working backwards, find a_{m}, the first value larger than a_{j}. We find a_{m} by setting m to n-1 and decreasing until a_{j} < a_{m}.

Step 2b: Swap a_{j} and a_{m}.

For example, our two sequences are 1 and 4, 3, 2. As the second sequence is decreasing because of the first step, a_{m} is the smallest element greater than a_{j} that can legitimately follow a_{0}, a_{1}, …, a_{j-1} in a permutation.

Step 3 (Step L4 in Knuth): Reverse a_{j+1}, a_{j+2}, …, a_{n-1}.

Here are some examples of the steps on (1, 2, 3, 4) that should clarify step 2a, 2b and 3:

(1, 2, 3, 4) >> (1, 2, 3), (4) >> (1, 2, 4), (3) >> (1, 2, 4), (3) >> (1, 2, 4, 3) (1, 2, 4, 3) >> (1, 2), (4, 3) >> (1, 3), (4, 2) >> (1, 3), (2, 4) >> (1, 3, 2, 4) (1, 3, 2, 4) >> (1, 3, 2), (4) >> (1, 3, 4), (2) >> (1, 3, 4), (2) >> (1, 3, 4, 2) (1, 3, 4, 2) >> (1, 3), (4, 2) >> (1, 4), (3, 2) >> (1, 4), (2, 3) >> (1, 4, 2, 3)

Here are some examples on the sequence (1, 2, 2, 3):

(1, 2, 2, 3) >> (1, 2, 2), (3) >> (1, 2, 3), (2) >> (1, 2, 3), (2) >> (1, 2, 3, 2) (1, 2, 3, 2) >> (1, 2), (3, 2) >> (1, 3), (2, 2) >> (1, 3), (2, 2) >> (1, 3, 2, 2) (1, 3, 2, 2) >> (1), (3, 2, 2) >> (2), (3, 2, 1) >> (2), (1, 2, 3) >> (2, 1, 2, 3)

Algorithm L is a fairly simple algorithm and it's also easy to understand and implement. Permutation generation is sometimes used as an interview question because it's difficult to get right even though the underlying problem is easy to grasp. It can thus be useful to know even for those not interested in combinatorics.

## 12 Comments:

What if I have array= (a,b,c) and I want to have array of array contains {(a,b,c),(a,c),(a,b),(b,c),(a),(b),(c)}

mia: There are some neat algorithms to create the power set (all subsets). Here are two implementations in both Python and Smalltalk: http://smalltalk.gnu.org/blog/bonzinip/fun-generators

This comment has been removed by the author.

I was looking for this a while ago, could find it in other languages but not python. This is very useful, have just solved some problems using this code.

Cheers.

See:

http://code.google.com/codejam/contest/dashboard?c=186264#s=p1

:-)

小さいサイズ

コーヒー焙煎

先物

エステ 表参道

福生市 不動産

募金

世田谷 マンション

ピアノ教室

RMT

リロケーション 賃貸

過払い

フランチャイズ 起業

婚活 相談

フランチャイズ 開業

大井町線 中古マンション

園芸用品

飲食 転職

通販 ファッション

ダイビング スクール

港区 不動産

生理不順 漢方

クロエ 財布

店舗設計

皮膚科 立川

ニキビ跡 治療

簿記 通信講座

朝霞 一戸建て

子宮がん

乳がん

賃貸オフィス

英会話 横浜

toeic

結婚カウンセリング

お見合いパーティー 東京

和光市 不動産

我孫子市 不動産

足立区 不動産

蕨市 不動産

埼玉県 一戸建て

海水魚販売

東横線 不動産

賃貸オフィス

エアコン 取り外し

ヴィトン バッグ

インテリア 家具

離婚

株式 投資顧問

J-Payment

カップリング

アヴァンス

納骨堂

マウイ島

オフィスレイアウト

ホームヘルパー

バイク買取

03発信

映像制作会社

任意整理 無料相談

スライドショー

注目株

オメガ 修理

USB

折込

老人ホーム 川崎

恵比寿 アパート

整体カイロプラクティック

業務用 厨房機器

当日配達

賃貸川西市

自己破産

ECサイト ASP

楽器レンタル

教員採用

司法書士 債務整理

エアコン 東京

名古屋 債務整理

浦和 不動産

you knowマンベアピグ?

it's manbearpig!!

jimmy black shoes

jimmy choo sandals

jimmy choo high

jimmy choo pumps

jimmy choo wedding shoes

buty jimmy choo

jimmy choo skor

jimmy choo booties

shopping jimmy choo

my jimmy choos

jimmy choos heels

DISCOUNT JIMMY CHOO

jimmy choo handbags

JIMMY CHOO

JIMMY CHOO shoes

jimmy choos

Christian Louboutin - Declic leather

pumps

Manolo Blahnik Something Blue Satin

Pump

Manolo Blahnik Satin Jeweled d'Orsay

Pump

mcqueen shoes

alexander mcqueen heels

Alexander McQueen Store

Jimmy Choo sale

Replica jimmy choo shoes

manolo blahnik online store

manolo shoes

manolo blahnik sale

replica christian louboutin shoes

discount christian louboutin shoes

alexander mcqueen shoes

jimmy choo outlet

jimmy choos

jimmy shoes

Manolo Blahnik Shoes

christian shoes

black boots

Chocolate boots

sand boots

Chestnut boots

gray boots

pink boots

grey boots

pink boots

Is it OK that the algorithm uses `reverse` on each iteration. `Reverse~ is of `O(n)` complexity. This may slow down the whole algorithm.

Post a Comment

Subscribe to Post Comments [Atom]

<< Home