Brute forcing

Revision as of 15:24, 18 June 2006 by Agolsme (talk | contribs)

Brute forcing is generally accepted as the term for solving a problem in a roundabout, time-consuming, and inconvenient method.


Given the problem "How many outfits can you create with thirteen hats and seven shoes?", a method involving brute force would be to list all 91 possibilities.

Another method of bruteforce is the Greedy Algorithm. As an example, given two sets $\{a_1,a_2,\ldots,a_n\}$ and $\{b_1,b_2,\ldots,b_3\}$ how can we maximize the sum of $\sum{i,j \in n} a_ib_j$ ? We sort the sets such that they are in increasing or decreasing order; then, the maximal sum is $a_1b_1 + a_2b_2 + a_3b_3 + \ldots a_nb_n$. The "greedy" part is when we maximize the sum each step by taking the largest possible term to add.

See the Rearrangment Inequality for consequences of the example(and a more formal proof).