gistfile1.txt

; 3. cviceni

; UKOL (20): Problem stabilnich (nebo spise ne nestabilnich) manzelstvi
; N procesu muzu a N procesu zen
; kazdy muz hodnoti kazdou zenu cislem od 1 do N, vetsi cislo je lepsi
; hodnoceni
; kazda zena hodnoti kazdeho muze cislem od 1 do N, vetsi cislo je
; lepsi hodnoceni
; parovani (pary muzu a zen 1:1) je stabilni, kdyz pro muze m1, m2 a
; jejich protejsky z1, z2 zaroven plati:
; 1. m1 hodnoti z1 lepe nez z2 nebo z2 hodnoti m2 lepe nez m1
; 2. m2 hodnoti z2 lepe nez z1 nebo z1 hodnoti m1 lepe nez m2
; reseni problemu: stabilnich parovani N paru
; vyreste problem a nastinte dukaz reseni
 
(defun stabilni-manzelstvi (muzi zeny)
  (let* ((N (min (length muzi) (length zeny)))
	 (parovani (make-array N :initial-element (list -1 -1)))
         (men (make-array N :initial-element nil))
         (offers (make-array N :initial-element nil))
         (pocetNabidek (make-array N :initial-element 0))
         (zadany 0)
         )
    (labels ((muz (i)
               (await (and (not (aref i offers))
                           (not (aref i men))))
               (setf (aref i offers) (position (- N (aref i pocetNabidek))))
               (setf (aref i pocetNabidek) (+ (aref i pocetNabidek) 1))
               
                ))
	     (zena (i)
               (await (position i offers))
               (if (position i (mapcar #'cdr parovani))
                   (progn
                     (let ((manzel (car (nth (position i (mapcar #'cdr parovani)) parovani)))
                           (dvori (position i offers)))
                       (if (; dvorici < snoubenec
                           
                 (progn
                   (push (list  chlap  i) parovani)
                   (setf (nth (position i offers) offers) nil))
               ))
      (co-progn
        (co-dotimes (i N) (muz i))
        (co-dotimes (i N) (zena i))
        )
      parovani
      )))

(stabilni-manzelstvi '((1 3 2) (2 1 3) (1 3 2))
		     '((1 3 2) (1 3 2) (2 1 3)))

=> #((1 3) (3 2) (2 1))

|#
function stableMatching {
    Initialize all m  M and w  W to free
    while  free man m who still has a woman w to propose to {
       w = m's highest ranked such woman
       if w is free
         (m, w) become engaged
       else some pair (m', w) already exists
         if w prefers m to m'
           (m, w) become engaged
           m' becomes free
         else
           (m', w) remain engaged
    }
}
#|