cutting a rod

I studied cuttingrod dp alogorithm.

first cuttingrod is recursive function
and
cuttingRodDP is dynamic problem.

If we want to use by using recursive function
to speed up. we have to use memoized array

def cuttingRod(s, arr):

    m = arr[s-1]
    for i in range(1,int(s/2)+1):
        left=  i
        right =s-i
        val = cuttingRod(left, arr) + cuttingRod(right,arr)
        print(left, right, val)
        m= max(m, val )

    return m

def cuttingRodDP(s, arr):

    m = [0 for i in range(len(arr)+1)]
    for i in range(1, len(arr)+1):
        m[i]= arr[i-1]


    maxValue =0
    for i in range(1, len(arr)+1):
        for j in range(1,i+1):
           maxValue =  max(maxValue, m[j] + m[i-j])
        m[i] = maxValue
        print(m)

    return maxValue


arr= [ 1 ,  5,   8 ,  9 , 10,  17,  17,  20]
print(cuttingRod(len(arr), arr))

print(cuttingRodDP(len(arr), arr))

Largest palindromic subsequence in pyhton

# link site is http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/

def lps(str):
    n = len(str)

    L = [[0 for col in range(n)] for row in range(n)]

    for i in range(n):
        L[i][i] =1
    #count    for cl in range(2, n+1):
         for i in range(0, n-cl+1):
            j= i+cl-1
            if str[i] == str[j] and cl ==2 :
                L[i][j] =2            elif str[i] == str[j]:
                 L[i][j] = L[i+1][j-1] + 2            else :
                L[i][j] = max(L[i][j-1], L[i+1][j])
    print(L)
    return L[0][n-1];

print(lps("ABACAA"))

Minimum coin numbers

this is somehow easy dynamic problem.

this is my python code

coins = [1, 2, 5, 10, 20, 50, 100, 500, 1000]

def find(coins, target):

    list = [];
    for i in reversed(range(len(coins))):
         print(coins[i])
         while target>= coins[i]:
             target = target - coins[i]
             list.append(coins[i])

    return list

list = find(coins, 93 )
print(list)

huffman coding ( encoding and decoding) algorithm in python

this is short code written by python.

Huffman encoding and decoding

I studied using this site and write code 

http://www.geeksforgeeks.org/greedy-algorithms-set-3-huffman-coding/

import random

dic = {}
class MinHeapNode:
    def setNode(self, left, right, freq, char):
        self.left = left
        self.right = right
        self.freq = freq
        self.char = char
        return self
def huffmanCoding(arr, freq):
    heapArr = []

    for i in range(len(arr)):
        heapArr.append(MinHeapNode().setNode(None, None , freq[i], arr[i]))
        print(heapArr[i].freq, heapArr[i].char)

    while(len(heapArr)>1):
       left = heapArr.pop(0)
       right = heapArr.pop(0)
       insertionSort(heapArr, MinHeapNode().setNode(left, right, left.freq+right.freq, left.char + right.char))

    rootheap= heapArr.pop()

    return rootheap


def printHeap(heap, str):
    if heap.left != None:
        printHeap(heap.left, str + '0')

    if heap.right !=None:
        printHeap(heap.right, str + '1' )

    if heap.left == None:
        print(heap.char, str)
        dic[heap.char] = str

def insertionSort(heapArr, heap):
    index = len(heapArr)
    for i in range(len(heapArr)):
        if heap.freq < heapArr[i].freq:
           index  = i
           break
    heapArr.insert(index, heap)

def makeNewString(arr, freq):

    freqcopy = freq[:]
    arrcopy = arr[:]
    strval = ''
    while len(freqcopy) >0:
        number = random.randrange(0,len(freqcopy))
        freqcopy[number] = freqcopy[number]-1        strval = strval + arrcopy[number]
        if freqcopy[number] == 0:
            freqcopy.pop(number)
            arrcopy.pop(number)

    return strval

def endcoding(str):
    strval = ''    for i in range(len(str)):
        strval = strval + dic[str[i]]

    return strval

