You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
91 lines
2.3 KiB
Racket
91 lines
2.3 KiB
Racket
;; Copyright 2019 Edward L. Platt <elplatt@alum.mit.edu>
|
|
;;
|
|
;; This module implements a family of graphs based on permutations of
|
|
;; sylvester-radix numbers.
|
|
|
|
#lang racket
|
|
|
|
(provide
|
|
|
|
;; Generate the list of graph nodes.
|
|
;;
|
|
;; Params:
|
|
;; m: Dimensionality of sylvester-radix numbers used as vertices.
|
|
;;
|
|
;; Example:
|
|
;; > (sylvester-nodes 2)
|
|
;; '((0 0) (1 0) (0 1) (1 1) (0 2) (1 2))
|
|
sylvester-nodes
|
|
|
|
;; Generate the list of directed graph edges.
|
|
;;
|
|
;; Params:
|
|
;; m: Dimensionality of sylvester-radix numbers used as vertices.
|
|
;;
|
|
;; Example:
|
|
;; > (sylvester-edges 1)
|
|
;; '(((0) (1)) ((1) (0)))
|
|
sylvester-edges
|
|
|
|
;; Create cyclic permutation operator for one digit of sylvester-radix number.
|
|
;;
|
|
;; Params:
|
|
;; i: Index of digit to permute.
|
|
;; n: Number of times to cycle digit.
|
|
;;
|
|
;; Example:
|
|
;; > ((cycle-sylvester-radix 2 1) '(0 0 0 0))
|
|
;; '(0 0 1 0)
|
|
cycle-sylvester-radix
|
|
|
|
;; Create skip operator.
|
|
;; The skip operator is a composition of single-digit cyclic permutations.
|
|
;; Skip operators are used to generate the graph edges.
|
|
;;
|
|
;; Params:
|
|
;; i: Results in an operator acting on digits 0 to i.
|
|
;;
|
|
;; Example:
|
|
;; > ((skip-sylvester-radix 2) '(0 0 0))
|
|
;; '(1 2 6)
|
|
skip-sylvester-radix)
|
|
|
|
(require "sylvester.rkt")
|
|
|
|
(define (sylvester-nodes m)
|
|
(map (compose (extend-sylvester-radix m)
|
|
make-sylvester-radix)
|
|
(range (- (sylvester m) 1))))
|
|
|
|
(define (sylvester-edges m)
|
|
(foldr
|
|
append
|
|
'()
|
|
(map (lambda (k) (map (sylvester-color-edge k) (sylvester-nodes m)))
|
|
(range m))))
|
|
|
|
(define (sylvester-color-edge k)
|
|
(lambda (v) (list v ((skip-sylvester-radix k) v))))
|
|
|
|
(define (cycle-sylvester-radix i n)
|
|
(lambda (v)
|
|
(let* ([v ((extend-sylvester-radix (+ i 1)) v)]
|
|
[head (take v i)]
|
|
[tail (if (< i (- (length v) 1))
|
|
(drop v (+ i 1))
|
|
'())]
|
|
[element (list-ref v i)])
|
|
(append
|
|
head
|
|
(cons (modulo (+ element n) (sylvester i))
|
|
tail)))))
|
|
|
|
(define (skip-sylvester-radix i)
|
|
(lambda (v)
|
|
(if (= i 0)
|
|
((cycle-sylvester-radix 0 1) v)
|
|
(let* ([prev (skip-sylvester-radix (- i 1))]
|
|
[partial (take v (min i (length v)))]
|
|
[value (sylvester-radix-value (prev partial))])
|
|
((compose (cycle-sylvester-radix i (+ 1 value)) prev) v)))))
|
|
|