Permutation of list of lists of booleans in Racket

user_13972510 0
Viewed 460

I'd like to create a function that: given a natural number, returns a list of lists with all the possible values for n propositional variables.

e.g, given n = 3, it should return:

(list  
 (list #false #false #false)  
 (list #false #false #true)  
 (list #false #true #false)  
 (list #false #true #true)  
 (list #true #false #false)  
 (list #true #false #true)  
 (list #true #true #false)  
 (list #true #true #true))

I know the amount of possible combinations is 2^n, but i am clueless about how to solve it on racket.

permutation racket combinatorics boolean list
2 Answers

You can use the cartesian-product function. (cartesian-product (list #false #true) (list #false #true) (list #false #true)) returns the same thing as your n = 3 example. The number of copies of (list #false #true) in the arguments should come from n.

(cartesian-product (list #false #true) ...n)

To do this, you can use cartesian-product with apply to give an arbitrary number of arguments in a list, and make-list to make a list of N elements:

(define (permutation-of-lists n)
  (apply cartesian-product (make-list n (list #false #true))))

Using it:

> (permutation-of-lists 0)
(list '())
> (permutation-of-lists 1)
(list (list #false) (list #true))
> (permutation-of-lists 2)
(list (list #false #false)
      (list #false #true)
      (list #true #false)
      (list #true #true))
> (permutation-of-lists 3)
(list (list #false #false #false)
      (list #false #false #true)
      (list #false #true #false)
      (list #false #true #true)
      (list #true #false #false)
      (list #true #false #true)
      (list #true #true #false)
      (list #true #true #true))
user_54325010

You can potentially do something like:


(define (permutation-of-lists n)
  (if (= 1 n)
      '((#t) (#f))
      (append
        (map (λ (p) (cons #t p)) (permutation-of-lists (sub1 n)))
        (map (λ (p) (cons #f p)) (permutation-of-lists (sub1 n))))))

This works for any n >= 1. You can also optionally add a case to handle n = 0. This essentially builds up these lists by appending both possible copies to the lists generated for n - 1 - one appends #true and the other appends #false to the front (and we keep both copies).

user_47803300
Related