🚀 go-pugleaf

Die Partitionierung nur zur Halbierung nach der Anzahl w�re leichter
l�sbar, als mit deinem Vorschlag. Aber wenn die Partition noch nach
anderen Parametern gel�st werden soll, ist es ein ganz guter Weg.
Die Halbierung nach Anzahl allein ist trivial l�sbar.

zB. Teile eine Menge von geometrischen Punkten (oder
h�herdimensionierten Nodes, Datenbanken) in zwei H�lften, so da� auf
jeder Seite ca. gleich viele Punkte sind. 
Sozusagen finde die beste Schnittgerade durch deine Punktwolke.
Das geht entweder mit adaptiver Optimierung (step-wide refinement) oder
rekursiv, wie bei dir.

H�her-dimensionalere Partitionierungen (f�r range-queries, SQL
Optimizations und so) funktioniert -glaub ich- eh nur mehr rekursiv, so
wie bei dir.

L�sungen k�nnte ich nur in Lisp/Scheme skizzieren:

p: 	globale punktwolke, wird immer leerer
l1, l2: zwei listen, anfangs leer
x, y: 	zwei elemente aus je einer liste

(defun main ()
  ;; initialize p
  (setq p ...)
  ;; halbiere mu� auch listen k�nnen, also fangen wir klein an.
  (halbiere (list (car p)) 	; links
            (list (last p)) 	; rechts
            (cdr (butlast p)))) ; der rest

(defun abstand (x y)	; => zahl 
  (custom-distance x y))

(defun halbiere (links rechts p)
  (cond 
    ((null p)  (list links rechts)) ; abbruch bedingung
    (T
     (let ((x (car p))	; wohin geh�rt n�chste? rechts oder links
       ;; hmm.. summe der abst�nde nach rechts <=> links
       ;; die summen aller anst�nde ist aber nicht besonders geschickt,
       ;; divide&conquer w�re etwas besser. 
       			; (naja, f�r 10 min auch nicht so schlecht.)
       (if (< (apply #'+ (mapcar #'(lambda (y) (abstand x y)) links))
              (apply #'+ (mapcar #'(lambda (y) (abstand x y)) rechts))
         (halbiere (cons x links) rechts (cdr p))
         (halbiere links (cons x rechts) (cdr p))
         ))))

oder so �hnlich.
aber du wolltest ja einen vergleich jeweils zweier elemente? hmm...

(setq p '(0 4 6 3 1 9 2 7 8 5)
      l  (length p)
      ;; teile in zwei ca. gleich gro�en listen
      p1 (firstn (/ l 2) p)	
      p2 (nthcdr (/ l 2) p))

;;; divide & conquer ist besser. so wie merge-sort
(defun compare (links rechts)
  (cond 
    ((null links)  rechts)
    ((null rechts) links)
    ((and (atom rechts) (atom links))
     (< links rechts))
    ((compare (cdr links) (cdr rechts))
       (list links rechts))
    (T (list (cons (car rechts) links)
	     (cons (car links) rechts)))
    ))

(compare p1 p2)

Robert Will wrote:
>folgende einfache Frage, ergab sich gerade f�r einen Algo. Mir viel die
>L�sung nicht auf Anhieb ein und dachte, vielleicht �berlegen wir mal
>zusammen.
>
>Ich m�chte eine Menge folgendermassen halbieren:
>paare jeweils zwei Elemente aus der Menge, die Paare hei�en Teilmengen.
>paare dann jeweils zwei dieser Teilmengen zu neuen Teilmengen
>paare dann die entstandenen Teilmengen,
>usw.
>
>F�r die Paarung gibt es eine Funktion, die zu jeweils zwei Teilmengen eine
>Paarungspriorit�t berechnet, mit f(A, B) <> f(B, A). Es kann vorkommen, da�
>hierbei zwei andere Teilmengen gleiche Priorit�t haben, da mu� man auch noch
>Paarungsalgorithmen anwenden.
>Ziel ist es die urspr�ngliche Menge zu halbieren, d.h. zwei Teilmengen zu
>erhalten, so da� in jeder Teilmenge h�chstens ein Element mehr ist, als in
>der anderen.
>
>Wie mu� man dabei eventuell bei der Paarung �brigbleibende Teilmengen
>verteilen?
>
>Geht das �berhaupt?
>
>
>Ich sehe gerade, es ist doch nicht so einfach, aber vielleicht hat sich ja
>schon mal irgendein ber�hmter Kopf damit herumgeschlagen und jemand von Euch
>hat sein Buch gelesen. :-)

--
Reini Urban
http://xarch.tu-graz.ac.at/autocad/news/faq/autolisp.html