Does this equation have a name?

  1. I'm trying to figure out how many times my computer will have to loop through an array. I'm building a logic calculator so it's checking contradictions. If there are four sentences, a b c d, then one has to check the following combinations to see if there is a contradiction

    ab
    ac
    ad
    bc
    bd
    cd

    The equation seems to be, let n = the number of sentences:

    (n - 1) + (n - 2) + (n - 3)

    But that's not a good equation because it does not inform us how many things to add together.

    If there are six sentences then the equation would be

    (n - 1) + (n - 2) + (n - 3) + (n - 4) + (n - 5)

    There has to be a better way to write that equation.
     
  2. jcsd
  3. In probability, it looks like it would be written as 4 choose 2, meaning that you have 4 sentences and choose 2 of them. The equation gives the number of unique results (ab is the same as ba). Google "Combination".
     
  4. Hey, computer scientist here. Cool project you're working on. I stumbled across this pattern while messing around with tabular K-map simplification (boolean logic):

    You have 4 variables (but this can be generalized to n variables) and are trying to find the total number of associative expressions such that AB = BA. (Looping through for A AND B as well as B AND A would be inefficient)

    This problem is analogous to finding the number of lines between a given number of points (see below). The formula is
    $$
    \frac{n^2-n}{2}
    $$

    Send me a PM: I'd like to take a closer look at your logic calculator.

    [​IMG]

    [​IMG]
    *plus sign changed to minus sign as per jz92's post
     

    Attached Files:

    Last edited: Sep 6, 2014
  5. The general equation for evaluating the number of unique combinations when you select k items from a set of n items is:

    $$
    \frac{n!}{(n-k)!*k!}
    $$

    n choose 2 is
    $$
    \frac{n!}{(n-2)!*2!}
    $$
    Simplified, it is:
    $$
    \frac{n^2-n}{2}
    $$

    Comparing each combination of 2, where there are 4 sentences, comes out to a total of (16-4)/2, or 6 comparisons. This, of course, requires that the loops are set up in a way that you never test the same combination twice.
     
    Last edited: Sep 6, 2014
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?

0
Draft saved Draft deleted