Permutation Generation
Someone asked me how to generate all possible permutations out of a given set and I thought it was kind of interesting to think about it. I was able to come up with a general solution pretty easily (thanks to all the algorithm and math classes I took!) and I would like to share it with everyone.
Recursive solution
For a given set, S,
whereas + and - signs denote set addition and set subtraction respectively.
Python implementation
def permutation(set):
if set == []:
return [[]]
else:
r = []
for i in xrange(0, len(set)):
for p in permutation(set[0:i] + set[i+1:]):
r.append([set[i]] + p)
return r
Results
>>> print permutation([1, 2, 3])
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
I wouldn't say this particular implementation is the most efficient one, but at least we know it works with up to a certain size of set. Sadly, we all have machines with a finite size of memory, our machine will produce stack overflow if your set is too big.
I think languages like Haskell would work very efficiently with this kind of recursive solution due to its beautiful features like lazy evaluation, tail recursion, etc. Please feel free to share your solution or implementation.
Class Note for CS445 on Jan 27, 2009
Announcements
Optional discussion section meets on Wednesday, 7-8pm at FCS 101
Largest Empty Rectangle Problem
Divide and conquer
function DivideAndConquer(A, m, n) begin
PrecomputeLeftRuns(...)
PrecomputeRightRuns(...)
return DivAndConq(A, m, 1, n, L, R)
end
DevAndConq()
PrecomputeLeftRuns() + PrecomputeRightRus()
Total number of rectangles
[m 2] * [n 2] = m*(m-1)/2 * n*(n-1)/2
(pair of rows) (pair of cols) theta(m^2) theta(n^2)
To sum up, for Largest Empty Rectangle, we've seen following algorithms:
- Exhaustive search (
time) - [Optimized exhaustive search (
time)] - Divide and conquer (
time) - [Dynamic programming ( time)]
- [Amortization (
time)] (optimal)
Class Note for SC445 on Jan 20, 2009
Announcements
- Office hours posted on the course webpage: M-F
- Optional discussion section will be on Wednesdays at 7-8pm
Problem (Largest Monochromatic Rectangle)
Given an m*n boolean array A[1:m, 1:n] of zeroes and ones, find a subarray A[i:k, j:l] that contains only zeros.
Exhaustive Search (examine all possibilities; pick the best one)
function exhaustive(A, m, n) begin * returns the area of the largest solution
a := 0
for i := 1 to m do
for j := 1 to n do
for k := i to m do
for l := j to n do begin
scan A[i:k, j:l]
if it contains only zeroes then
a := max{a, (k-i+1)*(l-j+1)}
end (for)
return a
end (function)
- (a) scan - a := max{}
- (b) for l:= j to n
- (c) for k := i to m
- (d) for j := 1 to n
- (e) for i := 1 to m
Analysis
(a)
(b)
(c)
(d)
(e)
: time for exhaustive search without any optimization
Notations and Formulas
upper- and lower-bounded by constant times f(n) 
upper-bounded by constant times f(n) 
lower-bounded by constant times f(n)
(almost always)
Divide and Conquer
Cut the input array vertically at the middle column. Then the optimal rectangle falls into three cases:
- It lies strictly in left half. (recurse)
- It lies strictly in right half. (recurse)
- It spans the middle. (some work to do)
If we cut it at the middle column, it breaks into a left rectangle that ends at the middle column and is optimal, and a right rectangle that starts at the middle column and is optimal. (where the start and end rows i and k are fixed -> new subproblem!)