Brute forcing

Revision as of 12:22, 5 May 2023 by Icecreamrolls8 (talk | contribs) (Rephrasing what brute force is)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Brute forcing is the method of completing a problem in the most straightforward way possible, through bashing calculations, and can actually sometimes be faster than a more creative approach, and is thus an important tool to have.

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 (although this would not be a smart time to use brute force).

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