;;
;; CMSC 245
;; 
;; written by Joseph Anthony C. Hermocilla
;;
;; Hitting Set
;;
;;  Given:
;;        S - a set
;;        C - a collection of subsets of S
;;        K - a positive integer
;;
;;  Problem:
;;        Is there a subset, S-prime, of S with |S-prime| <= K
;;        such that S' contains at least one element from each subset in C
;;
;;  Algorithm:
;;
;;      Very inefficient! Generates the powerset and performs the check, whew!
;; 


;;Lifted from http://www.ccs.neu.edu/home/pwang/teaching/csu520/f03/hw_proj/hw_proj2.htm
;;recursive powerset generator
;;
;;The powerset p(S) can be generated by considering the relationship b/w p(S) and p(S-x),
;; where x is a singleton.
;;
;;base case     : p(())=()
;;recursive call: p(S)=p(S-x) U x U p(S-x)
;;
(defun powerset (s)
   (if (null s) (list nil)                                  ;;base case: (powerset '()) = '(())
     (let ((cdr-powerset (powerset (cdr s))))               ;;p(S-x)
     (append cdr-powerset
         (mapcar #'(lambda (subset) (cons (car s) subset))
             cdr-powerset)))))

;;the set S
(setq S '(a b c d e f))

;;a collection of subset of S
(setq C '((a b) (a c) (b c a)))

;;the positive integer K
(setq K 2)

;;hiting set algo..
;;walang kwenta!
(defun hitset (S C K)
  (setq P (powerset S))          ;;generate the powerset
  (setq P (remove nil P))        ;;discard nil
  (dolist (S-prime P nil)        ;;for each subset S' in P
    (if (<= (length S-prime) K)  ;;|S'| <= K
       (dotimes (i (length S-prime) nil)      ;;for each s element of S'
	 (dolist (C-prime C nil)                                ;;check if s is an element of C'
	   (if (not (member (car (nthcdr i S-prime)) C-prime))  ;;remove S' from P if s not a member of C'
	       (setq P (remove S-prime P))                      
	     )
	   )
	 )
      (setq P (remove S-prime P))      ;;discard sets with |S'| > K
      )
    )
  P
)

(hitset S C K)