Powerset einer Liste mit abstrakten Listenfunktionen

Nov 24 2020

Ist es möglich, eine Schlägerfunktion zu erstellen, um das Powerset einer bestimmten Liste zurückzugeben ?


Einschränkungen-

  1. ohne explizite Rekursion
  2. Verwenden Sie abstrakte Listenfunktionen
  3. Code in 2 Zeilen enthalten (tatsächliche Anforderung)

Zum Beispiel: (powerset '(1 2))

'((1 2) (1) (2) ())

In irgendeiner Reihenfolge.

Die andere Frage, die ich gefunden habe, verwendet immer noch eine explizite Rekursion.


Mein Workflow:

  1. Nehmen wir (powerset '(a b c))als Beispiel:
  2. Holen Sie sich zuerst eine Liste mit ganzen Zahlen bis zu (expt 2 (length list)) ;'(0 1 2 3 4 5 6 7)
  3. Konvertieren Sie sie in ihre jeweilige Binärform 2->(0,1,0). Also bekommen wir'((0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1))
  4. map '(1 2 3) auf die Liste der Binärdateien. Zum Beispiel:2->'(0,1,0)->'((0,a) (1,b) (0,c))
  5. Filtern Sie die resultierende Liste mit einem Lambda, sodass wir Elemente mit 1 behalten, wie z '((1,b)).
  6. Extrahieren Sie das Powerset

Problem mit meinem Ansatz

Es folgt nicht der Einschränkung, dass sich die Frage in einer Zeile befindet (zusätzlich zum Funktionsheader).

(define (powerset list)
  ( ... )) ;; ie the code is contained in 2 lines of 80 characters

Ich hatte diese Frage in meiner Aufgabe als Bonusfrage, aber ich konnte es nicht tun.

  1. Was sind abstrakte Listenfunktionen?
  • Funktionen wie foldl, foldrundmap
  1. Mein Bonus umfasste 3 Unterteile
  • Teil 1 bat darum, diese Funktion einfach so zu machen, wie ich es wollte. Also habe ich Rekursion verwendet, um dies zu tun
  • Teil 2 ist der Teil, über den ich die Frage gestellt habe. Dieser war besonders schwierig, da der Code zusätzlich auf 2 Zeilen beschränkt sein musste
  • Teil 3 sollte der härteste sein.

Schreiben Sie keine Hilfsfunktionen und verwenden Sie keine explizite Rekursion (dh Ihre Funktion kann sich nicht beim Namen nennen). Verwenden Sie keine abstrakten Listenfunktionen. In der Tat, verwenden Sie nur die folgende Liste von Racket Funktionen, Konstanten und Sonderformen: cons, first, rest, empty?, empty, lambda, und cond.

Allerdings habe ich Y-combinatordiese Sache studiert und konnte sie lösen (nach 6 Stunden Codierung).

Antworten

2 WillNess Nov 25 2020 at 16:57

So beantworten Sie Ihren Bonus Teil 2:

(define (pws l) 
  (foldr (lambda (e a) (append (map (lambda (x) (cons e x)) a) a)) '(()) l))

Zwei Zeilen mit jeweils weniger als 80 Zeichen, erste Zeile für define(also eine Zeile) reserviert .

Wenn dies appendnicht erlaubt ist, verwandeln wir die append ... mapKombination ebenfalls in foldr:

(define (pws-fr l) 
  (foldr (lambda (e a)
           (foldr (lambda (x r)
                    (cons (cons e x) r))
                  a a))
         '(()) l))

oder, verkürzt,

(define (pws-fr-1 l) 
  (foldr (lambda (e a) (foldr (lambda (x r) (cons (cons e x) r)) a a)) '(()) l))

(mit genau 80 Zeichen in der zweiten Zeile).

Eine andere Möglichkeit, dies zu codieren, ist der append-map-basierte Code (das zweite Snippet) aus dieser Antwort, der, wenn er nur mit neu codiert foldrwird, wird

(define (pws-am-fr l) 
  (foldr (lambda (e a)
           (foldr (lambda (x r)
                    (cons x (cons (cons e x) r)))
                  '() a))
         '(()) l))

oder verkürzt,

(define (pws-am-fr1 l) (foldr (lambda (e a)
   (foldr (lambda (x r) (cons x (cons (cons e x) r))) '() a)) '(()) l))

die Ihre Anforderungen möglicherweise genau erfüllen oder nicht.