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-04

ArcでL-99 (P27b リストを任意の比率で分割した組み合わせ)

| 14:09 | ArcでL-99 (P27b リストを任意の比率で分割した組み合わせ) - わだばLisperになる を含むブックマーク はてなブックマーク - ArcでL-99 (P27b リストを任意の比率で分割した組み合わせ) - わだばLisperになる

今回は、前回の続きです。

リストを任意の比率で分割したすべての組み合わせをリストで返すというお題なのですが、多分、L-99のリスト篇では一番ややこしいんじゃないかと思います。

(1 2 3 4 5)というリストで、2:3に分ける場合、((1 2) (3 4 5) )と((2 1) (4 3 5) )は同じものとみなされますが、((1 2) (3 4 5) )と((3 4 5) (1 2) )は別物という扱いになります。

解答には、前に定義したcombinationと、setdiffを使用しています。butlastも見当たらないので、自作しました。

かなり混沌としていますが、私の実力では、最早これが正しいのかさえ良く分かりません(笑)

どう書くorgにはこういうのささっと綺麗に解く人が沢山いるんですよね。あやかりたい。あやかりたい。

(group '(aldo beat carla david evi flip gary hugo ida) '(2 3 4))
;=> (((aldo beat) (gary hugo ida) (carla david evi flip)) ...)

(len (group '(aldo beat carla david evi flip gary hugo ida) '(2 3 4)))
;=> 1260

(def group (lst pat)
  ((afn (lst pat)
     (if (or no.pat (~<= 0 (apply + pat) len.lst)) () 
	 (is len.lst car.pat) list.lst
	 (is 1 len.pat) (sep2 lst car.pat)
	 'else (sep2-list (self lst cdr.pat) car.pat)))
   lst rev.pat))

;; リストを2つに分ける
(def sep2 (lst num)
  (map [list _ (setdiff lst _)]
       (combination num lst)))

;; 複数のリストを2つに分けて、それを継げたリストを返す
(def sep2-list (lsts num)
  (let res ()
    (each l lsts
      (= res (+ (map [if cadr._
			 `(,@butlast.l ,@_)
			 `(,@butlast.l ,car._)]
		(sep2 last.l num))
		res)))
    res))

(def butlast (lst)
  (cut lst 0 (- len.lst 1)))