list - 查找X的所有可能列表(Finding all possible lists of X)

Question

I would like to create a function construct-tuples that consumes a list of length m and a Nat n and produces all possible n-tuples of a list of the elements of the consumed list.

(我想创建一个功能构造元组，它使用长度为m和Nat n的列表，并生成所消耗列表的元素的列表的所有可能的n元组。)

The following check-expects give an idea of what the function should produce:

(以下检查期望给出了该函数应产生的信息：)

(check-expect (construct-tuples '(+ -) 3)
              '((+ + +) (+ + -) (+ - +) (+ - -)
                        (- + +) (- + -) (- - +) (- - -)))
(check-expect (construct-tuples empty 3) (list empty))
(check-expect (construct-tuples '(+ -) 0) (list empty))
(check-expect (construct-tuples '(+ - * /) 4)
              (list
               (list '+ '+ '+ '+)
               (list '+ '+ '+ '-)
               (list '+ '+ '+ '*)
               (list '+ '+ '+ '/)
               (list '+ '+ '- '+)
               (list '+ '+ '- '-)
               (list '+ '+ '- '*)
               (list '+ '+ '- '/)
               (list '+ '+ '* '+)
               (list '+ '+ '* '-)
               (list '+ '+ '* '*)
               (list '+ '+ '* '/)
               (list '+ '+ '/ '+)
               (list '+ '+ '/ '-)
               (list '+ '+ '/ '*)
               (list '+ '+ '/ '/)
               (list '+ '- '+ '+)
               (list '+ '- '+ '-)
               (list '+ '- '+ '*)
               (list '+ '- '+ '/)
               (list '+ '- '- '+)
               (list '+ '- '- '-)
               (list '+ '- '- '*)
               (list '+ '- '- '/)
               (list '+ '- '* '+)
               (list '+ '- '* '-)
               (list '+ '- '* '*)
               (list '+ '- '* '/)
               (list '+ '- '/ '+)
               (list '+ '- '/ '-)
               (list '+ '- '/ '*)
               (list '+ '- '/ '/)
               (list '+ '* '+ '+)
               (list '+ '* '+ '-)
               (list '+ '* '+ '*)
               (list '+ '* '+ '/)
               (list '+ '* '- '+)
               (list '+ '* '- '-)
               (list '+ '* '- '*)
               (list '+ '* '- '/)
               (list '+ '* '* '+)
               (list '+ '* '* '-)
               (list '+ '* '* '*)
               (list '+ '* '* '/)
               (list '+ '* '/ '+)
               (list '+ '* '/ '-)
               (list '+ '* '/ '*)
               (list '+ '* '/ '/)
               (list '+ '/ '+ '+)
               (list '+ '/ '+ '-)
               (list '+ '/ '+ '*)
               (list '+ '/ '+ '/)
               (list '+ '/ '- '+)
               (list '+ '/ '- '-)
               (list '+ '/ '- '*)
               (list '+ '/ '- '/)
               (list '+ '/ '* '+)
               (list '+ '/ '* '-)
               (list '+ '/ '* '*)
               (list '+ '/ '* '/)
               (list '+ '/ '/ '+)
               (list '+ '/ '/ '-)
               (list '+ '/ '/ '*)
               (list '+ '/ '/ '/)
               (list '- '+ '+ '+)
               (list '- '+ '+ '-)
               (list '- '+ '+ '*)
               (list '- '+ '+ '/)
               (list '- '+ '- '+)
               (list '- '+ '- '-)
               (list '- '+ '- '*)
               (list '- '+ '- '/)
               (list '- '+ '* '+)
               (list '- '+ '* '-)
               (list '- '+ '* '*)
               (list '- '+ '* '/)
               (list '- '+ '/ '+)
               (list '- '+ '/ '-)
               (list '- '+ '/ '*)
               (list '- '+ '/ '/)
               (list '- '- '+ '+)
               (list '- '- '+ '-)
               (list '- '- '+ '*)
               (list '- '- '+ '/)
               (list '- '- '- '+)
               (list '- '- '- '-)
               (list '- '- '- '*)
               (list '- '- '- '/)
               (list '- '- '* '+)
               (list '- '- '* '-)
               (list '- '- '* '*)
               (list '- '- '* '/)
               (list '- '- '/ '+)
               (list '- '- '/ '-)
               (list '- '- '/ '*)
               (list '- '- '/ '/)
               (list '- '* '+ '+)
               (list '- '* '+ '-)
               (list '- '* '+ '*)
               (list '- '* '+ '/)
               (list '- '* '- '+)
               (list '- '* '- '-)
               (list '- '* '- '*)
               (list '- '* '- '/)
               (list '- '* '* '+)
               (list '- '* '* '-)
               (list '- '* '* '*)
               (list '- '* '* '/)
               (list '- '* '/ '+)
               (list '- '* '/ '-)
               (list '- '* '/ '*)
               (list '- '* '/ '/)
               (list '- '/ '+ '+)
               (list '- '/ '+ '-)
               (list '- '/ '+ '*)
               (list '- '/ '+ '/)
               (list '- '/ '- '+)
               (list '- '/ '- '-)
               (list '- '/ '- '*)
               (list '- '/ '- '/)
               (list '- '/ '* '+)
               (list '- '/ '* '-)
               (list '- '/ '* '*)
               (list '- '/ '* '/)
               (list '- '/ '/ '+)
               (list '- '/ '/ '-)
               (list '- '/ '/ '*)
               (list '- '/ '/ '/)
               (list '* '+ '+ '+)
               (list '* '+ '+ '-)
               (list '* '+ '+ '*)
               (list '* '+ '+ '/)
               (list '* '+ '- '+)
               (list '* '+ '- '-)
               (list '* '+ '- '*)
               (list '* '+ '- '/)
               (list '* '+ '* '+)
               (list '* '+ '* '-)
               (list '* '+ '* '*)
               (list '* '+ '* '/)
               (list '* '+ '/ '+)
               (list '* '+ '/ '-)
               (list '* '+ '/ '*)
               (list '* '+ '/ '/)
               (list '* '- '+ '+)
               (list '* '- '+ '-)
               (list '* '- '+ '*)
               (list '* '- '+ '/)
               (list '* '- '- '+)
               (list '* '- '- '-)
               (list '* '- '- '*)
               (list '* '- '- '/)
               (list '* '- '* '+)
               (list '* '- '* '-)
               (list '* '- '* '*)
               (list '* '- '* '/)
               (list '* '- '/ '+)
               (list '* '- '/ '-)
               (list '* '- '/ '*)
               (list '* '- '/ '/)
               (list '* '* '+ '+)
               (list '* '* '+ '-)
               (list '* '* '+ '*)
               (list '* '* '+ '/)
               (list '* '* '- '+)
               (list '* '* '- '-)
               (list '* '* '- '*)
               (list '* '* '- '/)
               (list '* '* '* '+)
               (list '* '* '* '-)
               (list '* '* '* '*)
               (list '* '* '* '/)
               (list '* '* '/ '+)
               (list '* '* '/ '-)
               (list '* '* '/ '*)
               (list '* '* '/ '/)
               (list '* '/ '+ '+)
               (list '* '/ '+ '-)
               (list '* '/ '+ '*)
               (list '* '/ '+ '/)
               (list '* '/ '- '+)
               (list '* '/ '- '-)
               (list '* '/ '- '*)
               (list '* '/ '- '/)
               (list '* '/ '* '+)
               (list '* '/ '* '-)
               (list '* '/ '* '*)
               (list '* '/ '* '/)
               (list '* '/ '/ '+)
               (list '* '/ '/ '-)
               (list '* '/ '/ '*)
               (list '* '/ '/ '/)
               (list '/ '+ '+ '+)
               (list '/ '+ '+ '-)
               (list '/ '+ '+ '*)
               (list '/ '+ '+ '/)
               (list '/ '+ '- '+)
               (list '/ '+ '- '-)
               (list '/ '+ '- '*)
               (list '/ '+ '- '/)
               (list '/ '+ '* '+)
               (list '/ '+ '* '-)
               (list '/ '+ '* '*)
               (list '/ '+ '* '/)
               (list '/ '+ '/ '+)
               (list '/ '+ '/ '-)
               (list '/ '+ '/ '*)
               (list '/ '+ '/ '/)
               (list '/ '- '+ '+)
               (list '/ '- '+ '-)
               (list '/ '- '+ '*)
               (list '/ '- '+ '/)
               (list '/ '- '- '+)
               (list '/ '- '- '-)
               (list '/ '- '- '*)
               (list '/ '- '- '/)
               (list '/ '- '* '+)
               (list '/ '- '* '-)
               (list '/ '- '* '*)
               (list '/ '- '* '/)
               (list '/ '- '/ '+)
               (list '/ '- '/ '-)
               (list '/ '- '/ '*)
               (list '/ '- '/ '/)
               (list '/ '* '+ '+)
               (list '/ '* '+ '-)
               (list '/ '* '+ '*)
               (list '/ '* '+ '/)
               (list '/ '* '- '+)
               (list '/ '* '- '-)
               (list '/ '* '- '*)
               (list '/ '* '- '/)
               (list '/ '* '* '+)
               (list '/ '* '* '-)
               (list '/ '* '* '*)
               (list '/ '* '* '/)
               (list '/ '* '/ '+)
               (list '/ '* '/ '-)
               (list '/ '* '/ '*)
               (list '/ '* '/ '/)
               (list '/ '/ '+ '+)
               (list '/ '/ '+ '-)
               (list '/ '/ '+ '*)
               (list '/ '/ '+ '/)
               (list '/ '/ '- '+)
               (list '/ '/ '- '-)
               (list '/ '/ '- '*)
               (list '/ '/ '- '/)
               (list '/ '/ '* '+)
               (list '/ '/ '* '-)
               (list '/ '/ '* '*)
               (list '/ '/ '* '/)
               (list '/ '/ '/ '+)
               (list '/ '/ '/ '-)
               (list '/ '/ '/ '*)
               (list '/ '/ '/ '/)))

I found a way to do this using recursive calls to map, but it only works for finite values, so I was wondering if there was a way to make this arbitrary?

(我找到了一种使用递归映射的方法来做到这一点的方法，但是它仅适用于有限值，因此我想知道是否有一种方法可以使此方法变得任意？)

  ask by bob translate from so

Answer 1

You can indeed solve this using recursion.

(您确实可以使用递归解决此问题。)

There's no need to even call out to functions like map.

(甚至不需要调出诸如map之类的功能。)

The following is an implementation that I believe solves the problem:

(以下是我认为可以解决问题的实现：)

(define (construct-tuples symbols n)
  (if (zero? n)
      (list '())
      (let ((tuples-n-1 (construct-tuples symbols (sub1 n))))
        (for*/list ([tuple tuples-n-1]
                    [symbol symbols])
          (cons symbol tuple)))))

This solution works via recursion.

(此解决方案通过递归工作。)

The base case returns a list containing one empty list.

(基本情况返回一个包含一个空列表的列表。)

For each iteration, we get the list of possible tuples for n-1, and then for every symbol, create a new list, containing the original list, plus that symbol.

(对于每次迭代，我们获得n-1个可能的元组的列表，然后为每个符号创建一个新列表，其中包含原始列表以及该符号。)

To illustrate how this works, consider the following:

(为了说明这是如何工作的，请考虑以下几点：)

• We want to calculate (construct-tuples '(+ -) 3)

  (我们要计算(construct-tuples '(+ -) 3))

• This would first need to calculate (construct-tuples '(+ -) 2)

  (这首先需要计算(construct-tuples '(+ -) 2))

• Which would need to calculate (construct-tuples '(+ -) 1)

  (需要计算的内容(construct-tuples '(+ -) 1))

• Which would need to calculate (construct-tuples '(+ -) 0)

  (哪个需要计算(construct-tuples '(+ -) 0))

• ... the answer of which is (list '())

  (...答案是(list '()))

• For each symbol in '(+ -) we create a new list appending that symbol to '() .

  (对于'(+ -)每个符号，我们创建一个新列表，将该符号追加到'() 。)

  This returns (list '(+) '(-))

  (这将返回(list '(+) '(-)))

• For each symbol in '(+ -) , create a new list appending that symbol to each list in (list '(+) '(-)).

  (对于'(+ -)每个符号，创建一个新列表，将该符号附加到（list'（+）'（-））中的每个列表。)

  This will create 4 new lists (2x2).

  (这将创建4个新列表（2x2）。) (list '(+ +) '(+ -) '(- +) '(- -))

• Lastly, for each symbol in '(+ -) , create a new list for each of the lists that we got from the recursive iteration (8 lists will be created (4x2))

  (最后，为'(+ -)每个符号，为我们从递归迭代中获得的每个列表创建一个新列表（将创建8个列表（4x2））)

Thes for*/list function does a lot of the heavy lifting in this function.

(for*/list功能在此功能中起了很多重的作用。)

What this does is iterates for every possible combination of the various arguments producing a list of the various answers.

(这样做是针对各种参数的每种可能组合进行迭代，从而产生各种答案的列表。)

(for*/list ([x '(+ -)]
            [y '(* /)])
  (list x y))

This will produce a list of every possible tuple between '(x -) and '(* /)

(这将产生'（x-）和'（**）之间每个可能的元组的列表)