[アルゴリズム]プログラマ-候補鍵

プログラマ-候補キー

説明する

from itertools import combinations

def is_minimum(key_comb, candidate_keys):
    for candidate_key in candidate_keys:
        if set(candidate_key).intersection(set(key_comb)) == set(candidate_key):
            return False
    return True


def is_unique(key_comb, transposed_relation):
    tmp_set = set()

    for j in range(len(transposed_relation[0])):
        tmp_list = []
        for i in key_comb:
            tmp_list.append(transposed_relation[i][j])

        if tuple(tmp_list) in tmp_set:
            return False
        tmp_set.add(tuple(tmp_list))
    return True


def solution(relation):
    transposed_relation = list(zip(*relation))

    columns = [i for i in range(len(transposed_relation))]
    keys = []
    for i in range(1, len(columns) + 1):
        keys.extend(list(combinations(columns, i)))

    candidate_keys = []

    for key_comb in keys:
        if not is_minimum(key_comb, candidate_keys):
            continue

        if is_unique(key_comb, transposed_relation):
            candidate_keys.append(key_comb)

    return len(candidate_keys)

print(solution([["100","ryan","music","2"],["200","apeach"

実はシフトする部分は必要ないのですが、1つ目の質問が間違っていたのでシフトの勉強をしたので放っておきました

他人を解く

from collections import deque
from itertools import combinations

def solution(relation):
    n_row = len(relation)
    n_col = len(relation[0])  

    candidates=[]
    for i in range(1,n_col+1):
        candidates.extend(combinations(range(n_col),i))

    final=[]
    for keys in candidates:
        tmp=[tuple([item[key] for key in keys]) for item in relation]
        if len(set(tmp))==n_row:
            final.append(keys)

    answer=set(final[:])
    for i in range(len(final)):
        for j in range(i+1,len(final)):
            if len(final[i])==len(set(final[i]).intersection(set(final[j]))):
                answer.discard(final[j])
                
    return len(answer)

候補:組み合わせにより任意の数の

を生成することができる.

final:可能な限り、一意性を確保

パターンで対応する値を抽出し、長さが正しいことを確認します.

例(100,200,...,600)の長さは6であり、一意性は

を満たす.

回答:最小性を満たす部分のみ抽出

交差点により、重複する変数が同じ元の変数

を有することを保証する.