Write a Lisp function ‘powerset(lst)’ that takes a list ‘lst’ as input and retur

Question

Write a Lisp function ‘powerset(lst)’ that takes a list ‘lst’ as input and returns the power set of the lst. Assume the input lst to be a set which is used to generate the power set of the input set. A power set is defined as a set of all subsets of a set.

>(powerset ‘(1 2 3))

((1 2 3) (2 3) (1 3) (3 ) (1 2) (2 ) (1) NIL)

Power set of {a, b, c, d, …} is equal to the union of power set of {b, c, d,…} and ‘a’ appended to each element of power set of {b, ,c, d,…}

Write a Lisp function ‘addx(x pset)’ that appends an element x to each element of a power set.

Sample output of addx:

>(addx ‘3 ‘(nil) )

( (3) NIL)

>(addx ‘2 ‘( (3) nil))

( (2 3) (2) (3) NIL)

>(addx ‘1 ‘( (2 3) (3) (2) nil))

( (1 2 3) (1 3) (1 2) (1) (2 3) (3) (2) NIL)

Use ‘addx’ to complete the Lisp function ‘powerset’.

Use the ‘remove-duplicates’ function to remove duplicate elements in the powerset.

I have written a Lisp function ‘ps’ that returns the power set of a list, but the duplicates have not yet been removed. Here is that code:

(defun ps(lst)

   (cond

            ((null lst) nil)

            ((equal 1 (length lst))(list lst)(list nil))

            (T (append (list lst)(list (list(car lst)))

            (list (cdr lst))

               (list (cons (car lst)(list (car (cdr lst)))))

                (list (cons (car lst)(list (car (reverse lst)))))

                 (ps(cdr lst))))))

So, what I need to do is write the ‘addx’ function and rewrite the code to incorporate that function. Then use the remove-duplicates function to remove the duplicates. The following functions are NOT ALLOWED: mapc, mapcar, maplist, do, do*, dolist, setq, and when. Loops are also NOT ALLOWED. I know how to remove the duplicates. I am just having a hard time understanding how to write the 'addx' function. Any help would be greatly appreciated.

Explanation / Answer

Program:

(defun powerset(lst)
   (cond
            ((null lst) nil)
            ((equal 1 (length lst))(list lst)(list nil))
            (T (append (list lst)(list (list(car lst)))
            (list (cdr lst))
               (list (cons (car lst)(list (car (cdr lst) ) ) ) )
                (list (cons (car lst)(list (car (reverse lst)))))
                 (powerset(cdr lst))
                )
            )
    )
)

(print (powerset '(1 2 3 4)))

((1 2 3 4) (1) (2 3 4) (1 2) (1 4) (2 3 4) (2) (3 4) (2 3) (2 4) (3 4) (3) (4) (3 4) (3 4) NIL)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.