Power set in Scheme with ordered output

Question

So I am familiar with the algorithm for creating a power set using Scheme that looks something like this:

 (define (power-set set) 
    (if (null? set) '(()) 
       (let ((power-set-of-rest (power-set (cdr set)))) 
             (append power-set-of-rest 
                   (map (lambda (subset) (cons (car set) subset)) 
                         power-set-of-rest)))))

So this, for (1, 2, 3, 4), would output:

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

I need to figure out how to output the power set "in order", for example:

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

Doing a little research, it seems as if the best option would be for me to run a sort before outputting. I am NOT allowed to use built in sorts, so I have found some example sorts for sorting a list:

(define (qsort e)
  (if (or (null? e) (<= (length e) 1)) 
    e
    (let loop ((left  null)    (right null)
               (pivot (car e)) (rest  (cdr e)))
      (if (null? rest)
         (append (append (qsort left) (list pivot)) (qsort right))
         (if (<= (car rest) pivot)
            (loop (append left (list (car rest))) right pivot (cdr rest))
            (loop left (append right (list (car rest))) pivot (cdr rest)))))))

I cannot figure out how I would go about sorting it based off of the second, or third element in one of the power sets though. Can anyone provide an example?

Answer 1

Here's a powerset function that returns the items in the correct order, without sorting. It requires Racket and uses its queues to implement breadth-first processing:

(require srfi/1 data/queue)
(define (powerset items)
  (define fifo (make-queue))
  (enqueue! fifo (cons '() items))
  (let loop ((result '()))
    (if (queue-empty? fifo)
        (reverse result)
        (let* ((head-entry (dequeue! fifo))
               (subset     (car head-entry))
               (rest-items (cdr head-entry)))
          (pair-for-each (lambda (next-items)
                           (enqueue! fifo (cons (cons (car next-items) subset)
                                                (cdr next-items))))
                         rest-items)
          (loop (cons (reverse subset) result))))))

We maintain a FIFO queue of pairs, each consisting of a subset (in reversed order) and a list of items not included in it, starting with an empty subset so all the original items are still not included in it.

For each such pair, we collect the subset into the result list, and also extend the queue by extending this subset by each item from the not-included items. Processing stops when the queue is empty.

Because we extend subsets each time by one element only, and in order, the result is ordered too.

Answer 2

Here's a compare function that should work for your needs. It assumes that the numbers in the two input arguments are sorted already.

(define (list-less? lst1 lst2)

  ;; Compare the contents of the lists.
  (define (helper l1 l2)

    ;; If two lists are identical, the answer is false.
    ;; This scenario won't be exercised in the problem.
    ;; It's here only for the sake of completeness.
    (if (null? l1)
      #f

      ;; If the first item of the second list is greater than
      ;; the first item, return true.
      (if (> (car l2) (car l1))
        #t
        (or (< (car l1) (car l2)) (helper (cdr l1) (cdr l2))))))

  ;; First compare the lengths of the input arguments.
  ;; A list of smaller length are assumed to be "less"
  ;; than list of greater length.
  ;; Only when the lists are of equal length, do we
  ;; compare the contents of the lists.
  (let ((len1 (length lst1)) (len2 (length lst2)))
    (if (> len1 len2)
      #f
      (or (< len1 len2) (helper lst1 lst2)))))