|
(Common Lisp)
(defparameter all '(((1 1)))) ; the first element of each pair represents a total path length, the second element represents how many trees of that size have the same path length
(defun combine-duplicates (list1) ; takes a list of pairs and merges any pairs with the same first number, by adding their second number together
(let*
((list (sort list1 #'(lambda (a b) (< (first a) (first b)))))
(place list))
(loop
(when (null (cdr place)) (return))
(if (= (first (car place)) (first (cadr place)))
(progn
(incf (second (car place)) (second (cadr place)))
(setf (cdr place) (cddr place)))
(setf place (cdr place))))
list))
(defun combine (num a b) ; combines 2 trees's path lengths into a larger tree, num is the number of element contained in both trees and the new root
(list (+ num (first a) (first b))
(* (second a) (second b)))) ; the numbers of possible trees are multiplied because each possible way of choosing one possibility from each, should be counted
(defun map-all (func list1 list2) ; this takes a function and two lists and feeds the function one element from each, in all combinations
(mapcan #'(lambda (b)
(mapcar #'(lambda (a) (funcall func a b)) list1))
list2))
(defun path-lengths (x) ; computes the list of possible total path lengths for a tree with x nodes
(when (<= (length all) x) ; if we have not already computed the solution for this size, we do so
(let ((num (1+ (* 2 x)))) ; because we are working with fully leafed trees, we calculate the number of elements when we are given just the number of nodes
(nconc all (list ; we stick the results for this size onto the end of our list of all results
(combine-duplicates
(mapcan ; we try all ways of splitting x-1 indistinguishable nodes into two groups
#'(lambda (n) (map-all
#'(lambda (a b) (combine num a b)) ; we get all possible trees by recursing to all possible trees for each branch
(path-lengths n) ; the path lengths of all possible trees with some of our nodes
(path-lengths (- x n 1)))) ; the path lengths of all possible trees with the rest of our nodes
(loop for i below x collect i))))))) ; list of 0 to x-1
(elt all x)) ; return the solutions for this size
(progn (path-lengths 40) nil) ; fills up the 'all' with results, change 40 to however many elements of this sequence you want (progn ... nil is so that it doesn't cover the screen with numbers)
(defun find-max (seq) ; finds the pair with the greatest number of trees
(let ((max '(0 0)))
(loop for i in seq do
(when (> (second i) (second max))
(setf max i)))
max))
(loop for a in all collect (first (find-max a))) ; gives you the path length with the greatest number of trees, for each size
| 