[PRODrammers]候補鍵/python

質問する

候補キー

フレンズ大学コンピュータ工学部の助教として、ジェギーはニオ学部主任の指示で、学生の個人資料の整理を担当した.
彼は本科でプログラミングの経験を回復し、すべての個人情報をデータベースに入れることにした.そのため、整理の過程で候補鍵(Candidate Key)を考慮する必要がある.
候補鍵の内容をよく覚えていないJazzyは、正しい内容を把握するために、データベース関連の書籍を見て、以下の内容を確認しました.

リレーショナル・データベースでは、発行版におけるTupleの属性(Attribute)または属性の集合のうち、以下の2つの性質を満たすものを候補キー(Candidate Key)と呼ぶことができる.
-一意性(一意性):リリース内のすべての凡例を一意に識別する必要があります.
-最小性(minimality):一意性を有する鍵を構成する属性(Attribute)の1つを除外すると、一意性が破壊されることを示す.すなわち、バージョン内のすべてのインスタンスを一意に識別するために必要な属性のみから構成されます.

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

上記の例では、学生の個人情報バージョンでは、学生ごとに独自の学号があります.したがって、学号はバージョンの候補鍵になることができる.
次の名前に同じ名前(apeach)を使う学生もいるので、名前は候補鍵として使用できません.ただし、[名前、プロフェッショナル]を同時に使用すると、バージョン内のすべての凡例が一意に認識されるため、候補キーになることができます.
もちろん、「名前、専攻、学年」とともに使用してもバージョン内のすべてのパターンを一意に認識できるが、最小性を満たすことはできないため、候補キーにはならない.
そのため、上記の学生の個人資料の候補身長は2つあります:学号、専門.
バージョンを表す文字列配列関係をパラメータとして指定する場合は、このバージョンの候補鍵の数を返すために、ソルバを完了します.

せいげんじょうけん

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

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

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

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

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

🤔 の意見を打診

初めて見たときは,コンビネーションジェネレータを連続的に呼び出して部分集合を作成し,一意性の最小性を比較すればよい.

論理がないわけではないでも….

最小チェック部分では、コードが少し窮屈になる可能性があります.

コレクションの長さを比較し続ける可能性があり、時間の複雑さが面倒になります.

考えてみれば、これは最終的に局所集合を求める問題ではないか.비트마스킹で直接集合を整数型に表すとしたら?時間の複雑さだけでなく、メモリも大幅に節約できます.
最小チェックも簡単なAND演算で終わります.비트마스킹で解きましょう!

📌 説明する

def checkuniq(arr, row):
    return True if len(set(zip(*arr))) == row else False
    
    
def checkmin(num, unique):
    for i in unique:
        if i & num == i: return False
    return True


def solution(relation):
    relation = tuple(zip(*relation))
    col = len(relation)
    row = len(relation[0])
    candidate = []
    
    for num in range(1, 1 << col):
        tmp = tuple(relation[i] for i in range(col) if num & (1 << i))
                
        if checkuniq(tmp, row) and checkmin(num, candidate):
            candidate.append(num)
            
    return len(candidate)

レビュー

最初はちょっと難しいと思いました.

しかし、この整数を一つの部分集合として表現する習慣を身につけると、それは簡単です!

の部分集合を表す場合、下位マスクを考慮する.