def huffmandecode(rootheap, strvalencoded):

    index = 0;
    orgstr = '';

    while index < len(strvalencoded):
        str = getchar(rootheap, index, strvalencoded)
        index = index + len(dic[str])
        orgstr = orgstr + str
    return orgstr

def getchar(rootheap, index, strvalencoded):
    if rootheap.left == None:
        return rootheap.char

    number = int(strvalencoded[index])
    if number ==0:
        return getchar(rootheap.left, index+1, strvalencoded)

    if number ==1:
        return getchar(rootheap.right, index+1, strvalencoded)

arr = ['a', 'b', 'c', 'd', 'e', 'f']
freq = [5, 9, 12, 13, 16, 45]
rootheap = huffmanCoding(arr, freq)

printHeap(rootheap, '')

strval  = makeNewString(arr, freq)
print("org     ", strval)

strvalencoded = endcoding(strval)
print("encoded ",strvalencoded)

orgencoded = huffmandecode(rootheap, strvalencoded)
print("decoded ", orgencoded)

python disjoint set (union find)

# make setdef MakeSet(number):
    return node().set(number)

# find rootdef find(x):
    if x.parent.number == x.number:
        return x
    else:
        return find(x.parent)

# merge two setsdef union(x, y):
    xRoot = find(x)
    yRoot = find(y)
    xRoot.parent = yRoot


class node():
    def set(self, number):
        self.parent = self        self.number = number
        return self
# make setsets = list(map(lambda x:MakeSet(x), range(10)))
for i in range(len(sets)):
    print(sets[i].number, sets[i].parent)

# one set is 0-4 super root is 4for i in range(0, 4):
    union(sets[i], sets[i+1])

# the otehr set is 5~9 super root is 9for i in range(5, len(sets)-1):
    union(sets[i], sets[i+1])

# test for all nodes finding root nodefor i in range(len(sets)):
    print(i ," parent -> ", find(sets[i]).number)

Combsort in python

this is combsort in python 

if you want to see detail of combsort 

refer this sites

https://en.wikipedia.org/wiki/Comb_sort

http://www.geeksforgeeks.org/comb-sort/

below is my python code

arr = [8, 4, 1, 56, 3, -44, 23, -6, 28, 0]

