Solving Recursion Problems with MMA - R.Gaylord

[Nile3]

Hello, I'm going through Introduction to programming with MMA by R.Gaylord and there is an exemple in chapter 7 about recursively creating k-elements subsets of a given set.

subsets[Range[5], 2] should give {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2,5}, {3,4}, {3, 5}, {4, 5}}

The problem is, I can't figure out how he created this function. He explains only the tip of the iceberg. I tried the common ways of analyzing using trace but the resulting output is way too big. Any tips on why this function works and how you would go about creating it from just knowing what you have to do would be appreciated.

subsets[lis_, 0] := {{}}
subsets[{}, k_] := {}
subsets[lis_, k_] := Module[{res = subsets[Rest[lis], k - 1]},
  Join[
   Map[(Join[{First[lis]}, #] &), res],
   subsets[Rest[lis], k]
   ]
  ]

In[9]:= subsets[Range[5], 2]

Out[9]= {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 
  4}, {3, 5}, {4, 5}}

 

[Bill Simpson]

I don't know what trace method you used, but this is more compact.
Trace[subsets[Range[5], 2], subsets[_, _]]
That only shows each call to subsets and might be more explanatory.

His function is a little tricky because it is using a sort of double recursion. On one hand it is nibbling away at the list of items still available to construct a subset and on the other it is nibbling away at the number of elements still needed to construct the subset.

As always with recursion, first comes the base case to stop the recursion. Since he has double recursion going on he has two base cases.

First
subsets[lis_, 0] := {{}}
means if I have nibbled down to where no more elements are needed to make a subset then I return the empty list to terminate the process of appending more and more elements to make up the n subset.
And
subsets[{}, k_] := {}
means if I am trying to nibble off more elements to make a subset but I have exhausted my supply then again I have to stop the process, but in a different way that we need to understand in a moment.

Now the recursion itself
subsets[lis_, k_] := Module[{res = subsets[Rest[lis], k - 1]},
Join[
Map[(Join[{First[lis]}, #] &), res],
subsets[Rest[lis], k]
]
]
The res=subsets[] will produce all the n-1 element subsets from the tail of the available list.

The Map[(Join[{First[lis]}, #] &), res] will combine the first element of the list with every possible n-1 subset from the tail.

And finally there are the n element subsets from the tail of the list.

Now if you use the Trace method I showed above you may be able to see how each of those recursion steps are either nibbling away at the rest of list or are nibbling away with n-1.

You can use a slight change to use Trace to look at the results from subsets calls
subsets[lis_, k_] := Module[{res = subsets[Rest[lis], k - 1], v},
Join[Map[(Join[{First[lis]}, #] &), res], v = subsets[Rest[lis], k]]];
Trace[subsets[Range[5], 2], _ = _]

That introduces a variable v to be used for assignments and tells Trace to only show assignments. So res= and v= will be shown in the trace. You can compare and contrast that with the previous version using Trace to gain some insight.

Sometimes I will position the cursor and insert a newline into the middle of a Trace output. That creates a copy of it and puts it into a new cell. Then I will insert more newlines, trying to organize the results vertically so I can better walk through the results and try to gain an understanding.

Study this for a while and try to decide if this is enough or if you need more?

 

[Nile3]

Great answer, thank you very much. I still don't know how to invent this type of functions on my own but I'll keep studying.

Do you know of a good website to get many examples of recursive functions?

 

[Bill Simpson]

See if you can borrow from a library or buy inexpensive old copies of books on LISP and Scheme programming languages. I'd advise at least trying to get a peek at any book before buying it over the net, unless the price means it really doesn't matter. Both LISP and Scheme texts will spend a lot of time introducing you to to recursion.

Winston's LISP text might be good, but it looks like it drank the "object oriented" Koolaid in later editions.
http://www.bestwebbuys.com/books/search.jsp?isrc=b-home-search&N=0&Ntt=winston+lisp&Ntk=All

Abelson's Structure and Interpretation might be good.
http://www.bestwebbuys.com/Structur...ter-Programs-ISBN-9780070004221?isrc=b-search