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

 

[alphy]

I would approach this problem by first understanding the concept of recursion and how it can be applied to solve problems. Recursion is a programming technique where a function calls itself until a certain condition is met. In this case, the subsets function is calling itself with a smaller list until the desired number of elements is reached.

To understand how this specific function works, I would first look at the base cases. In this case, the base cases are when k = 0 or when the list is empty. In both of these cases, the function returns an empty list, which makes sense as there are no subsets to be created.

Next, I would look at the recursive case, where the function calls itself with a smaller list and a smaller value of k. In this case, the function is using the first element of the list and combining it with all the subsets of the rest of the list with k-1 elements. This is done using the Map function, which applies a function to each element of a list.

The Join function is used to combine the subsets created in the previous step with the subsets of the rest of the list with k elements. This ensures that all possible combinations are included in the final result.

To create this function from scratch, I would start by understanding the base cases and then gradually build on the recursive case. It may also be helpful to break down the function into smaller, simpler steps and test them individually to understand how they work.

In addition, using the Trace function can help with understanding the flow of the function and how it operates on different inputs. It may also be helpful to experiment with different inputs and observe the resulting outputs to gain a deeper understanding.

Overall, solving recursion problems requires a combination of understanding the concept, breaking down the problem into smaller steps, and experimenting with different inputs to gain a deeper understanding.