Here’s a brute-force approach (it might be easier to understand): from itertools import chain def condense(*lists): # remember original positions positions = {} for pos, item in enumerate(chain(*lists)): if item not in positions: positions[item] = pos # condense disregarding order sets = condense_sets(map(set, lists)) # restore order result = [sorted(s, key=positions.get) for s in sets] … Read more
Here is the example of GNU Policy-Based STL MAP implemented as order statistic tree (tested on Linux gcc 4.6.1): #include <iostream> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef tree< int, int, less<int>, rb_tree_tag, tree_order_statistics_node_update> map_t; int main() { map_t s; s.insert(make_pair(12, 1012)); s.insert(make_pair(505, 1505)); s.insert(make_pair(30, 1030)); cout << s.find_by_order(1)->second << ‘\n’; … Read more
Perform line intersection tests for each pair of lines, one from each polygon. If no pairs of lines intersect and one of the line end-points of polygon A is inside polygon B, then A is entirely inside B. The above works for any type of polygon. If the polygons are convex, you can skip the … Read more
You can easily modify Floyd-Warshall algorithm. (If you’re not familiar with graph theory at all, I suggest checking it out, e.g. getting a copy of Introduction to Algorithms). Traditionally, you start path[i][i] = 0 for each i. But you can instead start from path[i][i] = INFINITY. It won’t affect algorithm itself, as those zeroes weren’t … Read more
EDIT: As FearUs pointed out, a better solution is to use Guava’s Sets.powerset(Set set). EDIT 2: Updated links. Quick and dirty translation of this solution: public static void main(String[] args) { List<List<String>> powerSet = new LinkedList<List<String>>(); for (int i = 1; i <= args.length; i++) powerSet.addAll(combination(Arrays.asList(args), i)); System.out.println(powerSet); } public static <T> List<List<T>> combination(List<T> values, … Read more
First, your code should have the condition of i <= n/2, otherwise it can miss one of the factors, for example 6 will not be printed if n=12. Run the loop to the square root of the number (ie. i <= sqrt(n)) and print both i and n/i (both will be multiples of n). { … Read more
You are making the Sieve of Eratosthenes much slower by making use of array manipulation functions such as Array#indexOf and Array#splice which runs in linear time. When you can have O(1) for both operations involved. Below is the Sieve of Eratosthenes following conventional programming practices: var eratosthenes = function(n) { // Eratosthenes algorithm to find … Read more
Geez, I’ll have to actually type it up from Knuth. This solution is by Joseph M. Morris [Inf. Proc. Letters 9 (1979), 197-200]. As far as I can tell, it runs in O(NlogN) time. static void VisitInO1Memory (Node root, Action<Node> preorderVisitor) { Node parent = root ; Node right = null ; Node curr ; while (parent != null) { curr … Read more
Here is a theoretical explanation And the algo in C: typedef struct { unsigned char r, g, b; } RGB; double ColourDistance(RGB e1, RGB e2) { long rmean = ( (long)e1.r + (long)e2.r ) / 2; long r = (long)e1.r – (long)e2.r; long g = (long)e1.g – (long)e2.g; long b = (long)e1.b – (long)e2.b; return … Read more
I’ll first give you the code and then explain it a bit: // direction vectors const int dx[] = {+1, 0, -1, 0}; const int dy[] = {0, +1, 0, -1}; // matrix dimensions int row_count; int col_count; // the input matrix int m[MAX][MAX]; // the labels, 0 means unlabeled int label[MAX][MAX]; void dfs(int x, … Read more