Разделение номера в R5RS

Во время стажировки меня попросили написать программу R5RS, которая создает функцию, скажем, два подмножества. Эта функция должна возвращать #t, если список L содержит два подмножества с одинаковыми суммами элементов и с равным количеством элементов, в противном случае она возвращает #f. Он принимает на вход список L (только положительные числа) и некоторые параметры (которые я считаю полезными. Нет условий на количество параметров), все равные 0 в начале.

Насколько я помню, требования были следующими: - Не определять другие функции и не вызывать их внутри функции "два подмножества". - Он может использовать только следующие конструкции: null?, cond, car, cdr, else, + ,=, not, and, #t, #f, two-subsets (сам для рекурсивного вызова), имена параметров, такие как список, сумма, ... и т. д., числовые константы и круглые скобки.

Были приведены некоторые примеры результатов, которые мы должны были получить, скажем:

(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.

Я начал с того, что написал подпись, которая, как мне кажется, должна быть примерно такой:

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

Проблема действительно сложная, и ее сложность явно превышает O(n), я читал об этом на https://en.wikipedia.org/wiki/Partition_problem .

Я попытался начать с определения алгоритма, прежде чем кодировать его. Я подумал о том, чтобы взять в качестве параметров: сумму списка L, поэтому в моих условиях я буду перебирать только те комбинации, сумма которых равна ‹= sum(L)/2. Делая это, я могу немного уменьшить сложность проблемы, но все же я не мог понять, как это сделать.

Это выглядит как интересная проблема, и я действительно хочу узнать о ней больше.


lisp racket r5rs
person Benz    schedule 26.04.2017    source источник
comment
Это не совсем проблема разделения, поскольку вы не указываете, что подмножества должны разделять набор. Учитывая это, я думаю, вам также нужно указать, что подмножества не должны быть пустыми, или это всегда верно, поскольку {}, {} - это два таких подмножества.   -  person    schedule 26.04.2017

Ответы (1)


arrow_upward
2
arrow_downward

Вот версия, которая не зависит от того, все ли числа положительны. Я достаточно уверен, что, зная, что они есть, вы можете добиться гораздо большего.

Обратите внимание, что это предполагает, что:

  • раздел не обязательно должен быть исчерпывающим;
  • но наборы не должны быть пустыми.

Мне было бы очень интересно увидеть версию, которая опирается на элементы списка +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)]))
person Community    schedule 26.04.2017
comment
Спасибо, это работает. В чем разница при добавлении Lambda? - person Benz; 27.04.2017
comment
@Benz (define (x ...) ...) — это сокращение от (define x (lambda (...) ...). - person ; 27.04.2017
comment
@tfb Я не думаю, что наличие всех положительных чисел помогает. Мы можем перейти от исходной задачи к положительной, добавив достаточно большую константу. Это не меняет условий, когда функция должна возвращать true/false. Вычисление достаточно большой константы — это O(n). Таким образом, какой бы ни была эффективность алгоритма для положительных чисел, алгоритм для всех чисел будет иметь одинаковую эффективность. - person Andrei; 08.05.2017