In Ruby, the prime library gives you the factorization: require ‘prime’ 4800.prime_division #=> [[2, 6], [3, 1], [5, 2]] To get that list of yours, you take the cartesian product of the possible powers: require ‘prime’ def factors_of(number) primes, powers = number.prime_division.transpose exponents = powers.map{|i| (0..i).to_a} divisors = exponents.shift.product(*exponents).map do |powers| primes.zip(powers).map{|prime, power| prime ** … Read more
Be aware that there’s a small mistake in the explanation of the algorithm in the book, look in the errata for the text “(*) Page 297”. About your questions: No, the items don’t need to be sorted, only contiguous (that is, you can’t rearrange them) I believe the easiest way to visualize the algorithm is … Read more
Big-O Notation describes the limiting behavior when n is large, also known as asymptotic behavior. This is an approximation. (See http://en.wikipedia.org/wiki/Big_O_notation) Insertion sort is faster for small n because Quick Sort has extra overhead from the recursive function calls. Insertion sort is also more stable than Quick sort and requires less memory. This question describes … Read more
Just build one level at a time, e.g.: class Node(object): def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right def traverse(rootnode): thislevel = [rootnode] while thislevel: nextlevel = list() for n in thislevel: print n.value, if n.left: nextlevel.append(n.left) if n.right: nextlevel.append(n.right) print thislevel = nextlevel t = Node(1, Node(2, Node(4, … Read more
Given the position of an open parenthesis in an array of characters, there’s a simple algorithm that uses a counter to find the matching close parenthesis. Initialize a counter to 1. Loop forward (to the right) through the text. If another open parenthesis is encountered, increment the counter. If a closing parenthesis is encountered, decrement … Read more
Take another Bresenham loop and use it to modify the start and end position of original line in rectangular direction. Problem is to efficently find the right starting point and not to draw any pixel twice (or skip a pixel) while drawing next line. Working and tested C code is available from Github C code … Read more
Non-recursive merge sort works by considering window sizes of 1,2,4,8,16..2^n over the input array. For each window (‘k’ in code below), all adjacent pairs of windows are merged into a temporary space, then put back into the array. Here is my single function, C-based, non-recursive merge sort. Input and output are in ‘a’. Temporary storage … Read more
This article explains the basic implementation in length: The goal of this blog post is to show the fundamentals of A* through a really simple C# implementation. It also points to better implementations, more suitable for production use: As for ways to find better routes, there are plenty of C# examples around that are far … Read more
I actually did not realize there was a name for this, so I proved and implemented this from scratch: def random_subset(iterator, K): result = [] N = 0 for item in iterator: N += 1 if len(result) < K: result.append(item) else: s = int(random.random() * N) if s < K: result[s] = item return result … Read more
It will have to go through all the elements in the array to do this. Array is a unique data structure where you have to specify a size when you initialize it. Order would be the source array’s size or in Big O terms its O(length). Infact this happens internally in an ArrayList. ArrayList wraps … Read more