-1
$\begingroup$

Today I wrote some C# code to generate all subsets of a set. It all worked correctly but then I realized about I'd made a rookie mistake. The puzzle here is not that the code is not working but rather that code works perfectly while it most definitely shouldn't be:

IEnumerable<IList<T>> GetAllSubSets<T>(IList<T> items, int i)
{
    IEnumerable<IList<T>> subsets;
    if (i < 0)
        subsets = new [] { new List<T>() };
    else
        subsets = GetAllSubSets(items, i - 1);
    foreach (var s in subsets)
        yield return s;

    if (i >= 0)
        foreach (var s in subsets)
        {
            s.Add(items[i]);
            yield return s;
        }
}

You might have realized the issue here already but if you haven't... There should be only a single call for each value i. So the call for i = -1 should only execute once. That means we create an array only once. So all the returned subsets should be pointing to same reference value of that one array and therefore all subsets would have same elements!

Why is this code working perfectly fine then?

$\endgroup$

closed as off-topic by Rohcana, CodeNewbie, Hackiisan, A E, Ben Aaronson Sep 3 '15 at 8:12

  • This question does not appear to be about creation and solving of puzzles, within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ I'm voting to close this question as off-topic because I feel this would be a better fit on Stack Overflow or Code Review $\endgroup$ – CodeNewbie Sep 3 '15 at 5:03
  • $\begingroup$ Off-topic question. $\endgroup$ – Waqas Shabbir Sep 3 '15 at 5:40
  • $\begingroup$ I posted it here because it was puzzling and I already knew the answer. I'm not asking this question to solve some problem. $\endgroup$ – Shital Shah Sep 3 '15 at 8:40
  • $\begingroup$ I was wondering if you knew the answer when you asked the question. Regardless, it would still be a good SO question -- there's no requirement that you don't know the answer to post a question. $\endgroup$ – Joel Rondeau Sep 3 '15 at 14:26
  • $\begingroup$ I often post questions on SO. I posted here because this is a good puzzle for C# as language. I don't think anyone would be searching for solution for this particular problem on SO. $\endgroup$ – Shital Shah Sep 4 '15 at 4:42
2
$\begingroup$

The inner call to GetAllSubSets() is only evaluated when the yield occurs. This lazy evaluation means that the call to create a new subset occurs multiple times.

To prove this, force the evaluation to happen immediately, and you will see that the new call happens only once. It can be done by changing the inner call as follows:

subsets = GetAllSubSets(items, i - 1).ToList();

Now the call evaluates immediately and the new call is only called once.

The most important part of this is to realize that you didn't properly understand the code that you wrote, so the best thing to do is to rewrite it until you do. I didn't understand it until I debugged it and saw the multiple new calls. Then I realized what was going on.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.