Andrew Cooke | Contents | Latest | RSS | Previous | Next

C[omp]ute

Welcome to my blog, which was once a mailing list of the same name and is still generated by mail. Please reply via the "comment" links.

Always interested in offers/projects/new ideas. Eclectic experience in fields like: numerical computing; Python web; Java enterprise; functional languages; GPGPU; SQL databases; etc. Based in Santiago, Chile; telecommute worldwide. CV; email.

Personal Projects

Choochoo Training Diary

Last 100 entries

[Programming] React Leaflet; AliExpress Independent Sellers; Applebaum - Twilight of Democracy; [Politics] Back + US Elections; [Programming,Exercise] Simple Timer Script; [News] 2019: The year revolt went global; [Politics] The world's most-surveilled cities; [Bike] Hope Freehub; [Restaurant] Mama Chau's (Chinese, Providencia); [Politics] Brexit Podcast; [Diary] Pneumonia; [Politics] Britain's Reichstag Fire moment; install cairo; [Programming] GCC Sanitizer Flags; [GPU, Programming] Per-Thread Program Counters; My Bike Accident - Looking Back One Year; [Python] Geographic heights are incredibly easy!; [Cooking] Cookie Recipe; Efficient, Simple, Directed Maximisation of Noisy Function; And for argparse; Bash Completion in Python; [Computing] Configuring Github Jekyll Locally; [Maths, Link] The Napkin Project; You can Masquerade in Firewalld; [Bike] Servicing Budget (Spring) Forks; [Crypto] CIA Internet Comms Failure; [Python] Cute Rate Limiting API; [Causality] Judea Pearl Lecture; [Security, Computing] Chinese Hardware Hack Of Supermicro Boards; SQLAlchemy Joined Table Inheritance and Delete Cascade; [Translation] The Club; [Computing] Super Potato Bruh; [Computing] Extending Jupyter; Further HRM Details; [Computing, Bike] Activities in ch2; [Books, Link] Modern Japanese Lit; What ended up there; [Link, Book] Logic Book; Update - Garmin Express / Connect; Garmin Forerunner 35 v 230; [Link, Politics, Internet] Government Trolls; [Link, Politics] Why identity politics benefits the right more than the left; SSH Forwarding; A Specification For Repeating Events; A Fight for the Soul of Science; [Science, Book, Link] Lost In Math; OpenSuse Leap 15 Network Fixes; Update; [Book] Galileo's Middle Finger; [Bike] Chinese Carbon Rims; [Bike] Servicing Shimano XT Front Hub HB-M8010; [Bike] Aliexpress Cycling Tops; [Computing] Change to ssh handling of multiple identities?; [Bike] Endura Hummvee Lite II; [Computing] Marble Based Logic; [Link, Politics] Sanity Check For Nuclear Launch; [Link, Science] Entropy and Life; [Link, Bike] Cheap Cycling Jerseys; [Link, Music] Music To Steal 2017; [Link, Future] Simulated Brain Drives Robot; [Link, Computing] Learned Index Structures; Solo Air Equalization; Update: Higher Pressures; Psychology; [Bike] Exercise And Fuel; Continental Race King 2.2; Removing Lowers; Mnesiacs; [Maths, Link] Dividing By Zero; [Book, Review] Ray Monk - Ludwig Wittgenstein: The Duty Of Genius; [Link, Bike, Computing] Evolving Lacing Patterns; [Jam] Strawberry and Orange Jam; [Chile, Privacy] Biometric Check During Mail Delivery; [Link, Chile, Spanish] Article on the Chilean Drought; [Bike] Extended Gear Ratios, Shimano XT M8000 (24/36 Chainring); [Link, Politics, USA] The Future Of American Democracy; Mass Hysteria; [Review, Books, Links] Kazuo Ishiguro - Never Let Me Go; [Link, Books] David Mitchell's Favourite Japanese Fiction; [Link, Bike] Rear Suspension Geometry; [Link, Cycling, Art] Strava Artwork; [Link, Computing] Useful gcc flags; [Link] Voynich Manuscript Decoded; [Bike] Notes on Servicing Suspension Forks; [Links, Computing] Snap, Flatpack, Appimage; [Link, Computing] Oracle is leaving Java (to die); [Link, Politics] Cubans + Ultrasonics; [Book, Link] Laurent Binet; VirtualBox; [Book, Link] No One's Ways; [Link] The Biggest Problem For Cyclists Is Bad Driving; [Computing] Doxygen, Sphinx, Breathe; [Admin] Brokw Recent Permalinks; [Bike, Chile] Buying Bearings in Santiago; [Computing, Opensuse] Upgrading to 42.3; [Link, Physics] First Support for a Physics Theory of Life; [Link, Bike] Peruvian Frame Maker; [Link] Awesome Game Theory Tit-For-Tat Thing; [Food, Review] La Fabbrica - Good Italian Food In Santiago; [Link, Programming] MySQL UTF8 Broken; [Link, Books] Latin American Authors

© 2006-2017 Andrew Cooke (site) / post authors (content).

Permute Fucntion (Scheme)

From: "andrew cooke" <andrew@...>

Date: Tue, 14 Aug 2007 22:53:01 -0400 (CLT)

":";exec snow -- "$0" "$@"

(package* permute/v1.0.0
  (provide: (define (permute lst))))

