It works! In an earlier iteration of the Johnson algorithm, I had supposed that A was an adjacency matrix. Instead, it appears to represent an adjacency list. In that example, implemented below, the vertices {a, b, c} are numbered {0, 1, 2}, yielding the following circuits. Addendum: As noted in this proposed edit and helpful … Read more
Very interesting question. I wanted to implement this into mine 4D rendering engine as I was curious how would it look like but I was too lazy and incompetent to handle ND transcendent problems from the math side. Instead I come up with different solution to this problem. Its not a Fibonaci Latice !!! Instead … Read more
Breadth-first search traverses a graph and in fact finds all paths from a starting node. Usually, BFS doesn’t keep all paths, however. Instead, it updates a prededecessor function π to save the shortest path. You can easily modify the algorithm so that π(n) doesn’t only store one predecessor but a list of possible predecessors. Then … Read more
if (X1+W1<X2 or X2+W2<X1 or Y1+H1<Y2 or Y2+H2<Y1): Intersection = Empty else: Intersection = Not Empty If you have four coordinates – ((X,Y),(A,B)) and ((X1,Y1),(A1,B1)) – rather than two plus width and height, it would look like this: if (A<X1 or A1<X or B<Y1 or B1<Y): Intersection = Empty else: Intersection = Not Empty
This problem reduces to the 0-1 Knapsack Problem, where you are trying to find a set with an exact sum. The solution depends on the constraints, in the general case this problem is NP-Complete. However, if the maximum search sum (let’s call it S) is not too high, then you can solve the problem using … Read more
Dmitriy is right that you’ll want the Sieve of Atkin to generate the prime list but I don’t believe that takes care of the whole issue. Now that you have a list of primes you’ll need to see how many of those primes act as a divisor (and how often). Here’s some python for the … Read more
Choosing a random pivot minimizes the chance that you will encounter worst-case O(n2) performance (always choosing first or last would cause worst-case performance for nearly-sorted or nearly-reverse-sorted data). Choosing the middle element would also be acceptable in the majority of cases. Also, if you are implementing this yourself, there are versions of the algorithm that … Read more