Restate the problem

Reading:

I’m going to get two numbers n and k. N is the size of a population. k is the number of items I choose out of that population per iteration. I need to count the number of different ways I can choose k items out of a population n.

Solution steps

In reading the Wikipedia article on combinations, I saw the formula shown below to calculate the number of 5-card poker hands possible from a standard 52-card deck.

I wrote two different implementations of “n choose k” algorithms in Python, but neither gave the correct answer for the sample dataset.

I installed the scipy library, used the perm method, and got the correct answer instantly.

I downloaded a Project Rosalind dataset and got a correct response on my first attempt, then moved on to other challenges. However, now that I’m writing this article, I want to figure out how to implement the “n choose k” algorithm myself.

I’ve borrowed a recursive factorial function that I wrote from another challenge, and I figured out that my function to count the number of combinations of n items from a set of size k was just missing a set of parentheses, so that works now, it return the correct result for the example given on wikipedia, but it returns a different result than Scipy perm.

Using Wolfram Alpha, I learned about the difference between counting combinations vs counting permutations.

I fixed my own code so that returned the same results as Scipy perm. Then I removed all the Scipy code from my solution and downloaded another dataset from Project Rosalind. My full set of code for this challenge after removing the Scipy library:

def fact(n):
    if n < 2:
        return 1
    else:
        return n * fact(n - 1)

def comb(n, k):
    return fact(n) // (fact(n - k))

if __name__ == "__main__":
    file_path = "/Users/robertbryan/Downloads/rosalind_pper.txt"
    file = open(file_path, "r").read().split(' ')
    n, k = int(file[0]), int(file[1])
    print(comb(n, k) % 1000000)

This returned a correct result for the new dataset.

Post-solution notes

Challenges solved so far: 45 (I solved this challenge for the first time in 2018.)

Time spent on challenge: 90 minutes, mostly on the rewrite I did to replace the library code with my own code.

Most time-consuming facet: Getting clear on the difference between counting combinations and permutations.

Closing thoughts: I’m glad I coded this myself instead of accepting the library result and moving on. I got clearer about the distinction between combinations and permutatations, which is helpful.