## All factors of a given number

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

## How to understand the dynamic programming solution in linear partitioning?

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

## Why is Insertion sort better than Quick sort for small list of elements?

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

## Printing BFS (Binary Tree) in Level Order with Specific Formatting

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

## How do I find the position of matching parentheses or braces in a given piece of text?

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

## how do I create a line of arbitrary thickness using Bresenham?

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

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

## How to implement an A* algorithm? [closed]

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

## Reservoir sampling

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

## Time complexity of System.arraycopy(…)?

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