具有有序输出的 Scheme 中的功率集 [英] Power set in Scheme with ordered output

问题描述

所以我熟悉使用 Scheme 创建幂集的算法，如下所示:

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)))))

因此，对于 (1, 2, 3, 4)，将输出:

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?

推荐答案

这是一个可以满足您需求的比较函数.它假设两个输入参数中的数字已经排序.

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)))))

这篇关于具有有序输出的 Scheme 中的功率集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！