Home > Palm > Samples > Combination
 
  Combination

What's that?

Remember those lessons of statistics you had long ago? Factorial? Combination? Well, we'll take those formulas to show how you can develop a mobile application using various SDK's and tools.

Factorial

Let's say we have letters A, B and C. How many "words" can we make, using each letter only once. By word, we mean "any series of three letters, even if it's not in a dictionary". ACB is one of them. Let's list all of'em: ABC, ACB, BAC, BCA, CAB, CBA. Another way to look at it is to say:

  1. For the first letter, I can pick A, B or C, which means I have 3 possibilities. Let me pick A.
  2. Then, for the second letter, I can only pick B or C, which means 2 possibilities. I pick B
  3. Finally, the only option left for the last letter is C: 1 possilibity

The total number of words is 6: three possibilities multiplied by two possibilities then by one. Hey that works! Look at our enumeration of words a bit above! Great... We just illustrated how to calculate a factorial: factorial(3)=3x2x1=6. You'll write this as 3! = 6.

4! = 4x3x2x1 = 4 x (3x2x1)= 4 x 3!
5! = 5x4x3x2x1 = 5 x (4x3x2x1) = 5 x 4!
1000! = 1000x999x998x997x...x1 = 1000 x 999!, or as a general definition:
n! = n x (n-1)!

Combination

Now, let's take another example. You would like to win the prize of this $1000 lottery. Here's the rule: there are five balls numbered 1 thru 5 and you must pick two of them. How many combinations are there? Well, go back to our previous example and apply the same principle here:

  1. For the first ball, I have 5 choices
  2. For the second one, I only have 4 choices
  3. For the third one... Hey, wait a minute, there is NO such "third one". You are allowed to pick only two numbers!

The total number of choices is 5 x 4 = 20.

Really? Is is THAT simple? Well, not quite! Let's see why. Here's a list of all the combinations:

  • 1 2
  • 1 3
  • 1 4
  • 1 5
  • 2 1... Er... Really?!? No way!!! Actually, in any lottery, "1 and 2" is same as "2 and 1"
  • 2 3... This one is okay, let's continue on without repeating choices as in previous bullet
  • 2 4
  • 2 5
  • 3 4
  • 3 5
  • 4 5

In other words, ORDER doesn't count. Well, it's a good thing for us whenever we buy a lottery ticket, as this gives us the chance to win if the winner is "ball 5 and ball 2" and we chose "ball 5 and ball 2".

So, we'll have to divide our "5 x 4 = 20" from above by 2. If we had to pick 3 balls, we would divide 5 x 4 x 3 by 3 x 2, because there are 3x2 ways of making a "three-letter word out of three given letters".

You will notice that 5 x 4 = (5 x 4 x 3 x 2 x 1) / (3 x 2 x 1) = 5! / 3!

The final result is 5! / 3! / 2! = 10. Check this formula against the list above.

You probably know that 3 = 5 - 2.

Remember? 5 is the total number of balls and 2 is how many of'em we can pick. The general formula to calculate the number of combinations of n items taken by p at a time is:

= n! / (n-p)! / p! = n! / [(n-p)! x p!]

Our sample

This small app implements three modules:

  1. factorial
  2. combination, which calls factorial three times, as the formula states
  3. go, which calls factorial(n), factorial(p), factorial(n-p) just to display intermediate values, and finally combination(n, p)

I intentionally didn't optimize this application. In a commercial app, it would make sense to not code the combination formula as is. It'd be smarter to calculate a "partial factorial" than to calculate two factorials and divide them.

Same remark for recursion. We did use recursion whenever the language's implementation allowed it. Again, a simple loop would run quicker and save stack space, which is very valuable on our small devices :)

 
[ Copyright © 2000- Eric Poncet - All rights reserved ]

[ Stage de musique classique | Stage de musique baroque | Stage de musique de chambre | Stage de musique latine ]
[ Stage de jazz | Stage de musiques actuelles | Stage de funk | Stage de metal | Stage de pop | Stage de reggae | Stage de rock ]
[ Stage d'improvisation | Colonie musicale ]