Implementation for greedy algorithms

activity_selection.py

#! usr/local/bin python3

def activity_selection(start, finish):
	"""
	activity selection problem
	start: start time of activities
	finish: finish time of activities
	return: selected activities
	"""
	n=len(start)
	if n==0:
		return []
	result=[0]
	j=0
	for i in range(1,n):
		if start[i]>=finish[j]:
			result.append(i)
			j=i
	return result

def activity_selection_dp(start, finish):
	"""
	activity selection problem with dynamic programming
	start: start tie of activities
	finish: finish time of activities
	return: selected activities
	"""
	n=len(start)
	if n==0:
		return []
	dp=[[0 for _ in range(n)] for _ in range(n)]
	for i in range(n):
		dp[i][i]=1
	for l in range(2,n+1):
		for i in range(n-l+1):
			j=i+l-1
			if finish[i]<=start[j]:
				dp[i][j]=dp[i+1][j-1]+2
			else:
				dp[i][j]=max(dp[i+1][j], dp[i][j-1])
	return dp[0][n-1]
	
def huffman_encoding(data):
	"""
	huffman encoding
	data: data to be encoded
	return: encoded data
	"""
	if len(data)==0:
		return ''
	freq={}
	for char in data:
		if char not in freq:
			freq[char]=0
		freq[char]+=1
	freq=sorted(freq.items(), key=lambda x:x[1], reverse=True)
	while len(freq)>1:
		char1, freq1=freq.pop()
		char2, freq2=freq.pop()
		freq.append((char1+char2,freq1+freq2))
		freq=sorted(freq,key=lambda x:x[1], reverse=True)
	char, _=freq[0]
	code={}
	for i in range(len(char)):
		code[char[i]]=str(bin(i))[2:]
	result=''
	for char in data:
		result+=code[char]
	return result

# test case
print(activity_selection([1, 3, 0, 5, 8, 5], [2, 4, 6, 7, 9, 9]))
print(activity_selection_dp([1, 3, 0, 5, 8, 5], [2, 4, 6, 7, 9, 9]))
print(huffman_encoding('aaabbc'))