Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 11 |

2008-03-03

ArcでL-99 (P27a 9人を2:3:4に分ける組み合わせ)

| 13:40 | ArcでL-99 (P27a 9人を2:3:4に分ける組み合わせ) - わだばLisperになる を含むブックマーク はてなブックマーク - ArcでL-99 (P27a 9人を2:3:4に分ける組み合わせ) - わだばLisperになる

P27はaとbの二段構えなのですが、今回は、9人を2:3:4に分けるすべての組み合わせをリストで返すというお題です。

組み合わせ系は総数が爆発的に増えたりすることが多く、非常に苦手です…。

ということで、解答も結構やっつけになってしまっています…。

解答には、前回定義したcombinationを使用しています。

CLでいうset-difference、SRFI-1でいうlset-differenceがArcで見付けられなかったので、MacLISPのsetdiffを参考に作成しました。

また、pointは、Schemeのlet/ccに相当するようです。

(group3 '(aldo beat carla david evi flip gary hugo ida))
;=> (((aldo beat) (carla david evi) (flip gary hugo ida))
;    ((aldo beat) (carla david flip) (evi gary hugo ida))
;    ((aldo beat) (carla david gary) (evi flip hugo ida)) ...)

(len (group3 '(aldo beat carla david evi flip gary hugo ida)))
;=> 1260

(def group3 (lst)
  (let res ()
    (each u (combination 2 lst)
      (let diff (setdiff lst u)
	(each v (combination 3 diff)
	  (= res `(,@res (,u ,v ,(setdiff diff v)))))))
    res))

(def setdiff (x y)
  (point exit
    (each yy y
      (when (mem yy x)
	(exit (y-x+z x y () ))))
    x))

(def y-x+z (y x z)
  (let y-x ()
    (each xx y
      (or (mem xx x) (push xx y-x)))
    (= y-x (join (rev y-x) z))))