combinatorics
How can I get pairs of values, where the first is taken from one list and the second from another list? [duplicate]
These are not really “combinations” in the sense of combinatorics. These are rather elements from the Cartesian product of a and b. The function in the standard library to generate these pairs is itertools.product(): for i, j in itertools.product(a, b): # Whatever
Google Interview: Arrangement of Blocks
This is a counting problem, not a construction problem, so we can approach it using recursion. Since the problem has two natural parts, looking from the left and looking from the right, break it up and solve for just one part first. Let b(N, L, R) be the number of solutions, and let f(N, L) … Read more
What does this list permutations implementation in Haskell exactly do?
Sorry about the late answer, it took a bit longer to write down than expected. So, first of all to maximize lazyness in a list function like this there are two goals: Produce as many answers as possible before inspecting the next element of the input list The answers themselves must be lazy, and so … Read more
Set partitions in Python
Since this nice question has been brought back to life, here’s a fresh answer. The problem is solved recursively: If you already have a partition of n-1 elements, how do you use it to partition n elements? Either place the n‘th element in one of the existing subsets, or add it as a new, singleton … Read more
How can I print out all possible letter combinations a given phone number can represent?
In Python, iterative: digit_map = { ‘2’: ‘abc’, ‘3’: ‘def’, ‘4’: ‘ghi’, ‘5’: ‘jkl’, ‘6’: ‘mno’, ‘7’: ‘pqrs’, ‘8’: ‘tuv’, ‘9’: ‘wxyz’, } def word_numbers(input): input = str(input) ret = [”] for char in input: letters = digit_map.get(char, ”) ret = [prefix+letter for prefix in ret for letter in letters] return ret ret is a … Read more
Creating all possible k combinations of n items in C++
From Rosetta code #include <algorithm> #include <iostream> #include <string> void comb(int N, int K) { std::string bitmask(K, 1); // K leading 1’s bitmask.resize(N, 0); // N-K trailing 0’s // print integers and permute bitmask do { for (int i = 0; i < N; ++i) // [0..N-1] integers { if (bitmask[i]) std::cout << ” ” … Read more
Combinatoric ‘N choose R’ in java math?
The Formula It’s actually very easy to compute N choose K without even computing factorials. We know that the formula for (N choose K) is: N! ——– (N-K)!K! Therefore, the formula for (N choose K+1) is: N! N! N! N! (N-K) —————- = ————— = ——————– = ——– x —– (N-(K+1))!(K+1)! (N-K-1)! (K+1)! (N-K)!/(N-K) K!(K+1) … Read more