# SICP Solutions

### Chapter 4, Metalinguistic Abstraction

#### Exercise 4.41

Well, with the interesting results of previous exercises, I thought to mirror the previous solution without using amb. It took unneccessarily more time with only a slight improvement in performance.

Later I wrote the permutation version too to check if there was indeed any performance gain.

The mirrored solution looks verbose but it is faster than the permuation based solution. Note that both solutions are faster than all the previous solutions.

First let’s see the numbers:

Version Iterations Time
Mirrored 10,000 6 secs
Permutation based 10,000 14 secs

Why mirrored version is faster? Because it is not trying every permutation.

Why this mirrored version is faster than the optimised amb version even when code is similar? Because (i)no backtracking as we discard the result as soon as it gets generated and move to next element unlike amb where we backtrack. (ii) Some minor optimizations like before combining possibilities there are some items which can be removed.(which was not possible in previous exercise).

Now, first the code for mirrored solution(Its too big compared to concise permutation based which is presented later):

Note: I used MIT scheme version of remove which requires to pass lambda instead of the element.

Here goes the ‘permutation’ based solution: