Skip to content

Instantly share code, notes, and snippets.

@kflu
kflu / PrintParenthesis.py
Created June 26, 2012 16:53
Printing all possible permutations of valid parenthesis pairs
class PrintParenth:
def __init__(self, n):
self.n = n
self.s = [None for i in range(2*n)]
def P(self, l, r):
if l==self.n and r==self.n:
yield ''.join(self.s)
if l < self.n:
self.s[l+r] = '('
@kflu
kflu / strperm.py
Created June 27, 2012 01:07
Calculate all string permutation
def strperm(S):
if not S: yield ""
for c in S:
for perm in strperm(S - set([c])):
yield c + perm
for s in strperm(set("abcd")):
print s
@kflu
kflu / n_choose_k.py
Created June 27, 2012 02:15
n choose k
def C(S,k):
'''Choose k elements from set S.'''
assert len(S) >= k
if k==0:
yield set()
S1 = S.copy()
for s in S:
S1.remove(s)
if len(S1) >= k-1:
for c in C(S1, k-1):
@kflu
kflu / Qsort.cs
Created July 6, 2012 00:25
Quick Sort in C#
using System;
using System.Collections.Generic;
namespace ConsoleApplication14
{
class Program
{
static void Main(string[] args)
{
var A = new int[] { 4, 3, 5, 2 };
@kflu
kflu / qsort.py
Created July 6, 2012 00:34
Quick sort in Python (with tests)
class QSort:
def __init__(self, A):
self.A = A
def partition(self, L, U):
s = U
p = L
while s != p:
if self.A[p] <= self.A[s]:
p += 1
else:
@kflu
kflu / SortedMatrix.cs
Created July 8, 2012 22:17
Find a value in a sorted matrix
using System;
using System.Diagnostics;
using System.Collections.Generic;
namespace ConsoleApplication4
{
/// <summary>
///
/// </summary>
/// <remarks>
@kflu
kflu / FindLongestPalindrome.cs
Created July 11, 2012 00:34
find longest palindrome
using System.Text;
using System;
using System.Diagnostics;
namespace ConsoleApplication15
{
class Program
{
static void Main(string[] args)
{
@kflu
kflu / MyQueue.cs
Created August 2, 2012 03:13
Using stacks to implement a Queue.
using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace ConsoleApplication7
{
class Program
{
static void Main(string[] args)
{
@kflu
kflu / CheckTreeBalance.cs
Last active October 7, 2015 22:24
Check if a binary tree is balance, i.e., all leaf nodes are on levels which difference does not exceed 1.
// Deprecated in favor of https://github.com/puzzl3r/puzzles/tree/master/CheckTreeBalance
using System.Diagnostics;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication8
{
@kflu
kflu / find_path.py
Created August 2, 2012 05:58
Finding path between two nodes in a directed graph using BFS.
from Queue import Queue
def find_path(E, V, n1, n2):
"""Find path between n1,n2 of a directed graph"""
for n in E:
n.from_ = None
q = Queue()
q.put(n1)
found = False
while not q.empty():