2004/12/24

というわけで、マイファーストPythonは、配列の要素の全組み合わせ(combination)を得るものでした。

#! /usr/bin/python
#
# get combinations set from array.
#
# Keiichirou SHIKANO

def get_combinations(array, n):
if len(array) < n:
print "get_combinations() error: too large combinations for the array"
return -1

kappa = 1
bb = array[ : ]
lena = [[1]]

for i in range(0, len(array) + 1):
lena[0].append(1)

while kappa < n:
aa = []
lena.append([])
for ichiro in range(0, len(array)):
cc = []
del bb[0 : lena[kappa - 1][ichiro]]
lena[kappa].append(len(bb))
for joe in range(0, len(bb)):
if kappa < 2:
cc = [array[ichiro]] + [bb[joe]]
else:
cc = [array[ichiro]] + bb[joe]
aa.append(cc)
bb = aa[ : ]
kappa = kappa + 1
return bb

# test data
b = ["foobar", [0, 1, 2], 3, 0, ["cat", 7]]
s1 = 4

print get_combinations(b, s1)


実行結果

[['foobar', [0, 1, 2], 3, 0], ['foobar', [0, 1, 2], 3, ['cat', 7]], ['foobar', [
0, 1, 2], 0, ['cat', 7]], ['foobar', 3, 0, ['cat', 7]], [[0, 1, 2], 3, 0, ['cat'
, 7]]]


自分で忘れないように簡単にメモしておくと、こいつは、まず2つの要素の組み合わせ((n 2)個)を構成する(n:配列の大きさ)。その組み合わせに対して、もう1つの要素を組み合わせたパターン(((n 2) 2)個)を求める。これの繰り返し。構成的に組み合わせの要素を求めるなら、枝も少ないし、けっこういいアルゴリズムな気がする(どうせすぐに認識の甘さを思い知るので、今はこう思わせておいてください)。
その代わり、メモリはやたらに喰う。あと、どんなに演算が早くても、全部で100個の要素から9個取り出す組み合わせを一覧しようとして結果を標準出力したりした日にゃあ、(100 9) = 1,902,231,808,400パターンになりますから! 黙っちゃうよ(計算あってる?)。

No comments :