Nummer Partitionierung in R5RS

Question

Ich wurde in einem Praktikumsinterview gebeten, ein R5RS-Programm zu erstellen, das eine Funktion erstellt, sagen wir zwei Untergruppen. Diese Funktion muss #t zurückgeben, wenn die Liste L zwei Untermengen mit gleichen Summen von Elementen und mit gleicher Anzahl von Elementen enthält, andernfalls wird #f zurückgegeben. Es nimmt Eintrag die Liste L (nur positive Zahlen) und einige Parameter (die ich für nützlich befunden. Es gibt keine Bedingungen für die Anzahl der Parameter) alle gleich 0 am Anfang.

Die Anforderungen, wie ich mich noch erinnere, waren wie folgt: - Definieren Sie keine anderen Funktionen und rufen Sie sie innerhalb der "Zwei-Teilmengen" -Funktion auf. - Es kann nur die folgenden Konstrukte verwenden: null ?, cond, auto, cdr, else, +, =, nicht, und, #t, #f, zwei Untergruppen (selbst für rekursiven Aufruf), die Namen der Parameter B. Liste, Summe, ... usw., numerische Konstanten und Klammern.

Es gab einige angeführten Beispiele zu den Ergebnissen, die wir haben sollen, lassen Sie uns sagen:

(two-subsets '(7 7) 0 0 0) returns #t. The two subsets are {7} and {7}. 
(two-subsets '(7 7 1) 0 0) returns #t. The two subsets are {7} and {7}. 
(two-subsets '(5 3 2 4) 0 0) returns #t. The two subsets are {2, 5} and {3, 4}. 
(two-subsets '(1 2 3 6 9) 0 0) returns #f. 

ich durch Schreiben der Signatur begann, dass es mir aussieht sollte es so etwas wie dieses:

(define two-subsets (lambda (L m n ... other parameters) 
        (cond 

Das Problem ist sehr kompliziert und seine Komplexität ist offensichtlich mehr als O (n), ich lese es auf https://en.wikipedia.org/wiki/Partition_problem.

Ich habe versucht, zuerst den Algorithmus zu definieren, bevor ich ihn kodiere. Ich dachte darüber nach, als Parameter zu nehmen: Summe der Liste L, also in meinen Bedingungen werde ich nur auf die Kombinationen iterieren, deren Summe < = sum (L)/2 ist. Dadurch kann ich die Komplexität des Problems ein wenig reduzieren, aber ich konnte trotzdem nicht herausfinden, wie es geht.

Es sieht wie ein interessantes Problem aus und ich möchte wirklich mehr darüber wissen.

Answer 1

Hier ist eine Version, die nicht davon abhängt, dass die Zahlen alle positiv sind. Ich bin mir ziemlich sicher, dass du viel besser als dies tun kannst, wenn du weißt, dass sie es sind.

Hinweis dies setzt voraus, dass:

• die Partition nicht erschöpfend sein muss;
• aber die Sätze dürfen nicht leer sein.

Ich wäre sehr interessiert, eine Version zu sehen, die auf den Elementen der Liste beruht + ve!

(define (two-subsets? l sl sld ssd) 
    ;; l is the list we want to partition 
    ;; sl is how many elements we have eaten from it so far 
    ;; sld is the length difference in the partitions 
    ;; ssd is the sum difference in the partitions 
    (cond [(and (not (= sl 0)) 
       (= sld 0) 
       (= ssd 0)) 
     ;; we have eaten some elements, the differences are zero 
     ;; we are done. 
     #t] 
     [(null? l) 
     ;; out of l, failed 
     #f] 
     ;; this is where I am sure we could be clever about the set containing 
     ;; only positive numbers, but I am too lazy to think 

     [(two-subsets? (cdr l) 
         (+ sl 1) 
         (+ sld 1) 
         (+ ssd (car l))) 
     ;; the left-hand set worked 
     #t] 
     [(two-subsets? (cdr l) 
         (+ sl 1) 
         (- sld 1) 
         (- ssd (car l))) 
     ;; the right-hand set worked 
     #t] 
     [else 
     ;; finally drop the first element of l and try the others 
     (two-subsets? (cdr l) sl sld ssd)]))