2012-05-23 2 views
1

$ 0 ~ 2^(n + 1) -1 $의 고유 한 집합 $ A $이 주어 졌을 때. 이진 모드에서는 0-1 요소가있는 n 차원 벡터입니다. 이제 임의의 부분 집합 $ S $에 $ A $의 고유 번호가 포함되어 있으면 $ f (S) $가 $ 0,1, ..., m-1이되도록 함수 $ f $를 찾을 수 있습니까? $, $ f (A \ S) $는 $ 0,1, ..., m-1 $에 속하지 않아야합니다. 함수 $ f $는 가능한 한 단순해야하며 선형 함수가 바람직합니다. 감사.분류를위한 해시 함수

+2

우리는 당신의 숙제를하지 않을 것입니다. – Mustafa

+0

불행히도 그것은 hw가 아닙니다. 나는 우아한 기능의 존재에 대해서 궁금해하고 있습니다. – zhh210

+2

오케이, 그럼 뭐하려고 했니? – Mustafa

답변

1

당신이 찾고있는 키워드는 minimal perfect hash function이며, 예, 주어진 S에 대한 최소한의 완벽한 해시 함수를 구성 always possible입니다.

+0

고마워요. 이게 내가 원하는거야. – zhh210

+0

그리고이 "대답"은 논평입니다. 당신은 육체적으로 이것을 좀 더 충실하게 원할 것입니다. – casperOne