java - 将方案翻译成java

Question

在阅读 SICP 期间，我通过练习 2.32 进行鼓励。

We can represent a set as a list of distinct elements, and we can represent the set of all subsets of the set as a list of lists. For example, if the set is (1 2 3 4), then the set of all subsets is (() (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)). Complete the following definition of a procedure that generates the set of subsets of a set and give a clear explanation of why it works:

(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
        (append rest (map ⟨??⟩ rest)))))

(define (subset s)
     (if (null? s)
         (list '())
         (let ((rest (subset (cdr s))))
             (append
                  rest (map (lambda (x) (cons (car s) x)) rest)
             )
         )))

(subset '(1 2 3 4))
1 ]=> 
;Value 15: (() (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))

我可以用模式来做到这一点，但之后我想知道:“我可以用java做什么？”。我思考这个问题是因为我无法理解为什么如果我们在每个递归中都获得前一个递归的子列表，它会起作用。

当然我可以用其他方式解决。 例如，使用这种方法:所有可能的组合 2^N-1，对于我们的例子，这是 2^4-1

number binary result
1      0001    (4)
2      0010    (3)
3      0011    (3,4)
4      0100    (2)
5      0101    (2,4)
6      0110    (2,3)
7      0111    (2,3,4)
8      1000    (1)
9      1001    (1,4)
10     1010    (1,3)
11     1011    (1,3,4)
12     1100    (1,2)
13     1101    (1,2,4)
14     1110    (1,2,3)
15     1111    (1,2,3,4)

我重写了一些方案代码以与java代码相似

(define (subset s)
     (if (null? s)
         (list '())
         ((lambda (rest)
                 (append rest (map (lambda (x) (cons (car s) x)) rest))
         )(subset (cdr s)))
     )
)
(subset '(1 2 3))
1 ]=> 
;Value 19: (() (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))

我编写了我的java实现

import java.util.*;
import java.util.function.UnaryOperator;

import static java.util.Arrays.asList;
import static java.util.stream.Collectors.*;

public class A {
    public static void main(String[] args) {
        List<Integer> l = new ArrayList<>(asList(1,2,3));

        System.out.println(subset(l));
    }

    private static List<List<Integer>> subset(final List<Integer> s) {
        if (s.isEmpty()) return new ArrayList<>();

        final UnaryOperator<List<List<Integer>>> f = (final List<List<Integer>> rest) -> {
            final List<List<Integer>> collect = rest.stream()
                    .map(x -> {
                        List<Integer> r = new ArrayList<>();
                        r.add(s.get(0));
                        r.addAll(x);

                        return r;
                    })
                    .collect(toList());

            rest.addAll(collect);

            return rest;
        };

        return f.apply(subset(new ArrayList<>(s.subList(1, s.size()))));
    }

}

在java中我有一个空列表(我将Set更改为List以便无需任何技巧即可获得索引0)。正如我之前提到的，我理解为什么我的 java 返回空列表，但我不明白如何修复我的 java 代码，使其行为与方案匹配。

Answer 1

您的基本情况是错误的。方案表达式 (list '())不计算为空列表:它计算为单元素列表，其元素是空列表。在 Java 中，您编写了 new ArrayList<>()作为基本情况，这是一个空列表。相反，使用类似 Arrays.asList(new ArrayList<>()) 的内容.