Thread: A mathematical algorithm question

  1. #1
    Registered User
    Join Date
    Feb 2012
    Posts
    29

    A mathematical algorithm question

    (I am not sure if this is the right section of the forum to post,I think it is)

    Let's say there are 50 numbers starting from 1 to 50.They will be grouped like:

    1 2 3 4
    1 2 3 5
    1 2 3 6
    ...
    2 3 4 5
    2 3 4 6
    2 3 4 7
    ...

    and end with:
    47 48 49 50

    I want to learn how many "1" number and "2" number(in the same combination) there are in the results.What would be the mathematical formula for calculating this?

  2. #2
    Registered User
    Join Date
    Jun 2011
    Posts
    4,513
    Can you elaborate on what you mean by "1" number and "2" number?

  3. #3
    Registered User
    Join Date
    Feb 2012
    Posts
    29
    Thanks for your answer.I mean how many 1 and 2 numbers are there in the results?

    1 2 3 4 //There are 1 number and 2 number
    ...
    1 4 5 6 //There is 1 number
    ...
    3 6 7 8 //There are no 1 or 2 numbers

    How many combinations are there which include 1 or 2 numbers?
    Last edited by Awareness; 04-26-2013 at 01:21 PM.

  4. #4
    Registered User
    Join Date
    Jun 2011
    Posts
    4,513
    Perhaps "algorithm" is a more fitting term than "formula" for this. And this would be a good exercise to pursue yourself.

    To develop the algorithm, go through the exercise "by hand" with a pen and paper. What process do you go through mentally to determine how many 1's and/or 2's are in each line? Take it step by step, and you should start to see a pattern. This pattern is what you should use to start developing an algorithm. When you have a list of steps you've taken to get results, start turning it into code.

  5. #5
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    An easy way to look at this:

    Assume 1 and 2 are part of the result, so there are 48 numbers left in the 'pool' to choose. How many different combinations are there for the remaining two numbers? That tells you how many combinations have both 1 and 2.

    If you want to know how many have 1, or 2, or both, then it's a bit trickier but it follows the same principles. Figure out how many ways you could pick numbers such that:
    * There is a 1 but not a 2
    * There is a 2 but not a 1
    * There is both a 1 and a 2

    The simple way to do this is imagine that you put every possible number into a hat and draw however many numbers it takes to fill the blanks in your patterns. Just remember, if you have 10 numbers in a hat, there are 10 possibilities... and you're left with 9 numbers in the hat (and 9 possibilities) for your next draw.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  6. #6
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    I am interested in this one, have thought about it before, never came up with a formula though, am crap at maths. - Am trying to get onto cat's suggestion but can't make it add up to the answers below

    For say a max range of 6 numbers

    range = 6
    line length = 4
    ocurrences to match = 2 (being nums 1 & 2 here but that is moot..)

    parameters:
    combos of 4 from 6 = 15
    combos of 2 from 6 = 15
    combos of 2 from 4 = 6

    In this example the number of lines containing 1 & 2 = 6

    1234
    1235
    1236
    1245
    1246
    1256
    - next line fails - 1345

    Another one, now max range is 7:

    parameters:
    range = 7
    line length = 4
    ocurrences to match = 2

    combos of 4 from 7 = 35
    combos of 2 from 7 = 21
    combos of 2 from 4 = 6

    In this example the number of lines containing 1 & 2 = 10

    1234
    1235
    1236
    1237
    1245
    1246
    1247
    1256
    1257
    1267
    - next line fails - 1345

    so can a general formula be written, relationship identified, given the answers in these examples
    and the parameters used?
    Last edited by rogster001; 04-30-2013 at 04:01 AM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  7. #7
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    For 1 and 2 this should actually be easy. Every combination here is ordered, so if 1 and 2 both appear, they have to appear in the first two places. In other words, all the qualifying combinations start with "1 2", and there's only two places left to fill with any ordered selection from 3-50, i.e. select from 48 numbers. There are 47 combinations that start with 3, 46 that start with 4, 45 that start with 5, etc - eventually we get to 1 combination starting with 49. If we switch this around, this is 1 (for 49) + 2 (for 48) + ... + 46 (for 4) + 47 (for 3), i.e. the 47th triangle number. The Nth triangle number is N*(N+1)/2, so we have 47*48/2 = 1128. There's your answer.

    The problem is much harder when you have other fixpoints than 1 and 2. If you look for, say, 3 and 40, you have to deal with combinations that look like "a b 3 40", "a 3 b 40", "a 3 40 b", "3 a b 40", "3 a 40 b" and "3 40 a b". You'd have to calculate the number of possible combinations for each of those individually and sum them up. Stricly speaking, 1 2 is a special case where all but the last of these patterns just yield 0 possibilities.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  8. #8
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    I have worked out a formula for it, this works for any valid set of paramters, [edit]Except for non fixed as per CornedBee post![/edit]

    I not read the above post example properly yet but i think it might be a lot simpler formula than mine!

    Anyway:
    You can use it for ocurrences of 1st marker only, or 1st & 2nd, or 1st, 2nd, 3rd or
    whatever.

    i'll attempt to describe it like this:

    let c = combo range to check, eg 1&2
    let s = sub range, ie the 'line length' eg in the original posts this was 4
    let R = total Range, eg in the original posts this was 50
    let O = occurences, the actual result, eg how many times did 1&2 occur

    formula is:

    O = ((combos of c,s) * (combos of s,R)) / combos of c,R

    here are some sample results:

    checking for 1 & 2:

    c s R O
    2 3 3 1
    2 3 4 2
    2 3 5 3
    2 3 6 4
    2 3 7 5
    2 3 8 6
    2 3 9 7
    2 3 10 8

    2 4 4 1
    2 4 5 3
    2 4 6 6
    2 4 7 10
    2 4 8 15
    2 4 9 21
    2 4 10 28

    2 5 5 1
    2 5 6 4
    2 5 7 10
    2 5 8 20
    2 5 9 35
    2 5 10 56

    checking for 1,2,3:
    c s R O
    3 5 5 1
    3 5 6 3
    3 5 7 6
    3 5 8 10
    3 5 9 15

    checking for 1:
    c s R O
    1 3 5 6
    1 3 6 10
    1 3 7 15
    1 3 8 21
    1 3 9 28
    1 3 10 36

    [EDIT]
    Checked the CornedBee idea like 47*48/2 ... but i cant get it to work where the subrange, ie line length is different than 4, is another bit needed for that?
    Last edited by rogster001; 05-09-2013 at 08:20 AM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  9. #9
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    For 1 and 2 this should actually be easy. Every combination here is ordered, so if 1 and 2 both appear, they have to appear in the first two places. In other words, all the qualifying combinations start with "1 2", and there's only two places left to fill with any ordered selection from 3-50
    If you consider the numbers per line as placeholders then fixed position does not matter. If you treat your combo of 2 as being simply any pair then choosing say 1 and 40 has the same amount of appearences (sharing the same line of subrange) throughout the range as choosing 1 and 2. Using the formula i posted proves this, but it also makes sense anyway.

    like

    looking for pairs in a line where the total range is 6 and subrange is 4

    complete set of combos for subrange of range is 15:
    1234
    1235
    1236
    1245
    1246
    1256
    1345
    1346
    1356
    1456
    2345
    2346
    2356
    2456
    3456

    If you take any pair of numbers they appear in the same amount of lines each, 6
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. algorithm question..
    By henri in forum C Programming
    Replies: 0
    Last Post: 12-13-2011, 07:39 AM
  2. Quick question on mathematical notation (translating to C)
    By gardhr in forum General Discussions
    Replies: 16
    Last Post: 09-17-2011, 12:00 AM
  3. algorithm question?
    By s_ny33 in forum C Programming
    Replies: 8
    Last Post: 10-10-2005, 06:53 PM
  4. STL algorithm question
    By Reggie in forum C++ Programming
    Replies: 1
    Last Post: 04-22-2003, 09:04 AM
  5. Mathematical Question
    By rmullen3 in forum C++ Programming
    Replies: 4
    Last Post: 12-29-2001, 09:44 PM