Problem Solutions: Combinations counting (task 128) - Whats wrong with my code?

rilianus 2014-10-13 05:49:06

Sorry, I've edited your post a bit - Admin

For a given N and K calculate C(N, K) - the number of different combinations of the data

#...
# UFO have stolen code from here to study :)
#...

# The expected answer was:
'29796772356 39443226966 3127595016 22760723700 35641470150 12846240784 4529365776 21243342120 12565671261'
# And my answer:
'28163417842 39443226965 3127595016 21519589904 35641470150 11097636665 3455623952 19342855996 12565671261 '

It seems that I'm missing some cases for some of the values, but surprisingly some of the answers are exactly right. What is the problem here, if I don't see anything distinguishable in wrong and right answers?

Rodion (admin) 2014-10-13 11:00:17

When I ran your code, I give the correct results (equal to these given in "expected answer").

Could there be some miracle with version of Python you use?

By the way you are doing unnecessary many multiplications. For example C(109, 7) is:

109 * 108 * 107 * 106 * 105 * 104 * 103
---------------------------------------
       1 * 2 * 3 * 4 * 5 * 6 * 7

Of course Python handles long values well (usually) but it is not quite efficient :)

UPD: I also tried to run your code directly from site - it works correctly, i.e. first value ends with ...56 - so there is no problem with your code.

rilianus 2014-10-14 09:14:20

Thank you very much for your help :)

First of all I was posting this code just before the class, so I saw that the formatting was all wrong, but I didn't have time to do anything about it - so thank you for taking care of that.

Second of all you saved me a lot of frustration - It'd taken me a lot of time to figure out to try another interpreter, since I just assumed my code sucked. When I ran it directly in the shell, instead of using repl.it the answers were all correct and I was able to finish the challenge ;)

And third of all thank you for your suggestion on optimization - I've taken care of that and the code runs much faster right now :)

Rodion (admin) 2014-10-14 09:26:59

Thanks a lot for confirming that you succeeded with this task - glad to hear it! :)

And thanks for all your kind word and for your participation! ;-)

Crakadoo 2015-11-29 15:16:48

Admin, thank you for this example

109 * 108 * 107 * 106 * 105 * 104 * 103
---------------------------------------
   1 * 2 * 3 * 4 * 5 * 6 * 7

How you calculate in this event: C(99, 92) or C(74, 66)?

Rodion (admin) 2015-11-30 08:40:16

Hi! Thanks for your question.

Remember the formula:

                n!
C(n, k) = --------------_
           k! * (n - k)!

You may see from it that it has a kind of symmetry - really, if you want to calculate C(n, n-k) it would be just the same! This gives a nice way to simplify calculations with large k:

                n!                n!
C(n, k) = -------------- = --------------- = C(n, n-k)
           k! * (n - k)!    (n - k)! * k!

So we can calculate C(99, 92) in the same way we calculate C(99, 99-92) = C(99, 7)... Hope this helps!