문자열 포함 관련 함수

# forbidden에 해당하는 문자를 포함하지 않았는가
# word가 letter(forbidden의 문자)를 하나라도 포함하면 False
def avoids(word,forbidden):
    for letter in forbidden:
        if letter in word:
            return False
    return True

avoids('sh','shit') # False

# available에 해당하는 문자만 포함하는가
# available이 letter(word의 문자)를 하나라도 포함 안 하면 False
def uses_only(word,available):
    for letter in word:
        if letter not in available:
            return False
    return True

uses_only('hi','hi_hello') # True

# required에 해당하는 문자열을 모두 포함하는가 
# word가 letter(required의 문자)를 하나라도 포함 안 하면 False
def uses_all(word,required):
    for letter in required:
        if letter not in word:
            return False
    return True

uses_all('hi_hello','hello') # True

enumerate 함수

(인덱스,값)조합으로 튜플을 만들고 이러한 튜플들을 저장하는 zip을 만듦

for index,element in enumerate('abc'):
    print(index,element)

중복된 원소가 있는지 찾기

def has_duplicates_set(t):
    s=set(t)
    if(len(s)<len(t)):
        return True
    else:
        return False

has_duplicates_set([1,2,3,1])

def has_duplicates_dict(t):
    d=dict()
    for i in t:
        d[i]=d.get(i,0)+1
    if(len(d)<len(t)):
        return True
    else:
        return False

has_duplicates_dict([1,2,3,1])

생일 문제

n명의 사람들 중 적어도 두 사람의 생일이 같을 확률

import random

iteration=1000
n=23
freq=0

# iteration번 시행
for itr in range(iteration):
    birth=set()
    # 생일 추가 - 생일 검색
    for i in range(n):
        new=random.randint(1,365)
        # (새로운 생일이 온건지 검사), 같은 것이 있으면 다음 시행 진행
        if(new in birth):
            freq+=1
            break
        birth.add(new)
print(freq/iteration)

문자의 빈도수를 딕셔너리에 저장하기

# 키로 정렬
def f1(x):
    return x[0]
# 값으로 정렬
def f2(x):
    return x[1]

def most_frequent(str):
    d=dict()
    for c in str:
        d[c]=d.get(c,0)+1
    d=sorted(d.items(),key=f2,reverse=True)
    for d_one in d:
        print(d_one,end='')
    print()

most_frequent('aabbbcccdddd')

이분탐색으로 사전에 담긴 단어의 인덱스 찾기

def in_bisect(list,str):
    low=0; high=len(list)-1;
    while(low<=high):
        mid=(low+high)//2
        comp=list[mid].strip()
        if(comp==str):
            return mid
        elif(comp<str):
            low=mid+1
        else:
            high=mid-1
    if(low>high):
        return None

f=open('words.txt')
list=[]
for x in f:
    list.append(x)

list.sort()
in_bisect(list,'zone')

텍스트 파일을 읽어서 단어 빈도수 함수 그리기

import string
import numpy as np
import matplotlib.pyplot as plt

def process_file(filename):
    hist = dict()
    fin = open(filename)
    for line in fin:
        process_line(line, hist)
    return hist

def process_line(line, hist):
    line = line.replace('-', ' ')
    for word in line.split():
        word = word.strip(string.punctuation + string.whitespace)
        word = word.lower()
        if len(word) > 0:
            hist[word] = hist.get(word, 0) + 1

def f2(x):
    return x[1]

hist = process_file('emma-a.txt')
h=sorted(hist.items(),key=f2,reverse=True)

ranks=[]
freqs=[]

rank=0
for w,f in h:
    freqs.append(f)
    rank+=1
    ranks.append(rank)

freqs=np.array(freqs)
ranks=np.array(ranks)

logf=np.log(freqs)
logr=np.log(ranks)

plt.xlabel('rank')
plt.ylabel('freq')
plt.plot(logr,logf)
plt.show()

행렬 계산 문제

def matadd(A,B):
    m=len(A)
    n=len(A[0])
    p=len(B)
    q=len(B[0])
    
    if m!=p or n!=q:
        raise Exception("Not Same size")
    
    mat=[]
    for i in range(m):
        row=[0]*n
        for j in range(n):
            row[j]=A[i][j]+B[i][j]
        mat.append(row)
    return mat

def matmul(A,B):
    m=len(A)
    n=len(A[0])
    p=len(B)
    q=len(B[0])
    
    if n!=p:
        raise Exception("Not Match")
        
    mat=[]
    for i in range(m):
        row=[0]*q
        for j in range(q):
            for k in range(n):
                row[j]+=A[i][k]*B[k][j]
        mat.append(row)
    return mat

def matpower(A,k):
    if k==1:
        return A[:]
    
    res=A[:]
    for i in range(1,k):
        res=matmul(A,res)
    return res

A=[[1,2],[-1,2]]
sum=A[:]
for i in range(2,17):
    B=matpower(A,i)
    sum=matadd(sum,B)
print(sum)

순열 나열

def permute(l,k):
    if k<=0 or k>len(l):
        return []
    if k==1:
        ones=[]
        for i in l:
            ones.append([i])
        return ones
    list=[]
    for i in range(len(l)):
        l2=l[:i]+l[i+1:]
        sub=permute(l2,k-1)
        for part in sub:
            list.append([l[i]]+part)
    return list

permute([1,2,3,4],3)

조합 나열

def choose(l,k):
    if k<=0 or k>len(l):
        return []
    if k==1:
        ones=[]
        for i in l:
            ones.append([i])
        return ones
    list=[]
    for i in range(len(l)):
        l2=l[i+1:]
        sub=choose(l2,k-1)
        for part in sub:
            list.append([l[i]]+part)
    return list

choose([1,2,3,4],3)

자연수의 분할 나열

def partition_number(n,k,ub=None):
    if k<=0 or k>n:
        return []
    if k==1:
        return [[n]]
    l=n-k+1 ## upper bound of the largest number
    if ub != None and ub<l:
        l=ub
    s=n//k ## lower bound of the largest number
    if n%k > 0:
        s += 1
    list=[]
    for i in range(l,s-1,-1):
        sub=partition_number(n-i,k-1,i)
        for j in sub:
            list.append([i]+j)
    return list

# 5를 3개의 자연수로 분할하는 모든 경우
partition_number(5,3)

# 5를 3개의 자연수로 분할하되 각각의 자연수가 2이하가 되도록 표현
partition_number(5,3,2)

집합의 분할 나열

def partition_set(A, k = None):
    n = len(A)
    if k == None:
        res = []
        for i in range(n):
            res.extend(partition_set(A, i + 1))
        return res
    if k <= 0 or k > n:
        return []
    if k == 1:
        return [[A[:]]]
    res = []
    a = A[0]
    A2 = A[1:]
    sub = partition_set(A2, k - 1)
    for part in sub:
        res.append([[a]] + part)
        sub = partition_set(A2, k)
    for part in sub:
        for i in range(len(part)):
            res.append(part[:i] + [part[i] + [a]] + part[i+1:])
    return res

partition_set([1,2,3,4],3)