From: Thomas Trenz
Subject: Re: challenge: set partitions and power set
Date: 
Message-ID: <2l6ue3$lmq@hitchcock.dfki.uni-sb.de>
K-PARTITIONS:

The function k-partition enumerates k-partitions of a given set and
calls for every partition a user defined function.
The enumeration stops when the user defined function returns a non-nil value.

The user defined function gets two parameters:

1. The partition as a list of lists (e.g. ((a b) (c) (d e f)) for a 3-partition
   of the set (a b c d e f)).
2. A list of additional arguments (optional).



(Defun User-Defined (Partition Optional-Args)
  (Print Partition)
  nil)                     ; return value nil to continue enumeration



(Defun K-Partition-Help (K Stack Partition Function Args)
  (If (And (>= (+ (Length Stack) (Length Partition)) K) 
	   (<= (Length Partition) K))                   
      (If (Null Stack)
	  (Progn
	   (If (= (Length Partition) K)
	       (Progn
		(Funcall Function Partition Args))))
	  
	  (Let ((Element (Pop Stack))
		(Temp-Partition Partition))

	       (Or (Progn
		    (Push (List Element) Temp-Partition)
		    (K-Partition-Help K Stack Temp-Partition Function Args))
		   
		   (Some #'(Lambda (Set)
				   (Setq Temp-Partition Partition)
				   (Setq Temp-Partition (Remove Set Temp-Partition :Test #'Equal))
				   (Push (Union (List Element) Set) Temp-Partition)
				   (K-Partition-Help K Stack Temp-Partition Function Args))
			 Partition))))))


; Computes all k-partitions of a given set and
; calls for every k-partition a Function given by the parameter FUNCTION.
; The enumeration of partitions stops, when FUNCTION return a non-nil value.

(Defun k-partition (Set K Function &Optional (ArgForFunction nil))
  (K-Partition-Help K (Rest Set) (List (List (First Set))) Function ArgForFunction))



; Demo call:

(k-partition '(a b c d e f) 3 (function User-Defined))



Thomas Trenz
mail: ·····@dfki.uni-sb.de