やっぱりオブジェクト！

 1: # Permutation generator
 2: #   generate sequence of length n consisted of value 0..(m-1).
 3: #     ex. Permutation(4,3) =>
 4: #           [0,1,2],[0,1,3],[1,0,2],[1,0,3],[2,0,1], .. ,[3,2,0],[3,2,1]
 5: #
 6: #   Permutation(m, n):
 7: #     create a object for mPn.
 8: #   permute():
 9: #     generate a permutation.
10: #     EOFError raised when no more permutations.
11: #
12: class Permutation:
13:     def __init__(self, m, n):
14:         if n > m or n <= 0: raise ValueError
15:         s = _sentinel()
16:         for i in xrange(n):
17:             s = _selection(s)
18:         self.sel = s
19:         self.sel.reset(range(m))
20:
21:     def permute(self):
22:         return self.sel.select()
23:
24: # internal classes
25: class _selection:
26:     def __init__(self, c):
27:         self.avail = []
28:         self.child = c
29:         self.next = 0
30:
31:     def reset(self, a):
32:         self.avail = a
33:         self.next = 0
34:         self.child.reset(self.avail[1:])
35:
36:     def select(self):
37:         s = self.avail[self.next]
38:         try:
39:             ss = self.child.select()
40:         except EOFError:
41:             self.next = self.next + 1
42:             try:
43:                 s = self.avail[self.next]
44:             except IndexError:
45:                 raise EOFError
46:             self.child.reset(self.avail[:self.next] + self.avail[self.next+1:])
47:             ss = self.child.select()
48:         return [s] + ss
49:
50: class _sentinel:
51:     def __init__(self):
52:         self.selected = 0
53: 
54:     def reset(self, a):
55:         self.selected = 0
56:
57:     def select(self):
58:         if self.selected:
59:             raise EOFError
60:         else:
61:             self.selected = 1
62:             return []

このライブラリは，

import perm
 ...
p = perm.Permutation(3, 2)
x = p.permute()
 ...
y = p.permute()
 ...

では，プログラムの解説です。さっきより真面目に解説します。

• 12，25，50行目の‘class’に続く部分がクラスの定義です。クラス内部で宣言された関数は，メソッドとして扱われます。
• この例では，継承がありませんが，継承を行う場合は，クラス名に続いて()内にカンマで区切って基底クラスを列挙します。_sentinelクラスは意味的には_selectionクラスの派生クラスであるべきなので，‘class _sentinel(_selection):’と宣言するのが正しいのでしょうが，すべてのメソッドをoverrideしていますし，形式的に派生クラスである必要性もないので，独立したクラスとして定義してしまっています。変数に型が無いのでこんなこともできるのです。
• メソッドは，形式的に，インスタンスのリファレンス（C++やJavaのthisにあたるもの）を，追加された第一引数で受け取ります。呼び出す側は，‘p.permute()’と呼び出しますが，メソッドの呼出し形式は，‘permute(self)’となります。一般的には，‘instance.method(x1,x2, .. ,xn)’は，‘method(self,x1,x2, .. ,xn)’で受けます。selfという名前は変更することも可能ですが，慣習的にselfを使います。
• _selectionや，_sentinelという内部的なクラスの名前は下線（アンダースコア）で始まっていますが，これはライブラリの輸入にあたっての常套手段です。‘from perm import *’という形式で輸入すると，定義されているものが，直接，輸入元の名前空間にマージされ，モジュール名の修飾が不要となります。つまり，いきなり‘Permutation’と表記して参照します（逆にいうと，‘import perm’形式で輸入すると，‘perm.Permutation’と，モジュール名の修飾が必要になります）。この際，名前が下線で始まっているトップレベルの定義名は，名前空間にはマージされず，輸入元からは見えなくなるのです。
• 13，26，51行目の__init__というメソッドがコンストラクタです。インスタンスの生成は，‘クラス名(__init__の実質的な引数)’（例えば，‘Permutation(3,2)’）と呼び出します。
• 19行目の‘range(m)’は，[0,1, .. ,m-1]というリストを生成します。