How to resolve the algorithm List rooted trees step by step in the Racket programming language
How to resolve the algorithm List rooted trees step by step in the Racket programming language
Table of Contents
Problem Statement
You came back from grocery shopping. After putting away all the goods, you are left with a pile of plastic bags, which you want to save for later use, so you take one bag and stuff all the others into it, and throw it under the sink. In doing so, you realize that there are various ways of nesting the bags, with all bags viewed as identical. If we use a matching pair of parentheses to represent a bag, the ways are: For 1 bag, there's one way: for 2 bags, there's one way: for 3 bags, there are two: for 4 bags, four: Note that because all bags are identical, the two 4-bag strings ((())()) and (()(())) represent the same configuration. It's easy to see that each configuration for n bags represents a n-node rooted tree, where a bag is a tree node, and a bag with its content forms a subtree. The outermost bag is the tree root. Number of configurations for given n is given by OEIS A81.
Write a program that, when given n, enumerates all ways of nesting n bags. You can use the parentheses notation above, or any tree representation that's unambiguous and preferably intuitive. This task asks for enumeration of trees only; for counting solutions without enumeration, that OEIS page lists various formulas, but that's not encouraged by this task, especially if implementing it would significantly increase code size. As an example output, run 5 bags. There should be 9 ways.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm List rooted trees step by step in the Racket programming language
Source code in the racket programming language
#lang racket
(require racket/splicing data/order)
(define (filtered-cartesian-product #:f (fltr (λ (cand left) #t)) l . more-ls)
(let inr ((lls (cons l more-ls)) (left null))
(match lls
[(list) '(())]
[(cons lla lld)
(for*/list ((a (in-list (filter (curryr fltr left) lla)))
(d (in-list (inr lld (cons a left)))))
(cons a d))])))
;; The "order" of an LRT
(define LRT-order (match-lambda [(list (app LRT-order o) ...) (apply + 1 o)]))
;; Some order for List Rooted Trees
(define LRT<=
(match-lambda**
[(_ (list)) #t]
[((and bar (app LRT-order baro)) (cons (and badr (app LRT-order badro)) bddr))
(and (or (< baro badro) (not (eq? '> (datum-order bar badr)))) (LRT<= badr bddr))]))
(splicing-letrec ((t# (make-hash '((1 . (())))))
(p# (make-hash '((0 . (()))))))
;; positive-integer -> (listof (listof positive-integer))
(define (partitions N)
(hash-ref! p# N
(λ () (for*/list ((m (in-range 1 (add1 N)))
(p (partitions (- N m)))
#:when (or (null? p) (>= m (car p))))
(cons m p)))))
;; positive-integer -> (listof trees)
(define (LRTs N)
(hash-ref! t# N
(λ ()
;; sub1 because we will use the N'th bag to wrap the lot!
(define ps (partitions (sub1 N)))
(append*
(for/list ((p ps))
(apply filtered-cartesian-product (map LRTs p) #:f LRT<=)))))))
(module+ main
(for-each displayln (LRTs 5))
(equal? (map (compose length LRTs) (range 1 (add1 13)))
'(1 1 2 4 9 20 48 115 286 719 1842 4766 12486))) ;; https://oeis.org/A000081
You may also check:How to resolve the algorithm Sequence of non-squares step by step in the Smalltalk programming language
You may also check:How to resolve the algorithm Ramer-Douglas-Peucker line simplification step by step in the Openscad programming language
You may also check:How to resolve the algorithm Long primes step by step in the 11l programming language
You may also check:How to resolve the algorithm Undefined values step by step in the Common Lisp programming language
You may also check:How to resolve the algorithm Roman numerals/Encode step by step in the Io programming language