File: comgen.mc

package info (click to toggle)
maxima 5.6-17
  • links: PTS
  • area: main
  • in suites: woody
  • size: 30,572 kB
  • ctags: 47,715
  • sloc: ansic: 154,079; lisp: 147,553; asm: 45,843; tcl: 16,744; sh: 11,057; makefile: 7,198; perl: 1,842; sed: 334; fortran: 24; awk: 5
file content (45 lines) | stat: -rw-r--r-- 1,894 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
;;;;;;;;;;;;;;;;;;; -*- Mode: Lisp; Package: Macsyma -*- ;;;;;;;;;;;;;;;;;;;
;;;     (c) Copyright 1982 Massachusetts Institute of Technology         ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(macsyma-module ComGen)

   ;*********************************************************************
   ;****************                                   ******************
   ;**************** Combinatorial Generating Routines ******************
   ;****************                                   ******************
   ;*********************************************************************

;;; Currently this includes a routine $LIST_PERMS for generating a list
;;; of all permutations of the elements of a given list. This should be
;;; generalized to a function $MAP_PERMS which maps a given function over
;;; all permutations without necessarily constructing the list of all
;;; permutations. Similar routines should be provided for generating
;;; ordered and unordered combinations (I already have a lisp version
;;; of these in ALGBRA;TOPOL >. ---Bil


#+Maclisp
(declare (mapex T))

(defun all_permutations (elts)
   (if (null elts) (ncons () )
      (mapcan #'(lambda (sub_perm)
		   (permute_an_elt_through (car elts) sub_perm))
	      (all_permutations (cdr elts)))))

(defun permute_an_elt_through (elt elts)
   (if (null elts) (ncons (ncons elt))
      (cons (cons elt elts)
	    (mapcar #'(lambda (sub_perm_thru) (cons (car elts) sub_perm_thru))
		    (permute_an_elt_through elt (cdr elts))))))

(defun $list_perms (mlist)
   (if ($listp mlist)
       (cons '(MLIST) (mapcar #'(lambda (x) (cons '(MLIST) x))
			      (all_permutations (cdr mlist))))
      (merror "The argument to LIST_PERMS was not a list:~%~M" mlist)))

;;; This is for a temporary backwards compatible definition for ASB.

(defun $permutations (mlist) ($list_perms mlist))