<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Woo Chia Wei on Medium]]></title>
        <description><![CDATA[Stories by Woo Chia Wei on Medium]]></description>
        <link>https://medium.com/@woochiawei?source=rss-1b6c2f8cc629------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*nYTpnwrDH8OtIkwqa0ucmw.jpeg</url>
            <title>Stories by Woo Chia Wei on Medium</title>
            <link>https://medium.com/@woochiawei?source=rss-1b6c2f8cc629------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Mon, 16 Nov 2026 18:52:53 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@woochiawei/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Combinatorics Programming]]></title>
            <link>https://medium.com/zero-equals-false/combinatorics-programming-deb15e2fee13?source=rss-1b6c2f8cc629------2</link>
            <guid isPermaLink="false">https://medium.com/p/deb15e2fee13</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[brute-force]]></category>
            <category><![CDATA[depth-first-search]]></category>
            <category><![CDATA[recursion]]></category>
            <category><![CDATA[combinatorics]]></category>
            <dc:creator><![CDATA[Woo Chia Wei]]></dc:creator>
            <pubDate>Sat, 04 Jan 2020 07:28:43 GMT</pubDate>
            <atom:updated>2020-01-05T08:49:32.883Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Write a function that prints all non-empty subsets of {1,2,3,..,10}.</em></p><p>I was asked to solve this problem during midterm exam of my first university year and during my job interview. The official answer provided by my lecturer was to write 10 loops where each <em>n</em>-th loop determine action of either take or not take <em>n</em>-th number. Here is implementation in Python:</p><pre>for x1 in range(0, 2):<br>    for x2 in range(0, 2):<br>        for x3 in range(0, 2):<br>            for x4 in range(0, 2):<br>                for x5 in range(0, 2):<br>                    for x6 in range(0, 2):<br>                        for x7 in range(0, 2):<br>                            for x8 in range(0, 2):<br>                                for x9 in range(0, 2):<br>                                    for x10 in range(0, 2):<br>                                        result = []<br>                                        if x1: result.append(1)<br>                                        if x2: result.append(2)<br>                                        if x3: result.append(3)<br>                                        if x4: result.append(4)<br>                                        if x5: result.append(5)<br>                                        if x6: result.append(6)<br>                                        if x7: result.append(7)<br>                                        if x8: result.append(8)<br>                                        if x9: result.append(9)<br>                                        if x10: result.append(10)<br>                                        if result:<br>                                            print(result)</pre><p>This solution is so inefficient that the number of loops are hard-coded and cannot be changed when the size of set is different.</p><p>Let’s think in another way, since take and not to take are binary-like, we can iterate the binary numbers from 1 to 2^n-1, then convert the binary expression to decision making step to determine which element to pick.</p><p>For instance, binary expression of 6 is 110, simply pad zeros to the expression to have length of 10 digits 0000000110, reading from left to right it tells us the selected elements as subset are {8, 9}. Here is the implementation in Python:</p><pre>n = 5<br>for i in range(1, 2 ** n):<br>    decision_expression = (&#39;{&#39; + &#39;0:0{}b&#39;.format(n) + &#39;}&#39;).format(i)<br>    subset = [index for index, decision in enumerate(decision_expression, start=1) if decision == &#39;1&#39;]<br>    print(subset)<br>    <br>###########<br># Output<br>###########<br>#[5]<br>#[4]<br>#[4, 5]<br>#[3]<br>#[3, 5]<br>#[3, 4]<br>#[3, 4, 5]<br>#[2]<br>#[2, 5]<br>#[2, 4]<br>#[2, 4, 5]<br>#[2, 3]<br>#[2, 3, 5]<br>#[2, 3, 4]<br>#[2, 3, 4, 5]<br>#[1]<br>#[1, 5]<br>#[1, 4]<br>#[1, 4, 5]<br>#[1, 3]<br>#[1, 3, 5]<br>#[1, 3, 4]<br>#[1, 3, 4, 5]<br>#[1, 2]<br>#[1, 2, 5]<br>#[1, 2, 4]<br>#[1, 2, 4, 5]<br>#[1, 2, 3]<br>#[1, 2, 3, 5]<br>#[1, 2, 3, 4]<br>#[1, 2, 3, 4, 5]</pre><p>This seems to be a better and short solution with just single loop, uses binary conversion and simple parsing from binary expression to subset. But this kind of brute force method is kind of painful and inflexible when the constraints are added into our original question. Some extended questions:</p><p><strong><em>Q2:</em></strong><em> Write a function that prints all non-empty subsets of {1,2,3,..,10} where each subset is allowed to have up to maximum 4 elements.</em></p><p><strong><em>Q3:</em></strong><em> Write a function that prints all non-empty subsets of {1,2,3,..,10} where each subset must have exactly 4 elements.</em></p><p>Looking at Q2 and Q3, we need to do checking on each generated subset, the disadvantage of brute force approach is even we have constraint checking in the loop itself, it still take the same number of iterations.</p><p>Since decision making is involved when move from element to element, let’s draw a decision making tree where each node stores <strong>selected </strong>&amp; <strong>remaining</strong>. To simplify the diagram, the notation being used will be 2 list expressions, for instance, [1], [2,3] means selected is [1] and remaining = [2,3].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/668/1*xSBGSki8I5Ccd6JH_teD5w.png" /></figure><p>Above tree shows how we traverse the tree and reach all the solutions at leaves. Now we are going to model this question to be DFS (Depth First Search). Below Python codes show how to perform recursive DFS to print all the subsets that satisfied stated conditions:</p><p><strong><em>Q1:</em></strong><em> Write a function that prints all non-empty subsets of {1,2,3,..,10}.</em></p><pre>def solveQ1(items):<br>    def scan(node):<br>        # Termination Condition - no more remaining<br>        # Print selected items and exit<br>        if len(node[&#39;remaining&#39;]) == 0:<br>            if node[&#39;selected&#39;]:<br>                print(node[&#39;selected&#39;])<br>            return<br>        <br>        # Deep copies<br>        new_selected = list(node[&#39;selected&#39;])<br>        new_remaining = list(node[&#39;remaining&#39;])<br>        next_item = new_remaining.pop(0)<br>        <br>        # Take next item<br>        scan({<br>            &#39;selected&#39;: new_selected + [next_item],<br>            &#39;remaining&#39;: new_remaining<br>        })<br>    <br>        # Not to take next item<br>        scan({<br>            &#39;selected&#39;: new_selected,<br>            &#39;remaining&#39;: new_remaining<br>        })<br>        <br>    root = {<br>        &#39;selected&#39;: [],<br>        &#39;remaining&#39;: items<br>    }<br>    scan(root)<br>            <br>solveQ1([1,2,3,4])</pre><p><strong><em>Q2:</em></strong><em> Write a function that prints all non-empty subsets of {1,2,3,..,10} where each subset is allowed to have up to maximum 4 elements.</em></p><pre>def solveQ2(items, max_allowed):<br>    def scan(node):<br>        # Termination Condition - no more remaining<br>        # Print selected items and exit<br>        if node[&#39;remaining&#39;] == [] or len(node[&#39;selected&#39;]) == node[&#39;max&#39;]:<br>            if node[&#39;selected&#39;]:<br>                print(node[&#39;selected&#39;])<br>            return<br>        <br>        # Deep copies<br>        new_selected = list(node[&#39;selected&#39;])<br>        new_remaining = list(node[&#39;remaining&#39;])<br>        next_item = new_remaining.pop(0)<br>        <br>        # Take next item<br>        scan({<br>            &#39;max&#39;: node[&#39;max&#39;],<br>            &#39;selected&#39;: new_selected + [next_item],<br>            &#39;remaining&#39;: new_remaining<br>        })<br>    <br>        # Not to take next item<br>        scan({<br>            &#39;max&#39;: node[&#39;max&#39;],<br>            &#39;selected&#39;: new_selected,<br>            &#39;remaining&#39;: new_remaining<br>        })<br>        <br>    root = {<br>        &#39;max&#39;: max_allowed,<br>        &#39;selected&#39;: [],<br>        &#39;remaining&#39;: items<br>    }<br>    scan(root)<br>            <br>solveQ2([1,2,3,4,5,6,7], 4)</pre><p><strong><em>Q3:</em></strong><em> Write a function that prints all non-empty subsets of {1,2,3,..,10} where each subset must have exactly 4 elements.</em></p><pre>def solveQ3(items, count):<br>    def scan(node):<br>        # Exit if not enough numbers to form solution<br>        if len(node[&#39;selected&#39;]) + len(node[&#39;remaining&#39;]) &lt; node[&#39;count&#39;]:<br>            return<br>        <br>        # Termination Condition - no more remaining<br>        # Print selected items and exit<br>        if len(node[&#39;selected&#39;]) == node[&#39;count&#39;]:<br>            if node[&#39;selected&#39;]:<br>                print(node[&#39;selected&#39;])<br>            return<br>        <br>        # Deep copies<br>        new_selected = list(node[&#39;selected&#39;])<br>        new_remaining = list(node[&#39;remaining&#39;])<br>        next_item = new_remaining.pop(0)<br>        <br>        # Take next item<br>        scan({<br>            &#39;count&#39;: node[&#39;count&#39;],<br>            &#39;selected&#39;: new_selected + [next_item],<br>            &#39;remaining&#39;: new_remaining<br>        })<br>    <br>        # Not to take next item<br>        scan({<br>            &#39;count&#39;: node[&#39;count&#39;],<br>            &#39;selected&#39;: new_selected,<br>            &#39;remaining&#39;: new_remaining<br>        })<br>        <br>    root = {<br>        &#39;count&#39;: count,<br>        &#39;selected&#39;: [],<br>        &#39;remaining&#39;: items<br>    }<br>    scan(root)<br>            <br>solveQ3([1,2,3,4,5,6,7], 4)</pre><p>Above 3 questions shared the same data structure and algorithm. Tree search is a power technique to generate solutions with good performance, the bad tree branch can be pruned earlier without going deeper, thus the search space can be reduced significantly to speed up the entire scanning process. The challenging part is to choose a right metadata structure to pass the right information to next layer for constraint checking.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=deb15e2fee13" width="1" height="1" alt=""><hr><p><a href="https://medium.com/zero-equals-false/combinatorics-programming-deb15e2fee13">Combinatorics Programming</a> was originally published in <a href="https://medium.com/zero-equals-false">Zero Equals False</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>