Getting all possible combinations of x booleans (R

问题:

i have a problem. How do I get all possible combinations of x booleans in Racket? (on a low language level)

I need something like that:

For x=1 (list (list false) (list true))

For x=2 (list (list false false) (list false true) (list true false) (list true true))

For x=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))

etc.

I have no idea how to do this in Racket.

Thanks you!

回答1:

Here is one way to convert a number to a list of booleans. To generate all combinations, use it in a loop as you described.

  (map (λ (x) (eqv? x #\1)) 
       (string->list (number->string 12345 2)))

Replace 12345 with any number.

回答2:

You're asking for all n-size permutations (not combinations!) of the list '(#t #f), with repetitions allowed. Adapting this answer for Racket:

(define (permutations size elements)
  (if (zero? size)
      '(())
      (append-map (lambda (p)
                    (map (lambda (e)
                           (cons e p))
                         elements))
                  (permutations (sub1 size) elements))))

Use it like this:

(permutations 3 '(#t #f))

=> '((#t #t #t) (#f #t #t) (#t #f #t) (#f #f #t)
     (#t #t #f) (#f #t #f) (#t #f #f) (#f #f #f))

回答3:

What you're actually doing is sort of building the powerset for a set of size x.

A powerset is the set of all possible subsets. For example, the powerset of (list 1 2 3) is (list (list 1 2 3) (list 1 2) (list 1 3) (list 1) (list 2 3) (list 2) (list 3) empty).

(A set is a subset of itself and the empty set is a subset of all sets.)

Why what you're doing describes the powerset is because an element can either be or not be in a subset. So apply (list true true true) to (list 1 2 3) will return (list 1 2 3) and (list false true true) will return (list 2 3).

This is my code for your problem.

(define baselist (list  (list true) (list false)))
;; List1 List2 -> List of Lists
;; Where List1 is any list of lists, and list2 is a list of lists of size 2
;; and all of the lists within list 2 has one element
(define (list-combination list-n list-two)
  (cond [(empty? list-n) empty]
        [else (cons (append (first list-n) (first list-two))
                    (cons (append (first list-n) (second list-two))
                          (list-combination (rest list-n) list-two)))]))
;; tflist Number -> List of Boolean Lists
;; creates baselistn
(define (tflist n)
  (cond [(= 1 n) baselist]
        [else (list-combination (tlist (sub1 n)) baselist)]))

So (tflist 3) will return your original problem. Now to make a powerset, you can do the following...

;; subset List1 ListofBooleans -> List
;; Determines which elements of a set to create a subset of
;; List1 and LoB are of the same length
(define (subset set t-f-list)
  (cond [(empty? t-f-list) empty]
        [(first t-f-list) (cons (first set) (subset (rest set) (rest t-f-list)))]
        [else (subset (rest set) (rest t-f-list))]))
;;powerset set -> Powerset
;; produces a  powerset of a set
(define (powerset set)
  (local ((define upperbound (expt 2 (length set)))
          (define tflist (tlist (length set)))
          (define (powerset set n)
            (cond [(= n upperbound) empty]
                  [else (cons (subset set (list-ref tflist n)) (powerset set (add1 n)))])))
    (powerset set 0)))