Python kth Hamming number (해밍 수)

해밍 수

Regular Number

@wikipedia

 

1. Hamming number

해밍 수란 인수가 2, 3, 5으로만 이루어진 수를 말한다.

그래서 5-smooth number, ugly number라고도 불린다.

 

한마디로, 아래 식을 만족하는 수

(다음 수들은 해밍 수이다. 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...)

$H = 2^i * 3^j * 5^k$, ($i, j, k >= 0$)

 

2. 파이썬

시간 복잡도: O(n), 결과를 바로바로 출력하면 공간 복잡도 O(1) 가능

프로그램: n 보다 작거나 같은 모든 해밍 수를 배열에 넣고 출력할 것이다.

n = 25
base = [2, 3, 5]

nums = [1]
append = nums.append  # tweak

candidates_indices = [0 for _ in base]
candidates = base[:]

while True:
    nextHN = min(candidates)
    if nextHN > n:
        break
    append(nextHN)

    for index, val in enumerate(candidates):
        if val == nextHN:
            candidates_indices[index] += 1
            candidates[index] = base[index] * nums[candidates_indices[index]]

print(nums)

# 결과 [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25]

 

설명

base = [2, 3, 5]  # 5 smooth number 만든다고 표시 (n-th smooth number 만들기 가능)

nums = [1]  # 결과 출력용 (1부터 시작)

candidates_indices(후보 인덱스) = [0, 0, 0]

candidates(후보) = [2, 3, 5]


영원히:
    nextHN = 후보 중 가장 작은 값 = 처음엔 2
    
    if nextHN이 n보다 크면: "종료"

    결과에 nextHN을 넣는다.



    enumerate(후보 배열) index와 value으로 for-loop

        if 후보 값이 이미 결과에 있는 값이면:

            후보_인덱스[index]은 1추가 (처음엔 후보_인덱스[0] = 1)

            후보[index] = base[index] * 결과[ 후보_인덱스[index] ] (처음엔 base[0] * nums[1] = 2 * 2)


''' candidates_indices는 아래와 같이 변함 (N = 25)
[0, 0, 0]
[1, 0, 0]
[1, 1, 0]
[2, 1, 0]
[2, 1, 1]
[3, 2, 1]
[4, 2, 1]
[4, 3, 1]
[5, 3, 2]
[6, 4, 2]
[6, 5, 3]
[7, 5, 3]
[8, 6, 3]
[9, 6, 4]
[10, 7, 4]
[10, 7, 5]
'''

''' candidates 배열은 아래와 같이 변함 (N = 25)
[2, 3, 5]
[4, 3, 5]
[4, 6, 5]
[6, 6, 5]
[6, 6, 10]
[8, 9, 10]
[10, 9, 10]
[10, 12, 10]
[12, 12, 15]
[16, 15, 15]
[16, 18, 20]
[18, 18, 20]
[20, 24, 20]
[24, 24, 25]
[30, 27, 25]
[30, 27, 30]
'''