[RESOLVED] Groups and combinations.

[gordoncom]

I need a formula for a betting app I am writing. It concerns multiple bets ie doubles and trebles. For a bet of 4 selections where all the selections are runners there are 6 doubles AB AC AD BC BD CD and 4 trebles ABC ABD ACD BCD. Now if any selection fails to run for whatever reason then the bet still stands so long as one of the selections involved still runs. So, if 2 selections fail to run, say A and B the doubles are changed thus :-
AB void
AC – C
AD – D
BC –C
BD –D
CD unchanged
The trebles are changed thus
ABC –C
ABD –D
ACD-CD
BCD-CD
If three of the selections fail to run, then all bets where those selections would have been included are altered in a similar manner. I need to be able to compute the changed multiples ie doubles trebles singles etc for all selections from 4 to 8. For the life of me I can’t figure it out. I wonder if anyone would be kind enough to provide a solution. Many thanks.

[Lenggries]

If I read your problem correctly, this is more of an algorithm and programming question that is probably best addressed in the forum for whatever language you are programming in.

That said, I would approach this by making a data structure that consisted of boolean flags representing their bets. So there is a flag for A, one for B, etc. Thus, if they had a double of "AB", their data structure would look something like this:
A - TRUE
B - TRUE
C - FALSE
D - FALSE

So then if A "fails to run", you simply go through each data structure and set A to False, giving us:
A - FALSE
B - TRUE
C - FALSE
D - FALSE

Once every selection is false, it is void.

If your language can operate bitwise on numbers (like long or int datatypes), this approach can be highly efficient, as each selection can be represented by a single bit, and you can determine if something is void simply by checking if the total value equals 0. The syntax for doing that, however, is best discussed in a thread specific to that language.

[jemidiah]

I'd go with the boolean flag array (Lenggries' first suggestion). Bitwise arithmetic is probably too complex for someone asking this question. You can simulate the fast zero testing bitwise arithmetic gets you by keeping a count of the number of non-zero entries in the flag array. Most likely speed is a complete non-issue and should be ignored in favor of simple, correct, easy-to-maintain code anyway.

[gordoncom]

Thanks for the replies. I think I was hoping that a relationship could be found between the various variables, ie nr selections, treble etc so that a formula would emerge for easy calculation but given that such is not apparent I will go with the suggested replies. THanks again.

[jemidiah]

I think I was hoping that a relationship could be found between the various variables, ie nr selections, treble etc so that a formula would emerge for easy calculation

Maybe we're confused about your question.... Actually, I just reread it and came up with a different, much more interesting, interpretation. Perhaps you want to compute the number of possible choices under a few constraints, rather than actually writing a program that simulates making those choices.


Given n objects to bet on and k of those objects to select, there are (n choose k) different possible ways to make those selections. You gave the n=4, k=2 example (AB, AC, AD, BC, BD, CD) in your first post; there are 6 = (4 choose 2) of them. Here, "n choose k" is the binomial coefficient. It can be calculated using many libraries, or you could write your own function. The formula is...

(n choose k) = n*(n-1)*...*(n-(k-1)) / [k*(k-1)*...*2*1]

Note that 4 choose 2 = 4*3 / [2*1] = 6.

Now, suppose that m of the original objects are taken away. Here your question becomes fuzzy again. What precisely do you want to calculate? "I need to be able to compute the changed multiples ie doubles trebles singles"--how many q-element selections are left, for each q between 1 and k? Distinct or not? For instance, with n=4, k=2, m=2, we can simulate the process by removing AB from ABCD:

AB -> empty
AC -> C
AD -> D
BC -> C
BD -> D
CD -> CD

So, for q=1, we have C or D (though these both occur twice; does that matter?), and for q=2 we have only CD. Wrapping this all up in a function f(n, k, m, q), we have f(4, 2, 2, 2) = 1 and f(4, 2, 2, 1) = 2 (or 4?). And you want a general formula for f so you don't have to brute force the situation? Let me think....

It boils down to picking a final arrangement after the objects are taken away and figuring out how many initial arrangements turn in to that final arrangement. Given a length q final arrangement, length k initial arrangements have to take away (k-q) objects just to get the length right. These of course must be chosen from the m total objects which get taken away. In all, (m choose k-q) initial arrangements hit the same final arrangement.

How many length q final arrangements are there? They must be chosen from the n-m remaining objects, so there are (n-m choose q) of them. The explicit form of f is then either

f_nodup(n, k, m, q) = (n-m choose q)
(no duplicates)

or

f_dup(n, k, m, q) = (n-m choose q) * (m choose k-q)
(counting duplicates)

As a sanity check, try the n=5, k=3, m=2 case, again removing AB:
ABC -> C
ABD -> D
ABE -> E
ACD -> CD
ACE -> CE
ADE -> DE
BCD -> CD
BCE -> CE
BDE -> DE
CDE -> CDE
=> f_nodup(5, 3, 2, 1) = 3 [C, D, E]
=> f_dup(5, 3, 2, 1) = 3 [each appears once]

=> f_nodup(5, 3, 2, 2) = 3 [CD, CE, DE]
=> f_dup(5, 3, 2, 2) = 6 [each appears twice]

=> f_nodup(5, 3, 2, 3) = 1 [CDE]
=> f_dup(5, 3, 2, 3) = 1 [each appears once]

[I checked, and my formulae agree.]


Finally, a nice mathy point. When counting with duplicates, each initial arrangement was included precisely once, which gives us a roundabout method to compute the number of initial arrangements. Since this is by definition (n choose k), we have the formula

(n choose k) = sum for q from 0 to m of (n-m choose q) * (m choose k-q)

I just looked it up, and this is (the most important special case of a slightly rearranged version of) Vandermonde's identity. It was apparently known to a 14th century Chinese mathematician. The calculations above resulting in this formula constitute what's known as a combinatorial proof.

[gordoncom]

Jemidiah, thank you for taking the time to provide the answer you have. It is just what I was hoping for and has helped enormously. Thank you.

[jemidiah]

Glad I could help; sorry I misunderstood the question initially. I'm curious, were you after the f_dup or f_nodup function?

[Also... I don't want to sound like I'm bragging, but I also don't want too much praise for my time. It didn't take long to write the above--something like 20 minutes. The problem itself is actually very simple given a little background in combinatorics. Most of my time was spent typing. I'm also happy to see a combinatorial proof pop out of a common identity I wasn't aware of beforehand.]

[gordoncom]

f_dup. I have fashioned an answer of sorts for myself which works well enough without the presence of duplicates, but it is confounded by the presence of duplicates. Thank you again.