候補鍵(Programmers 42890)

🧑‍💻 候补基

フレンズ大学コンピュータ工学部助教のジェギーはニオ学部主任の指示で、学生の個人資料の整理を担当した.

は学部時代のプログラミング経験を回復し、すべての個人情報をデータベースに入れることにした.そのため、整理の過程で候補鍵(Candidate Key)を考慮する必要がある.

の候補鍵の内容をよく覚えていないJazzieは、正しい内容を把握するためにデータベース関連の書籍を見て、以下の内容を確認しました.

リレーショナル・データベースでは、発行版におけるTupleの属性(Attribute)または属性の集合のうち、以下の2つの性質を満たすものを候補キー(Candidate Key)と呼ぶことができる.

一意性(一意性):バージョン内のすべてのインスタンスについて、一意に識別する必要があります.

最小性(minimality):一意性鍵を構成する属性(Attribute)の1つを除外すると、一意性が破壊されることを示す.すなわち、バージョン内のすべてのインスタンスを一意に識別するために必要な属性のみから構成されます.

第

題のために、以下の学生の個人情報を与える際に、候補身長の最大個数を求める.

の上の例は、学生の個人情報バージョンにおいて、学生一人一人がそれぞれ唯一の「学号」を持っていることを示している.したがって、「学号」はバージョンの候補鍵になることができる.

以降、「名前」に対して同じ名前(「apeach」)を使用する学生がいるため、「名前」は候補鍵として使用できない.ただし、[名前](Name)と[プロフェッショナル](Professional)を同時に使用すると、バージョン内のすべての凡例が一意に認識されるため、候補鍵として使用できます.

もちろん,[[名前],[専門],[学年]]を併用してもバージョン内のすべてのチュートリアルを一意に認識することは可能であるが,最小性を満たすことはできないため候補キーにはならない.

従って、上記学生個人情報の候補鍵は、「学号」、「名称」、「専門」の2つである.パラメータとして

バージョンを表す文字列配列関係が与えられた場合、このバージョンの候補鍵の個数を返すために、ソルバが完了する.

せいげんじょうけん

関係は2 D文字列配列です.

関係のカラムの長さは1または8以下で、各カラムはバージョンのプロパティを表します.

関係のローの長さは1または20以下であり、各ローはバージョンのtupleを表す.

関係のすべての文字列の長さは1または8以下であり、アルファベットの小文字と数字のみから構成されています.

関係のすべての図例は唯一識別可能である.△つまり、繰り返しのアクセントがない.

I/O例
relationresult[["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]]2

🧑‍💻 解決策

は他の人のコードを運用した.

列を用いて組み合わせ、それを繰り返し検査すればよい.
このとき、繰り返しチェックは内蔵関数issubsetを使用します.

の候補キーリストの長さを返すと終わります!

🧑‍💻 コード#コード#

from itertools import combinations
def solution(relation):
   row = len(relation)
   col = len(relation[0])
   key_idx = list(range(col))
   candidtate_keys = []

   if row == 1 : return col

   for i in range(1, col + 1) :
       for comb in combinations(key_idx, i) :
           hist = []
           for re in relation :
               current_key = [re[c] for c in comb]
               if current_key in hist :
                   break
               else :
                   hist.append(current_key)
           else :
               for ck in candidtate_keys :
                   if set(ck).issubset(set(comb)) :
                       break
               else :
                   candidtate_keys.append(comb)

   return len(candidtate_keys)

🧑‍💻 総評

本当に触ることさえできません.

いつものように、答えを見て納得したので難しくないと思いましたが、この問題は本当に難しい・・・