Popular recipes tagged "optimal_solution"http://code.activestate.com/recipes/tags/optimal_solution/popular/2011-02-07T06:37:52-08:00ActiveState Code RecipesBinary search function. (Python)
2011-02-07T06:37:52-08:00Kevin L. Sitzehttp://code.activestate.com/recipes/users/4173535/http://code.activestate.com/recipes/577565-binary-search-function/
<p style="color: grey">
Python
recipe 577565
by <a href="/recipes/users/4173535/">Kevin L. Sitze</a>
(<a href="/recipes/tags/binary/">binary</a>, <a href="/recipes/tags/binary_search/">binary_search</a>, <a href="/recipes/tags/bsearch/">bsearch</a>, <a href="/recipes/tags/functional/">functional</a>, <a href="/recipes/tags/lower_bound/">lower_bound</a>, <a href="/recipes/tags/optimal_solution/">optimal_solution</a>, <a href="/recipes/tags/search/">search</a>, <a href="/recipes/tags/upper_bound/">upper_bound</a>).
Revision 3.
</p>
<p>For a number of years Python has provided developers with the special parameters 'cmp' and 'key' on list.sort and __builtin__.sorted. However Python does not provide a built-in mechanism for doing binary searches on such sorted lists. This recipe provides a simple function that allows you to perform binary searches on your sorted sequences.</p>
Fast flatten() with depth control and oversight over which subtrees to expand (Python)
2010-11-26T11:10:01-08:00Kevin L. Sitzehttp://code.activestate.com/recipes/users/4173535/http://code.activestate.com/recipes/577470-fast-flatten-with-depth-control-and-oversight-over/
<p style="color: grey">
Python
recipe 577470
by <a href="/recipes/users/4173535/">Kevin L. Sitze</a>
(<a href="/recipes/tags/flatten/">flatten</a>, <a href="/recipes/tags/iterator/">iterator</a>, <a href="/recipes/tags/iterators/">iterators</a>, <a href="/recipes/tags/list/">list</a>, <a href="/recipes/tags/optimal_solution/">optimal_solution</a>, <a href="/recipes/tags/python/">python</a>, <a href="/recipes/tags/sequence/">sequence</a>, <a href="/recipes/tags/tuple/">tuple</a>).
</p>
<p>Extremely fast, non-recursive, depth limited flatten with powerful control over which subtrees are to be expanded. If this is what you need then look no further.</p>
Partition Problem and natural selection (Python)
2009-10-27T00:27:14-07:00Jai Vikram Singh Vermahttp://code.activestate.com/recipes/users/4171450/http://code.activestate.com/recipes/576937-partition-problem-and-natural-selection/
<p style="color: grey">
Python
recipe 576937
by <a href="/recipes/users/4171450/">Jai Vikram Singh Verma</a>
(<a href="/recipes/tags/approximate_solution/">approximate_solution</a>, <a href="/recipes/tags/complete/">complete</a>, <a href="/recipes/tags/crossover/">crossover</a>, <a href="/recipes/tags/easiest_hard_problem/">easiest_hard_problem</a>, <a href="/recipes/tags/generations/">generations</a>, <a href="/recipes/tags/genetic_algorithms/">genetic_algorithms</a>, <a href="/recipes/tags/natural_selection/">natural_selection</a>, <a href="/recipes/tags/np/">np</a>, <a href="/recipes/tags/np_complete/">np_complete</a>, <a href="/recipes/tags/np_hard/">np_hard</a>, <a href="/recipes/tags/optimal_solution/">optimal_solution</a>, <a href="/recipes/tags/partition_problem/">partition_problem</a>).
Revision 4.
</p>
<p>Partition problem
From Wikipedia, the free encyclopedia</p>
<p>In computer science, the partition problem is an NP-complete problem. The problem is to decide whether a given multiset of integers can be partitioned into two "halves" that have the same sum. More precisely, given a multiset S of integers, is there a way to partition S into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2? The subsets S1 and S2 must form a partition in the sense that they are disjoint and they cover S. The optimization version asks for the "best" partition, and can be stated as: Find a partition into two subsets S1,S2 such that max(sum(S_1), sum(S_2)) is minimized (sometimes with the additional constraint that the sizes of the two sets in the partition must be equal, or differ by at most 1).</p>
<p>The partition problem is equivalent to the following special case of the subset sum problem: given a set S of integers, is there a subset S1 of S that sums to exactly t /2 where t is the sum of all elements of S? (The equivalence can be seen by defining S2 to be the difference S − S1.) Therefore, the pseudo-polynomial time dynamic programming solution to subset sum applies to the partition problem as well.</p>
<p>Although the partition problem is NP-complete, there are heuristics that solve the problem in many instances, either optimally or approximately. For this reason, it has been called the "The Easiest Hard Problem" by Brian Hayes.</p>