1
그래서 집합의 powerset을 각 요소의 고유 번호 (색인)에 매핑 한 다음이 번호를 지도 또는 목록의 비 고유 값 모든 하위 집합을 명시 적으로 저장하지 않아도되지만 고유 한 번호 만 저장하면됩니다. 선형 시간 (바람직하게는, 그러나 필요하다면 더 높은 차수의 다항식을 제공 할 수 있다고 가정) 알고리즘은 부분 집합의 요소로부터 고유하게 숫자를 생성합니다. 직감으로 볼 때, 서브 세트의 요소에 대한 합산 또는 컨볼 루션 함수를 사용하여 그러한 알고리즘이 존재할 수 있다고 생각합니다.집합을 고유 번호로 인코딩하는 빠른 알고리즘
공식적인 용어로, 나는 모든 하위 집합이 필요한 우주 U = {1,2,3,...,n}이 있습니다. 이러한 하위 집합은 2^n입니다. 함수 fX 하위 숫자 y, 즉 f(X)=y에 매핑 기능이 있습니다. y은 고유하지 않은 숫자입니다.
이제 좀 k ϵ X 또 다른 하위 집합 한 집합에서 Y 값 Y = X - {k}을 X 값을 이동할 수 있도록 내 프로그램이 필요합니다. 그렇다면 해당 요소에서 Y의 고유 식별자를 계산할 수있는 알고리즘이 있다면 k을 제거하고 X의 (나머지) 요소를 사용하여 저장된 하위 집합 목록을 검색하는 대신 검색해야합니다. 검색 및 각 하위 집합을 저장하는 메모리 비용을 비교해야합니다.
그런 알고리즘이 있는지 누가 알 수 있습니까?
질문을 명확하게 할 수 있습니까? 마지막 단락이 아닙니다. – banarun
질문을 명확히하려는 시도에 감사드립니다.하지만 불행히도 여전히 이해가되지 않습니다. 예를 들어 설명 할 수 있습니까? 마지막 예는 이해하기가 어렵습니다. – Aravind
표준 접근 방식은 다음과 같습니다. 바이너리 숫자를 사용하여 세트를 나타냅니다. 예를 들어 이진수 00001011은 U에서 첫 번째, 두 번째 및 네 번째 요소를 포함하는 집합을 나타냅니다. –