Difference between revisions of "Brute forcing"

(Replace)
(One intermediate revision by one other user not shown)
Line 1: Line 1:
Brute forcing is generally accepted as the term for solving a problem in a roundabout, time-consuming, and inconvenient method.
+
Brute forcing is generally accepted as the term for solving a problem in a roundabout, time-consuming, uncreative, and inconvenient method.
  
  
 
Given the problem "How many outfits can you create with thirteen hats and seven pairs of 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 pairs of 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 <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.
+
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_n\}</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 [[Rearrangement Inequality]] for consequences of the example (and a more formal proof).
 
See the [[Rearrangement Inequality]] for consequences of the example (and a more formal proof).

Revision as of 15:53, 24 January 2009

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


Given the problem "How many outfits can you create with thirteen hats and seven pairs of 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 $\{{a}_1,{a}_2,\ldots,{a}_n\}$ and $\{b_1,b_2,\ldots,b_n\}$ 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 Rearrangement Inequality for consequences of the example (and a more formal proof).

See also