def combsort(arr):

    gap = len(arr)
    swapped = True
    while gap !=1 or swapped:
        gap= int(gap//1.3)
        if gap==0:
            gap =1
        swapped = False        for i in range(0, len(arr)-gap):
            if arr[i] > arr[i+gap]:
                swap(arr, i , i+gap)
                swapped = True                print(arr)

def swap(arr, i, j):
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp

combsort(arr)

print(arr)

shell sort in python

arr = [12, 34, 54, 2, 3]

def shellsort(arr):
    n = len(arr)
    gap = int(n/2)


    while gap > 0 :
        for i in range(gap, n):

            temp = arr[i]

            j = i
            while j>=gap and arr[j-gap] >temp:
                arr[j] = arr[j-gap]
                j-= gap

            arr[j] = temp
        gap//=2
shellsort(arr)
print(arr)

Bucket Sort in python

I make buckets as many as size of arr

and put data.

arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
def bucketSort(arr, size):
    buckets = [[] for i in range(size)]

    # put arr in bucket        

    for i in range(len(arr)):
        num = size*arr[i]
        buckets[int(num)].append(arr[i])

    output = []
    # use insertion sort        

    for i in range(len(buckets)):
        insertionSort(buckets[i])

    # concat all data        

    for i in range(len(buckets)):
        while len(buckets[i]) > 0:
            output.append(buckets[i].pop(0))

    return output


def swap(arr, i, j):
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp

def insertionSort(arr):
    for i in range(1, len(arr)):
        index= i
        print("index : " + str(i))
        while index!=0:
            if arr[index] < arr[index-1]:
                temp = arr[index]
                arr[index]= arr[index-1]
                arr[index-1] = temp
                index = index-1                print(arr)
            else :
                break
print(bucketSort(arr, len(arr)))

Count sort in Python

this is my python code for count sort

you can run

arr = [1, 4, 1, 2, 9, 5, 2]


def countSort(arr):
    #find max range    

    mval =0;
    for i in range(len(arr)):
        mval = max(mval, arr[i])

    # 배열 초기화    

    temp = [0]*(mval+1)
    output = [0]*(len(arr))

    # counting    

    for i in range(len(arr)):
        temp[arr[i]] =temp[arr[i]] + 1
    print(temp)
    

    # recounting    

    for i in range(1, len(temp)):
        temp[i]= temp[i-1] + temp[i]



    # counting sort    

    for i in range(len(arr)):
        output[temp[arr[i]] -1] =  arr[i]
        temp[arr[i]] = temp[arr[i]] -1
    print(temp)
    print(output)

countSort(arr)

Insertion Sort in Python.

Insertion sort is somehow difficult when I wrote code from only logic images

this is not optimized Insertion sort 

I will optimize and update sort code

arr = [5,2,3,7,1,4]

def swap(arr, i, j):
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp

def insertionSort(arr):
    for i in range(1, len(arr)):
        index= i
        print("index : " + str(i))
        while index!=0:
            if arr[index] < arr[index-1]:
                temp = arr[index]
                arr[index]= arr[index-1]
                arr[index-1] = temp
                index = index-1                print(arr)
            else :
                break
insertionSort(arr)
print(arr)

bubble Sort in Python

this is second weeks in algorithm study,

I want learn python and study basic algorithm.

this time I studied Bubble sort.

this time complexity is always O(N^2).

next time I will rewrite optimized Bubble sort  

arr =  [5, 1, 4, 2, 8]

def swap(arr, a, b):
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;

def bubblesort(arr):
    for i in range(len(arr)) :
        print( str(i+1) + " 번재 passing");
        for j in range(len(arr)-1):
            if arr[j] > arr[j+1] :
                swap(arr, j, j+1);
                print(arr)


bubblesort( arr);
print("result : ")
print(arr)

This is a selection sort algorithm

This time I attended algorithm study group using geeksforgeeks hompage.
this is just start and review algorithm basic.
I hope to study this steadily .

If you have question about selection sort. reply~!
time complexity O(n2)

arr = [5,2,3,7,1,4]
def selectionSort(arr):
    for i in range(len(arr)-1):
        print(i)
        minimum = arr[i]
        for j in range(i+1, len(arr)):
            if arr[j] < minimum:
                minimum = arr[j]
                swap(arr, i, j)
                print(arr);

def swap(arr, i, j):
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp

def selectionSortOnlyOneSwap(arr):
    for i in range(len(arr)-1):
        print(i)

        minimum = arr[i]
        minposition = i
        for j in range(i+1, len(arr)):
            if arr[j] < minimum:
                minimum = arr[j]
                minposition = j

        if minposition != i:
            swap(arr, i, minposition)

        print(arr)

selectionSort(arr)
print(arr)
print("only one time swap")

arr = [5,3,2,7,1,4]
print(arr)
selectionSortOnlyOneSwap(arr)

interesting def

Interesting  ~

>>> i =5
>>>
>>> def f(arg=i):
print(arg)

>>> i =7
>>> f()

guess what number??

the result is 5

List Type

I think Python is very simple to learn
simple to understand
simple to code...

there are many advantage if I use this language.

Now I start to learn list

Make List:
squares = [1,2,3,4,5]

Add List:
squares.append(6)

Copy List:
sqaures[:]

Range List:
sqaures[0:2]

Clear List:
sqaures = []

I started Just Python

My first Language was Java
Second is javascript,
third is c
fourth is Python which I'm trying to learn ~!

Compare to java.
this is amazing and very simple

ex)
>>> 3 * 'abc' + 'de'
'abcabcabcde'

>>> word = 'Python'
>>> word[0:2]
'Py'

Very Very Interesting..

I will use it more and more