Thursday, April 03, 2008

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 a0, a1, …, an-1 generate all permutations of the sequence in lexicographically correct order.

Step 1 (Step L2 in Knuth): Partition the sequence into two sequences a0, a1, …, aj and aj+1, aj+2, …, an-1 such that we have already generated all permutations beginning with a0, a1, …, aj. This can by done by decreasing j from n-2 until aj < aj+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 aj+1, aj+2, …, an-1 working backwards, find am, the first value larger than aj. We find am by setting m to n-1 and decreasing until aj < am.

Step 2b: Swap aj and am.

For example, our two sequences are 1 and 4, 3, 2. As the second sequence is decreasing because of the first step, am is the smallest element greater than aj that can legitimately follow a0, a1, …, aj-1 in a permutation.

Step 3 (Step L4 in Knuth): Reverse aj+1, aj+2, …, an-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:

Blogger mia said...

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

Wednesday, April 9, 2008 at 7:14:00 AM GMT+2  
Blogger Björn Edström said...

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

Thursday, April 10, 2008 at 2:28:00 AM GMT+2  
Blogger ted said...

This comment has been removed by the author.

Tuesday, February 17, 2009 at 10:53:00 PM GMT+1  
Blogger ted said...

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.

Tuesday, February 17, 2009 at 10:55:00 PM GMT+1  
Blogger Udi Oron said...

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

:-)

Saturday, September 12, 2009 at 11:37:00 PM GMT+2  
Blogger TUTU said...

小さいサイズ
コーヒー焙煎
先物
エステ 表参道
福生市 不動産
募金
世田谷 マンション
ピアノ教室
RMT
リロケーション 賃貸
過払い
フランチャイズ 起業
婚活 相談
フランチャイズ 開業
大井町線 中古マンション
園芸用品
飲食 転職
通販 ファッション
ダイビング スクール
港区 不動産
生理不順 漢方
クロエ 財布
店舗設計
皮膚科 立川
ニキビ跡 治療
簿記 通信講座
朝霞 一戸建て
子宮がん
乳がん
賃貸オフィス
英会話 横浜
toeic

Wednesday, November 25, 2009 at 3:23:00 PM GMT+1  
Blogger TUTU said...

結婚カウンセリング
お見合いパーティー 東京
和光市 不動産
我孫子市 不動産
足立区 不動産
蕨市 不動産
埼玉県 一戸建て
海水魚販売
東横線 不動産
賃貸オフィス
エアコン 取り外し
ヴィトン バッグ
インテリア 家具
離婚
株式 投資顧問
J-Payment
カップリング
アヴァンス
納骨堂
マウイ島
オフィスレイアウト
ホームヘルパー
バイク買取
03発信
映像制作会社
任意整理 無料相談
スライドショー
注目株 
オメガ 修理
USB
折込
老人ホーム 川崎
恵比寿 アパート
整体カイロプラクティック
業務用 厨房機器
当日配達
賃貸川西市
自己破産
ECサイト ASP
楽器レンタル
教員採用
司法書士 債務整理
エアコン 東京
名古屋 債務整理
浦和 不動産

Wednesday, November 25, 2009 at 3:23:00 PM GMT+1  
Blogger ハリソン said...

you knowマンベアピグ?
it's manbearpig!!

Monday, March 1, 2010 at 9:01:00 AM GMT+1  
Blogger radella said...

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

Wednesday, July 28, 2010 at 5:05:00 AM GMT+2  
Blogger jimmychooshoes said...

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

Sunday, August 8, 2010 at 9:52:00 AM GMT+2  
Blogger hibeyond said...

black boots

Chocolate boots

sand boots

Chestnut boots

gray boots

pink boots

grey boots

pink boots

Wednesday, August 10, 2011 at 5:47:00 AM GMT+2  
Blogger Oleg Golovin said...

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

Saturday, December 24, 2011 at 5:39:00 PM GMT+1  

Post a Comment

Subscribe to Post Comments [Atom]

<< Home