permutations with repetition in scheme

With my exams finished and my final project at uni also finished, I had some time to spend with my already-started-but-not-finished small coding challenges.

As you may know, some time ago I started not one but two implementations of mastermind.

One in Perl, and the other in Scheme.

I wanted to finish the scheme implementation, so I started to look at Donald Knuth's paper about Mastermind. It's not so complicated, but as I've been far from complex algorithms for some time, it scared me a bit.

First thing to do is having available all possible combinations (strictly speaking they are permutations as order matters) of colours (in our case numbers). Two nested maps, a recursive call, and you're done.

As I don't have time to comment all the code, I'll just post here the permutations part, and keep the complete code private for now. When I have the time, I'll post it all, with appropiate comments. It's a minimax algorithm, so not daunting at all, but....

Here it is:

	;;; permutations with repetitions. Base to get all possible
	;;; mastermind solutions.
	;;;
	;;; Example usage:
	;;; (perm '(1 2 3) 2) => ((1 1) (2 1) (3 1) (1 2) (2 2) (3 2) (1 3) (2 3) (3 3))
	(define (perm lst len)
	(cond ((= 0 len) '(()))
	(else (append-map (lambda (x)
	(map (lambda (y) (cons y x )) lst))
	(perm lst (- len 1))))))

view raw perm1tations.ss hosted with ❤ by GitHub

Apart from this, I've hacked with a few things (as time permitted). If you're specially interested in something, ask.

• net sniffing
• Image analyzing and video tracking
• html parsing and web scraping