{"id":1253,"date":"2014-04-14T07:00:01","date_gmt":"2014-04-14T07:00:01","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2014\/04\/14\/the-geeky-thrill-of-discovering-that-two-things-are-really-the-same-thing-just-with-different-labels\/"},"modified":"2014-04-14T07:00:01","modified_gmt":"2014-04-14T07:00:01","slug":"the-geeky-thrill-of-discovering-that-two-things-are-really-the-same-thing-just-with-different-labels","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20140414-01\/?p=1253\/","title":{"rendered":"The geeky thrill of discovering that two things are really the same thing, just with different labels"},"content":{"rendered":"

\nToday’s post about binomial coefficients\nwas intended to be a warm-up for Catalan numbers,\nbut it turns out Eric Lippert already covered them,\n\nfirst in the context of binary trees<\/a>,\n\nthen in the context of arbitrary trees and forests<\/a>,\nand then again\n\nin the context of matched parentheses<\/a>.\nAnother way of seeing the correspondence\nbetween forests and matched parentheses is simply to consider\neach {<\/code> as an XML open-tag and each }<\/code> as\nan XML end-tag.\n<\/p>\n

\nOne thing to take away from the enumeration of objects controlled\nby Catalan numbers is that when you see multiplication in a recurrence\nrelation, that typically corresponds to a nested loop.\n(We saw this ourselves when we studied Stirling numbers of the second kind.)\n<\/p>\n

\nThe correspondence between binary trees and arbitrary forests\nis done by simply renaming variables:\nleft­Child<\/code> and right­Child<\/code>\nturn into\nfirst­Child<\/code> and next­Sibling<\/code>.\n<\/p>\n

\nRenaming variables also\nreveals an interesting equivalence\nbetween the two algorithms for\nreversing a linked list.\nOne technique is to do link rewriting:\n<\/p>\n

\nNode *Reverse(Node *head)\n{\n Node *prev = nullptr;\n while (head) {\n  \/\/ The node we are rewriting\n  Node *current = head;\n  \/\/ Advance to next node before\n  \/\/ we overwrite the outbound pointer\n  head = current->next;\n  \/\/ Repoint to previous node\n  current->next = prev;\n  \/\/ Advance the trailing pointer\n  prev = current;\n }\n return prev;\n}\n<\/pre>\n
\nAnother technique is to pop nodes off one list while pushing\nthem onto another.\n<\/p>\n
\nNode *Reverse(Node *head)\n{\n Node *result = nullptr;\n while (head) {\n  \/\/ Pop\n  Node *current = head;\n  head = current->next;\n  \/\/ Push\n  current->next = result;\n  result = current;\n }\n return result;\n}\n<\/pre>\n
\nBut if you look more closely at the two versions,\nyou’ll see that they are not really two algorithms.\nThey are the same<\/i> algorithm, just with different\ncomments and variable names!\n<\/p>\n
\nOne of my colleagues used this as an interview question and guided\ncandidates through both algorithms, only to discover\nlater that they were actually the same algorithm,\nmerely viewed through different-colored glasses.<\/p>\n","protected":false},"excerpt":{"rendered":"
Today’s post about binomial coefficients was intended to be a warm-up for Catalan numbers, but it turns out Eric Lippert already covered them, first in the context of binary trees, then in the context of arbitrary trees and forests, and then again in the context of matched parentheses. Another way of seeing the correspondence between […]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[26],"class_list":["post-1253","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-other"],"acf":[],"blog_post_summary":"
Today’s post about binomial coefficients was intended to be a warm-up for Catalan numbers, but it turns out Eric Lippert already covered them, first in the context of binary trees, then in the context of arbitrary trees and forests, and then again in the context of matched parentheses. Another way of seeing the correspondence between […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/1253","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=1253"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/1253\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=1253"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=1253"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=1253"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}