12.81 util.combinations - 組み合わせ

Module: util.combinations ¶

このモジュールは、いくつかの便利なコンビネーションや順列とそれに関連する 操作の手続きを実装しています。

このモジュールのほとんどの手続きは2つのバージョンを持っています。 1つはアスタリスクの付かない手続き(例えば、permutations)で、 与えられたセットにある全ての要素を区別して扱います。もう1つは、 アスタリスクの付く手続き(例えば、permutations*)で、重複を 考慮します。アスタリスクの付く手続きは、オプショナルなeq引数を取り ます。それは等値性のテストに使われ、デフォルトはeqv?です。

Function: permutations set ¶

Function: permutations* set :optional eq ¶

{util.combinations} リストsetの全ての順列のリストを返します。

(permutations '(a b c))
  ⇒ ((a b c) (a c b) (b a c) (b c a) (c a b) (c b a))

(permutations '(a a b))
  ⇒ ((a a b) (a b a) (a a b) (a b a) (b a a) (b a a))

(permutations* '(a a b))
  ⇒ ((a a b) (a b a) (b a a))

setがある程度の要素を持っている場合、可能性のある順列の数は 爆発的に大きくなります。注意して使って下さい。 一度にそれぞれの順列を処理したい場合は、下記のpermutations-for-eachの 使用を考慮して下さい。

Function: permutations-for-each proc set ¶

Function: permutations*-for-each proc set :optional eq ¶

{util.combinations} リストsetのそれぞれの順列に対して、procを呼び出します。 戻り値は未定義値です。

Function: combinations set n ¶

Function: combinations* set n :optional eq ¶

{util.combinations} リストsetのn個の要素の可能性のある全ての順列のリストを 返します。

(combinations '(a b c) 2)
  ⇒ ((a b) (a c) (b c))

(combinations '(a a b) 2)
  ⇒ ((a a) (a b) (a b))

(combinations* '(a a b) 2)
  ⇒ ((a a) (a b))

setが大きいときは、組み合わせの爆発について注意して下さい。

Function: combinations-for-each proc set n ¶

Function: combinations*-for-each proc set n :optional eq ¶

{util.combinations} setのn個の要素のそれぞれの組み合わせについてprocを 呼び出します。戻り値は未定義値です。

Function: power-set set ¶

Function: power-set* set :optional eq ¶

{util.combinations} リストsetの累乗集合(全てのサブセット)を返します。

(power-set '(a b c))
  ⇒ (() (a) (b) (c) (a b) (a c) (b c) (a b c))

(power-set* '(a a b)
  ⇒ (() (a) (b) (a a) (a b) (a a b))

Function: power-set-for-each proc set ¶

Function: power-set*-for-each proc set :optional eq ¶

{util.combinations} setのそれぞれのサブセットについてprocを呼び出す。

Function: power-set-binary set ¶

{util.combinations} power-setのように、setの累乗集合を返しますが、順番が異なります。 power-set-binaryはサブセットの空間を深さ優先でトラバースしますが、 power-setは横型探索を行います。

(power-set-binary '(a b c))
  ⇒ (() (c) (b) (b c) (a) (a c) (a b) (a b c))

Function: cartesian-product list-of-sets ¶

Function: cartesian-product-right list-of-sets ¶

{util.combinations} list-of-setsにあるセットのデカルト積を返します。 cartesian-productは左固定順で結果を構築しますが (一番右の要素がまず異なる)、 cartesian-product-rightは右固定順で行います (一番左の要素がまず異なる)。

(cartesian-product '((a b c) (0 1)))
  ⇒ ((a 0) (a 1) (b 0) (b 1) (c 0) (c 1))

(cartesian-product-right '((a b c) (0 1)))
  ⇒ ((a 0) (b 0) (c 0) (a 1) (b 1) (c 1))