#define private public - A subset of Python (30 Jun 2013)

topic end
<!--
   * Set TOPICTITLE = #define private public - A subset of Python (30 Jun 2013)
-->

<style type="text/css">
pre {background-color:#ffeecc;}
</style>

%STARTINCLUDE%
<a name="30"></a>

---+++ [[DefinePrivatePublic20130630ASubsetOfPython][A subset of Python]] (30 Jun 2013)

<summary>
Over the years, I collected implementations of an algorithm to solve the
<a href="http://www.clausbrod.de/Blog/BlogOnSoftware20060301">subset sum problem</a>
in various languages. A few days ago, I experimented a little with Python, and
here is the deplorably non-idiomatic and na&iuml;ve result - apologies offered.

</summary>


<pre>
<style type="text/css">
<!--
.String { color: #4a708b; }
.Statement { color: #b03060; font-weight: bold; }
.PreProc { color: #1874cd; }
.Constant { color: #ff8c00; }
.Special { color: #8a2be2; }
.Identifier { color: #458b74; }
-->
</style>
<span class="PreProc">import</span> random
<span class="PreProc">import</span> array
<span class="PreProc">import</span> sys

numbers = array.array(<span class="String">'i'</span>)
flags = array.array(<span class="String">'c'</span>)
solutions = <span class="Constant">0</span>

<span class="Statement">def</span> <span class="Identifier">find_solutions</span>(k, target_sum):
    <span class="Statement">global</span> solutions

    <span class="Statement">if</span> target_sum == <span class="Constant">0</span>:
        <span class="Identifier">print</span> <span class="String">&quot;  Solution:&quot;</span>,
        <span class="Statement">for</span> i <span class="Statement">in</span> <span class="Identifier">range</span>(<span class="Constant">0</span>, <span class="Identifier">len</span>(numbers)):
            <span class="Statement">if</span> flags[i] != <span class="Constant">0</span>:
                <span class="Identifier">print</span> numbers[i],
        <span class="Identifier">print</span>
        solutions = solutions + <span class="Constant">1</span>
    <span class="Statement">else</span>:
        <span class="Statement">if</span> k &lt; <span class="Identifier">len</span>(numbers):
            <span class="Statement">if</span> (numbers[k] * (<span class="Identifier">len</span>(numbers)-k+<span class="Constant">1</span>)) &gt;= target_sum:
                <span class="Statement">if</span> target_sum &gt;= numbers[k]:
                    flags[k] = <span class="Constant">1</span>
                    find_solutions(k+<span class="Constant">1</span>, target_sum - numbers[k])
                    flags[k] = <span class="Constant">0</span>
                find_solutions(k+<span class="Constant">1</span>, target_sum)

<span class="Statement">def</span> <span class="Identifier">find_subset_sum</span>(target_sum):
    <span class="Statement">global</span> solutions
    <span class="Statement">global</span> flags
    <span class="Identifier">print</span> <span class="String">&quot;Subsets which sum up to %s:&quot;</span> % target_sum
    flags = [<span class="Constant">0</span>] * <span class="Identifier">len</span>(numbers)
    find_solutions(<span class="Constant">0</span>, target_sum)
    <span class="Identifier">print</span> <span class="String">&quot;Found&quot;</span>, solutions, <span class="String">&quot;different solutions&quot;</span>

<span class="Statement">def</span> <span class="Identifier">subset_sum_test</span>(size):
    <span class="Statement">global</span> numbers
    total = <span class="Constant">0</span>

    <span class="Identifier">print</span> <span class="String">&quot;Random values:</span><span class="Special">\n</span><span class="String">  &quot;</span>,
    <span class="Statement">for</span> i <span class="Statement">in</span> <span class="Identifier">range</span>(<span class="Constant">0</span>, size):
        numbers.append(random.randint(<span class="Constant">0</span>, <span class="Constant">1000</span>))
        total = total + numbers[i]
        <span class="Identifier">print</span> numbers[i],
    <span class="Identifier">print</span>

    numbers = <span class="Identifier">sorted</span>(numbers, reverse = <span class="Identifier">True</span>)
    target_sum = total/<span class="Constant">2</span>
    find_subset_sum(target_sum)

subset_sum_test(<span class="Constant">15</span> <span class="Statement">if</span> <span class="Identifier">len</span>(sys.argv) &lt; <span class="Constant">2</span> <span class="Statement">else</span> <span class="Identifier">int</span>(sys.argv[<span class="Constant">1</span>]))

</pre>


---

%STOPINCLUDE%

%COMMENT{type="below" nonotify="on"}%

---
to top
End of topic
Skip to action links | Back to top
You are here: Blog > DefinePrivatePublic20130630ASubsetOfPython

r1.1 - 30 Jun 2013 - 13:01 - ClausBrod to top
Blog