1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Does this equation have a name?

  1. Sep 3, 2014 #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. Sep 3, 2014 #2
    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. Sep 6, 2014 #3
    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.

    attachment.php?attachmentid=72797&stc=1&d=1410029342.png

    attachment.php?attachmentid=72798&stc=1&d=1410029342.png
    *plus sign changed to minus sign as per jz92's post
     

    Attached Files:

    Last edited: Sep 6, 2014
  5. Sep 6, 2014 #4
    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 this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Does this equation have a name?
Loading...