; generates a list of all permutations
; assumes all values in original list are unique (under equal?)
(define (permute lst)
  (case (length lst)
    ((0) '())
    ((1) (list lst))
    (else (flat-map (lambda (head)
                      (map (lambda (perm) (cons head perm))
                           (permute (except head lst))))
                    lst))))

(define (flat-map f lst) (flat-map-acc f lst '()))
(define (flat-map-acc f lst acc)
  (if (null? lst)
      acc
      (flat-map-acc f (cdr lst) (append acc (f (car lst))))))

; this does not attempt to keep any kind of ordering
(define (except x lst) (except-acc x lst '()))
(define (except-acc x lst acc)
  (if (null? lst)
      acc
      (let ((head (car lst))
            (tail (cdr lst)))
        (if (equal? x head)
            (append acc tail)
            (except-acc x tail (cons head acc))))))


(test*
 (define (dup x) (list x x))
 (expect* (equal? '() (flat-map dup '())))
 (expect* (equal? '(1 1) (flat-map dup '(1))))
 (expect* (equal? '(1 1 2 2) (flat-map dup '(1 2)))))

(test*
 (expect* (equal? '() (except 0 '())))
 (expect* (equal? '() (except 1 '(1))))
 (expect* (equal? '(2) (except 1 '(1 2))))
 (expect* (equal? '(3 2 1) (except 0 '(1 2 3))))
 (expect* (equal? '(2 3) (except 1 '(1 2 3))))
 (expect* (equal? '(1 3) (except 2 '(1 2 3))))
 (expect* (equal? '(2 1) (except 3 '(1 2 3)))))

(test*
 (expect* (equal? '() (permute '())))
 (expect* (equal? '((1)) (permute '(1))))
 (expect* (equal? '((1 2)(2 1)) (permute '(1 2))))
 (expect* (equal? '((1 2 3)(1 3 2)(2 1 3)(2 3 1)(3 2 1)(3 1 2))
                  (permute '(1 2 3)))))

Improved Permutation Function (Start of List Library)

From: "andrew cooke" <andrew@...>

Date: Wed, 15 Aug 2007 12:07:38 -0400 (CLT)

":";exec snow -- "$0" "$@"

; library of list-related functions

(package* ac-lists/v1.0.0
  (provide:
      ; abstract the typical patter used to recurse over lists
      (define-syntax acl-list-process
        (syntax-rules (null?)
          ((_ ((null? list) null-body)
              ((head tail) body))
           (if (null? list)
               null-body
               (let ((head (car list))
                     (tail (cdr list)))
                 body)))))
    (define (acl-filter pred lst))
    (define (acl-filter-acc pred lst acc))
    (define (acl-except x lst))
    (define (acl-flat-map fun lst))
    (define (acl-flat-map-acc fun lst acc))
    (define (acl-permute lst))
    ))

; remove all values that match predicate from a list
(define (acl-filter pred lst) (reverse (acl-filter-acc pred lst '())))
(define (acl-filter-acc pred lst acc)
  (acl-list-process
   ((null? lst) acc)
   ((head tail) (if (pred head)
                    (acl-filter-acc pred tail acc)
                    (acl-filter-acc pred tail (cons head acc))))))

(test*
 (define (one? x) (= 1 x))
 (expect* (equal? '() (acl-filter one? '())))
 (expect* (equal? '() (acl-filter one? '(1))))
 (expect* (equal? '(2) (acl-filter one? '(2))))
 (expect* (equal? '(2 3) (acl-filter one? '(2 1 3)))))

; exclude instances of a particular value
(define (acl-except x lst) (acl-filter (lambda (y) (equal? x y)) lst))

(test*
 (expect* (equal? '() (acl-except 0 '())))
 (expect* (equal? '() (acl-except 1 '(1))))
 (expect* (equal? '(2) (acl-except 1 '(1 2))))
 (expect* (equal? '(1 2 3) (acl-except 0 '(1 2 3)))))

; map with append instead of cons
(define (acl-flat-map fun lst) (reverse (acl-flat-map-acc fun lst '())))
(define (acl-flat-map-acc fun lst acc)
  (acl-list-process
   ((null? lst) acc)
   ((head tail) (acl-flat-map-acc fun tail (append (fun head) acc)))))

(test*
 (define (dup x) (list x x))
 (expect* (equal? '() (acl-flat-map dup '())))
 (expect* (equal? '(1 1) (acl-flat-map dup '(1))))
 (expect* (equal? '(1 1 2 2) (acl-flat-map dup '(1 2)))))

; a list of all permutations
; assumes all values in original list are unique (under equal?)
(define (acl-permute lst)
  (define (perm-rest x)
    (define (cons-x rest) (cons x rest))
    (let ((rest (acl-except x lst)))
      (map cons-x (acl-permute rest))))
  (acl-list-process
   ((null? lst) '())
   ((head tail) (if (null? tail)
                    (list lst)
                    (acl-flat-map perm-rest lst)))))

(test*
 (expect* (equal? '() (acl-permute '())))
 (expect* (equal? '((1)) (acl-permute '(1))))
 (expect* (equal? '((1 2)(2 1)) (acl-permute '(1 2))))
 (expect* (equal? '((1 3 2)(1 2 3)(2 3 1)(2 1 3)(3 2 1)(3 1 2))
                  (acl-permute '(1 2 3)))))

Comment on this post