algorithm

Understanding this matrix transposition function in Haskell

by

Let’s look at what the function does for your example input: transpose [[1,2,3],[4,5,6],[7,8,9]] <=> (map head [[1,2,3],[4,5,6],[7,8,9]]) : (transpose (map tail [[1,2,3],[4,5,6],[7,8,9]])) <=> [1,4,7] : (transpose [[2,3],[5,6],[8,9]]) <=> [1,4,7] : (map head [[2,3],[5,6],[8,9]]) : (transpose (map tail [[2,3],[5,6],[8,9]])) <=> [1,4,7] : [2,5,8] : (transpose [[3],[6],[9]]) <=> [1,4,7] : [2,5,8] : (map head [[3],[6],[9]]) : (transpose … Read more

How can I find the center of a cluster of data points?

by

The following solution works even if the points are scattered all over the Earth, by converting latitude and longitude to Cartesian coordinates. It does a kind of KDE (kernel density estimation), but in a first pass the sum of kernels is evaluated only at the data points. The kernel should be chosen to fit the … Read more

White balance algorithm [closed]

by

GIMP apparently uses a very simple algorithm for automatic white balancing. http://docs.gimp.org/en/gimp-layer-white-balance.html The White Balance command automatically adjusts the colors of the active layer by stretching the Red, Green and Blue channels separately. To do this, it discards pixel colors at each end of the Red, Green and Blue histograms which are used by only … Read more

Traversing a n-ary tree without using recurrsion

by

What you are doing is essentially a DFS of the tree. You can eliminate recursion by using a stack: traverse(Node node) { if (node==NULL) return; stack<Node> stk; stk.push(node); while (!stk.empty()) { Node top = stk.pop(); for (Node child in top.getChildren()) { stk.push(child); } process(top); } } If you want a BFS use a queue: traverse(Node … Read more

Find nth SET bit in an int

by

Nowadays this is very easy with PDEP from the BMI2 instruction set. Here is a 64-bit version with some examples: #include <cassert> #include <cstdint> #include <x86intrin.h> inline uint64_t nthset(uint64_t x, unsigned n) { return _pdep_u64(1ULL << n, x); } int main() { assert(nthset(0b0000’1101’1000’0100’1100’1000’1010’0000, 0) == 0b0000’0000’0000’0000’0000’0000’0010’0000); assert(nthset(0b0000’1101’1000’0100’1100’1000’1010’0000, 1) == 0b0000’0000’0000’0000’0000’0000’1000’0000); assert(nthset(0b0000’1101’1000’0100’1100’1000’1010’0000, 3) == 0b0000’0000’0000’0000’0100’0000’0000’0000); assert(nthset(0b0000’1101’1000’0100’1100’1000’1010’0000, … Read more

Secret Santa – Generating ‘valid’ permutations

by

What you’re looking for is called a derangement (another lovely Latinate word to know, like exsanguination and defenestration). The fraction of all permutations which are derangements approaches 1/e = approx 36.8% — so if you are generating random permutations, just keep generating them, and there’s a very high probability that you’ll find one within 5 … Read more