In part three we enumerated all the combinations of a particular size from a sequence by observing that the sequence {50, 60, 70, 80, 90} had combinations of exactly three elements as follows: Continue reading
Last time I showed how to use an immutable stack of Booleans to act as flags indicating whether a particular element of a sequence should be chosen as one of the combinations of exactly k elements. A reasonable criticism of this approach is that when you have a stack containing, say, thirty flags, each of which is a managed object and contains a Boolean and a reference, then we’ve overspent by a large factor; thirty bits could fit into a single int.
All right, we have an immutable stack of Booleans and we wish to produce all such stacks of size n that have exactly k true elements. As always, a recursive algorithm has the following parts:
Let’s start with a signature. What do we have? integers n and k. What do we want? A sequence of Boolean stacks such that the size is n, and there are k bits turned on. We therefore require that n and k both be non-negative, and that n be greater than or equal to k. Continue reading
Last time we saw that producing all the subsequences of a given size k from a given sequence of size n is essentially the same problem as computing all the sequences of n Booleans where exactly k of them are true. How do we do that?
An approach that I often see is “enumerate all sequences of n Booleans, count the number of on bits, and discard those which have too many or too few”. Though that works, it’s not ideal. Suppose we are seeking to enumerate the combinations of 16 items chosen from a set of 32. There are over four billion possible combinations of 32 bits, and of those over three billion of them have more or fewer than 16 true bits, so that’s a lot of counting and discarding to do. We can do better! To do so, we’ll use a combination of all my favourite techniques:
Long-time readers of this blog will have seen me use these techniques before, but for new readers, a quick introduction is in order. Continue reading
I’ve done many articles over the years on different ways to manipulate sets and sequences in C#: The Cartesian product is when you have a sequence of sequences, say Continue reading
Last time on FAIC I generated a “random” permutation of a deck of cards and gave you the first five cards, and challenged you to determine what the next five cards were. David Poeschl (of the Roslyn team!) was the first to get a possible order and, with the additional hint that the sixth card was the three of hearts, Joel Rondeau found the correct solution, which is below. Both used brute-force algorithms.
Last time in this series I presented an algorithm for generating a random number, and the time before I presented an algorithm that turns such a number into a permutation, so we can put them together to make an algorithm that returns a random permutation:
static Permutation RandomPermutation(int size, Random random)
{
return Permutation.NthPermutation(size, RandomFactoradic(size, random));
}
Is this actually a correct algorithm for generating a random permutation? Give it some thought.
Last time on FAIC I showed how you could produce the mth permutation of n elements, where m is a number between zero and n!-1 that chooses from the n! possible permutations. There’s a very interesting way to represent numbers that are always less than n! for a given n that I thought I might talk about today.
Last time on FAIC I implemented a short algorithm that produces a sequence containing every permutation of a given size, such that the sequence is a Hamiltonian tour of the vertices of the n-dimensional permutohedron. That is, the shape you get when you make each vertex have the coordinates of a permutation, and an edge connects two permutations that differ only by a swap of adjacent items.
Since we have an algorithm that produces the same order every time, we can number each ordering; it is convenient to do so starting with zero and going to n!-1. What I’d like is an algorithm which given size, the number of items in the permutation, and index, an integer between zero and size!-1, gives back the indexth permutation of length size, without having to calculate all of them.
Last time on FAIC I described an algorithm for producing every permutation of size n such that any two successive permutations differ only by swapping two adjacent items. Today let’s actually write some code to implement this algorithm.
Fabulous adventures in coding 