Constexpr, Permutations, Combinations, Binomial Theorem, and Infinite Sets

Channel:

Bill Kerney

Subscribers:

2,640

Published on September 7, 2021 8:13:22 PM ● Video Link: https://www.youtube.com/watch?v=ecsGbJgPJuE

Duration: 1:33:43

91 views

1

Today we covered a few different topics, starting with some C++ stuff and then moving on into the math world of combinatorics.


So one of the challenges of the Hash Table assignment was that the starter code I gave you had a template parameter called SIZE, but this means that it has to be *compile time* determinable. But if you are going to pass it in as a command line parameter, this obviously can't be known when you compile it!


So you have to refactor your code - leaving the functionality the same but changing how it works. Pull SIZE out of the template parameter list, and make it a private member variable. Then pass SIZE in as a constructor parameter and all the rest of your code should work the same. This will allow you to read from argc/argv (checking to make sure the right number of parameters were passed in) and automate your testing.


Next topic was permutations and combinations, which correspond closely to the concept of lists and sets.


A list is, essentially, an ordered set. A set has no order - if Bob and Cindy are in a group, they are in a group. It doesn't matter if you write {Bob,Cindy} or {Cindy,Bob} - writing them that way, in fact, would be a duplicate. But for lists, the order does matter. For example, if we are going to assign the roles of president and vice-president, Bob being Pres and Cindy being VP is different from Cindy being Pres and Bob being VP. So {Bob,Cindy} is different from {Cindy,Bob}, and we'd have to count both.


The equation to figure out how to line up N people in a list is: N!
The equation to figure out how to line up K people out of a group of N people in a list is: N!/(N-K)!


The relationship of a set to a list is: you first compute the size of a list - for example, if you want to see how many ways you can make a group of 4 from a pool of 10 people, you first compute how many ways you can line up 4 people from 10, which is the equation I just gave above: 10!/(10-4)!


And then you remove duplicates. Just as how {Bob,Cindy} and {Cindy,Bob} are duplicates in a set where order doesn't matter, we divide the number of ways of making a set by the number of duplicate entries we get, which is: K!


I.e. if we are making a group of three, there will be 3! = 6 duplicates for every answer, as you can have {Bob,Cindy,Steve},{Bob,Steve,Cindy},{Cindy,Bob,Steve},{Cindy,Steve,Bob},{Steve,Cindy,Bob},{Steve,Bob,Cindy} = 6 duplicates, when all we really want is one: {Bob,Cindy,Steve} when the order doesn't matter.


So the number of ways of making a committee of three from a class of 10 is this: 10!/(3!)(7!)


The general equation is, to see how many sets of size K you can make from a pool of size N: N!/(K!)(N-K!)


We call this "N choose K" and is a core part of the Computer Science vernacular. If you Duck Duck Go "10 choose 4" or whatever, DDG recognizes this and will give you the answer.



Pascal's Triangle is a cool way to compute the values of N choose K.


The Binomial Theorem, which expands (x+y)^N, just uses the Pascal's Triangle, aka N choose K, to come up with the coefficients without needing to tediously do the algebra for it. If you have coefficients for X and Y, you can substitute them out, do the Binomial Theorem, and substitute them back in.


Finally we talked about infinite sets. The size (cardinality) of Z (integers) is Aleph Null (N0). As we talked about before, if you can make a function that gives a one-to-one correspondence between two sets, the two sets have the same size. This results in the somewhat counterintuitive result that there are as many even numbers as integers, that there are as many numbers divisible by trillion as there are integers, that there are as many rational number (an integer divided by an integer) as integers, and so forth. All of the sets listed have the same size - Aleph Null. All of these sets we call "Countably Infinite".


HOWEVER, not all infinite sets are the same size. Some sets are not countably infinite. The most famous uncountably infinite set is all Real numbers (aka numbers with decimals and such, like pi or -10.1). There are, in fact, more real numbers between 0.000001 and 0.000002 than there are all integers. |R| is a much larger infinity than |Z|. If this hurts your brain, then you're doing it right!