Difference between revisions of "Brute forcing"
(oops latesx error er actually, can someone help me fix the red one?) |
(latex error and see also) |
||
| Line 4: | Line 4: | ||
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. | 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 | + | Another method of brute force is the Greedy Algorithm. As an example, given two sets <math>\{{a}_1,{a}_2,\ldots,{a}_n\}</math> and <math>\{b_1,b_2,\ldots,b_3\}</math> how can we maximize the sum of <math>\sum_{i,j \in n} a_ib_j</math>? We sort the sets such that they are in increasing or decreasing order; then, the maximal sum is <math>a_1b_1 + a_2b_2 + a_3b_3 + \ldots a_nb_n</math>. The "greedy" part is when we maximize the sum each step by taking the largest possible term to add. |
| − | See the [[ | + | See the [[Rearrangement Inequality]] for consequences of the example (and a more formal proof). |
| + | |||
| + | == See also == | ||
| + | |||
| + | * [[Dumbassing]] | ||
Revision as of 15:44, 18 June 2006
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 brute force is the Greedy Algorithm. As an example, given two sets 
and 
how can we maximize the sum of 
? We sort the sets such that they are in increasing or decreasing order; then, the maximal sum is 
. The "greedy" part is when we maximize the sum each step by taking the largest possible term to add.
See the Rearrangement Inequality for consequences of the example (and a more formal proof).
