Art of Computer Programming Volume 4: Fascicle 3 has a ton of these that might fit your particular situation better than how I describe.
Gray Codes
An issue that you will come across is of course memory and pretty quickly, you'll have problems by 20 elements in your set -- 20C3 = 1140. And if you want to iterate over the set it's best to use a modified gray code algorithm so you aren't holding all of them in memory. These generate the next combination from the previous and avoid repetitions. There are many of these for different uses. Do we want to maximize the differences between successive combinations? minimize? et cetera.
Some of the original papers describing gray codes:
- Some Hamilton Paths and a Minimal Change Algorithm
- Adjacent Interchange Combination Generation Algorithm
Here are some other papers covering the topic:
- An Efficient Implementation of the Eades, Hickey, Read Adjacent Interchange Combination Generation Algorithm (PDF, with code in Pascal)
- Combination Generators
- Survey of Combinatorial Gray Codes (PostScript)
- An Algorithm for Gray Codes
Chase's Twiddle (algorithm)
Phillip J Chase, `Algorithm 382: Combinations of M out of N Objects' (1970)
The algorithm in C...
Index of Combinations in Lexicographical Order (Buckles Algorithm 515)
You can also reference a combination by its index (in lexicographical order). Realizing that the index should be some amount of change from right to left based on the index we can construct something that should recover a combination.
So, we have a set {1,2,3,4,5,6}... and we want three elements. Let's say {1,2,3} we can say that the difference between the elements is one and in order and minimal. {1,2,4} has one change and is lexicographically number 2. So the number of 'changes' in the last place accounts for one change in the lexicographical ordering. The second place, with one change {1,3,4} has one change but accounts for more change since it's in the second place (proportional to the number of elements in the original set).
The method I've described is a deconstruction, as it seems, from set to the index, we need to do the reverse – which is much trickier. This is how Buckles solves the problem. I wrote some C to compute them, with minor changes – I used the index of the sets rather than a number range to represent the set, so we are always working from 0...n.
Note:
- Since combinations are unordered, {1,3,2} = {1,2,3} --we order them to be lexicographical.
- This method has an implicit 0 to start the set for the first difference.
Index of Combinations in Lexicographical Order (McCaffrey)
There is another way:, its concept is easier to grasp and program but it's without the optimizations of Buckles. Fortunately, it also does not produce duplicate combinations:
The set that maximizes , where .
For an example: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1)
. So, the 27th lexicographical combination of four things is: {1,2,5,6}, those are the indexes of whatever set you want to look at. Example below (OCaml), requires choose
function, left to reader:
(* this will find the [x] combination of a [set] list when taking [k] elements *)
let combination_maccaffery set k x =
(* maximize function -- maximize a that is aCb *)
(* return largest c where c < i and choose(c,i) <= z *)
let rec maximize a b x =
if (choose a b ) <= x then a else maximize (a-1) b x
in
let rec iterate n x i = match i with
| 0 -> []
| i ->
let max = maximize n i x in
max :: iterate n (x - (choose max i)) (i-1)
in
if x < 0 then failwith "errors" else
let idxs = iterate (List.length set) x k in
List.map (List.nth set) (List.sort (-) idxs)
A small and simple combinations iterator
The following two algorithms are provided for didactic purposes. They implement an iterator and (a more general) folder overall combinations.
They are as fast as possible, having the complexity O(nCk). The memory consumption is bound by k
.
We will start with the iterator, which will call a user provided function for each combination
let iter_combs n k f =
let rec iter v s j =
if j = k then f v
else for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in
iter [] 0 0
A more general version will call the user provided function along with the state variable, starting from the initial state. Since we need to pass the state between different states we won't use the for-loop, but instead, use recursion,
let fold_combs n k f x =
let rec loop i s c x =
if i < n then
loop (i+1) s c @@
let c = i::c and s = s + 1 and i = i + 1 in
if s < k then loop i s c x else f c x
else x in
loop 0 0 [] x
I usually go with something like the implementation given in Josh Bloch's fabulous Effective Java. It's fast and creates a pretty good hash which is unlikely to cause collisions. Pick two different prime numbers, e.g. 17 and 23, and do:
public override int GetHashCode()
{
unchecked // Overflow is fine, just wrap
{
int hash = 17;
// Suitable nullity checks etc, of course :)
hash = hash * 23 + field1.GetHashCode();
hash = hash * 23 + field2.GetHashCode();
hash = hash * 23 + field3.GetHashCode();
return hash;
}
}
As noted in comments, you may find it's better to pick a large prime to multiply by instead. Apparently 486187739 is good... and although most examples I've seen with small numbers tend to use primes, there are at least similar algorithms where non-prime numbers are often used. In the not-quite-FNV example later, for example, I've used numbers which apparently work well - but the initial value isn't a prime. (The multiplication constant is prime though. I don't know quite how important that is.)
This is better than the common practice of XOR
ing hashcodes for two main reasons. Suppose we have a type with two int
fields:
XorHash(x, x) == XorHash(y, y) == 0 for all x, y
XorHash(x, y) == XorHash(y, x) for all x, y
By the way, the earlier algorithm is the one currently used by the C# compiler for anonymous types.
This page gives quite a few options. I think for most cases the above is "good enough" and it's incredibly easy to remember and get right. The FNV alternative is similarly simple, but uses different constants and XOR
instead of ADD
as a combining operation. It looks something like the code below, but the normal FNV algorithm operates on individual bytes, so this would require modifying to perform one iteration per byte, instead of per 32-bit hash value. FNV is also designed for variable lengths of data, whereas the way we're using it here is always for the same number of field values. Comments on this answer suggest that the code here doesn't actually work as well (in the sample case tested) as the addition approach above.
// Note: Not quite FNV!
public override int GetHashCode()
{
unchecked // Overflow is fine, just wrap
{
int hash = (int) 2166136261;
// Suitable nullity checks etc, of course :)
hash = (hash * 16777619) ^ field1.GetHashCode();
hash = (hash * 16777619) ^ field2.GetHashCode();
hash = (hash * 16777619) ^ field3.GetHashCode();
return hash;
}
}
Note that one thing to be aware of is that ideally you should prevent your equality-sensitive (and thus hashcode-sensitive) state from changing after adding it to a collection that depends on the hash code.
As per the documentation:
You can override GetHashCode for immutable reference types. In general, for mutable reference types, you should override GetHashCode only if:
- You can compute the hash code from fields that are not mutable; or
- You can ensure that the hash code of a mutable object does not change while the object is contained in a collection that relies on its hash code.
The link to the FNV article is broken but here is a copy in the Internet Archive: Eternally Confuzzled - The Art of Hashing
Best Answer
There is a way to reduce this to a simple sub-problem.
There are 2 parts to the explanation, the algorithm, and the reason the algorithm provides an optimal solution. The first won't make sense without the second, so I'll start with the why.
If you think of bombing the rectangle (assume a big rectangle - no edge cases yet) you can see that the only way to reduce the hollow rectangle of squares on the perimeter to 0 is to bomb either the perimeter or to bomb the hollow rectangle of squares just inside the perimeter. I'll call the perimeter layer 1, and the rectangle inside it layer 2.
An important insight is that there is no point bombing layer 1, because the "blast radius" you get from doing so is always contained within the blast radius of another square from layer 2. You should be able to easily convince yourself of this.
So, we can reduce the problem to finding an optimal way to bomb away the perimeter, then we can repeat that until all squares are 0.
But of course, that won't always find an optimal solution if it's possible to bomb away the perimeter in a less than optimal fashion, but by using X extra bombs make the problem of reducing the inner layer simpler by >X bombs. So, if we call the permiter layer one, if we place an extra X bombs somewhere in layer 2 (just inside layer 1), can we reduce the effort of later bombing away layer 2 by more than X? In other words, we have to prove we can be greedy in reducing the outer perimeter.
But, we do know we can be greedy. Because no bomb in layer 2 can ever be more efficient in reducing layer 2 to 0 than a strategically placed bomb in layer 3. And for the same reason as before - there is always a bomb we can place in layer 3 that will affect every square of layer 2 that a bomb placed in layer 2 can. So, it can never harm us to be greedy (in this sense of greedy).
So, all we have to do is find the optimal way to reduce the permiter to 0 by bombing the next inner layer.
We are never hurt by first bombing the corner to 0, because only the corner of the inner layer can reach it, so we really have no choice (and, any bomb on the perimeter that can reach the corner has a blast radius contained in the blast radius from the corner of the inner layer).
Once we have done so, the squares on the perimeter adjacent to the 0 corner can only be reached by 2 squares from the inner layer:
At this point the perimeter is effectively a closed 1 dimensional loop, because any bomb will reduce 3 adjacent squares. Except for some weirdness near the corners - X can "hit" A,B,C,and D.
Now we can't use any blast radius tricks - the situation of each square is symmetric, except for the weird corners, and even there no blast radius is a subset of another. Note that if this were a line (as Colonel Panic discusses) instead of a closed loop the solution is trivial. The end points must be reduced to 0, and it never harms you to bomb the points adjacent to the end points, again because the blast radius is a superset. Once you have made your endpoint 0, you still have a new endpoint, so repeat (until the line is all 0).
So, if we can optimally reduce a single square in the layer to 0 we have an algorithm (because we have cut the loop and now have a straight line with endpoints). I believe bombing adjacent to the square with the lowest value (giving you 2 options) such that the highest value within 2 squares of that lowest value is the minimum possible (you may have to split your bombing to manage this) will be optimal but I don't (yet?) have a proof.