今までの勉強をふまえて、前回のジェネレータをクラスで書く。
class perm:
def __init__(self, l):
self.l = l
self.n = len(l)
self.i = 0
if self.n > 1:
self.perm = perm(l[1:])
def __iter__(self):
return self
def next(self):
if self.n > 1:
while self.i < self.n:
try:
e = self.perm.next()
return [ self.l[self.i] ] + e
except StopIteration:
self.i += 1
self.set_new_perm()
raise StopIteration
else:
self.i += 1
if self.i > 1:
raise StopIteration
return self.l
def set_new_perm(self):
if self.i == self.n:
raise StopIteration
self.perm = perm(self.l[:self.i] + self.l[self.i+1:])def isValid(e):
for i in range(len(A)):
if A[i].count(e[i]) == 0:
return False
return TrueA = [ [ 1, 2 ], [ 2, 3 ], [ 3, 1 ] ];
l = [ 1, 2, 3 ]
for e in perm(l):
if isValid(e):
print e
けっこう大変だった。
上では全ての順列を発生させて、それが条件にあてはまっているかチェックしているが、それは効率が悪い。例えば、いささか人工的だが、こういうデータがあったとする。
A = [ [ 1, 2 ], [ 2, 3 ], [ 3, 1 ], [ 4, 5 ], [ 5, 6 ], [ 6, 4 ] ];
このとき、e = [ 3, 1, 2, 4, 5, 6 ] をチェックすると、最初の要素でひっかかるので、最初の要素は次の、e = [ 4, 1, 2, 3, 5, 6 ] に移っていい。
チェックを何番目に引っかかったかを返すことにし（チェックを通ったら-1）、引っかかったらそこはすっ飛ばすことにする。
class perm:
def __init__(self, l):
self.l = l
self.n = len(l)
self.i = 0
if self.n > 1:
self.perm = perm(l[1:])
def __iter__(self):
return self
def next(self):
if self.n > 1:
while self.i < self.n:
try:
e = self.perm.next()
return [ self.l[self.i] ] + e
except StopIteration:
self.i += 1
self.set_new_perm()
raise StopIteration
else:
self.i += 1
if self.i > 1:
raise StopIteration
return self.l
def proceed_last(self, i):
if i == 0:
self.i += 1
self.perm = perm(self.l[:self.i] + self.l[self.i+1:])
else:
self.perm.proceed_last(i - 1)
def set_new_perm(self):
if self.i == self.n:
raise StopIteration
self.perm = perm(self.l[:self.i] + self.l[self.i+1:])def isValid(e):
for i in range(len(A)):
if A[i].count(e[i]) == 0:
return i
return -1A = [
[ 1, 2 ], [ 2, 3 ], [ 3, 1 ], [ 4, 5 ], [ 5, 6 ], [ 6, 4 ],
];
l = range(1, 7)
p = perm(l)
for e in p:
iRet = isValid(e)
if iRet == -1:
print e
else:
p.proceed_last(iRet)
6つの順列だから720回チェックしなければならなかったが、これだと31回で済む。
