검색 트리 순서가 중요하지 않은 곳 [recepies]

항목의 순서가 중요하지 않은 항목의 k 목록을 통해 필터링 할 수있는 알려진 알고리즘이 있는지 궁금합니다. 예를 들어검색 트리 순서가 중요하지 않은 곳 [recepies]

는 말은 치킨 샐러드

X1 + X2 + X3 + ... +

chicken+onions+mushroom+lettuce = chicken salad 
onions+mushrooms+lettuce+chicken = chicken salad 
mushrooms+lettuce+chicken+onions = chicken salad 
lettuce+mushrooms+onions+chicken = chicken salad 
chicken+mushrooms+onions+lettuce = chicken salad

그래서 기본적으로 치킨 샐러드 재료로 요리 할 수 XK = y를 만드는 recepies 수십가 할 수 있습니다 순서는 중요하지 않습니다. 그래서 그 구성 요소 (성분)가 Set1 (치킨 샐러드)을 만들었다 고 가정하면 그 구성 요소를 세트와 일치시킬 수있는 알고리즘이 있습니까? 그 재료가 다른 세트 (즉, 양파 + 버섯 + 상추 + 참치 = 참치 샐러드)의 일부일 수있는 곳. 또한 닭고기 + 닭고기 + 버섯 + 양파 + 상추 = 디럭스 치킨 샐러드의 양을 다르게 할 수 있다고 덧붙여 야합니다.

if 문장을로드하고 O (n) 검색을 수행 할 수 있습니다. 여기서 n 세트의 수는 있지만이 문제를 해결하는 데 도움이되는 효율적인 알고리즘 () (구조화 된 알고리즘)이 있는지 궁금합니다.

감사

출처

2012-03-10 Saad

그냥 명확히하기 위해 재료 목록을 작성하고 생산할 수있는 요리법을 제출 하시겠습니까? – cjm

그렇습니다. 버섯 + 양파 + 닭 + 상추 또는 양상추 = 양파 + 버섯 + 상추 + 닭고기 + 닭 + 버섯 + 양파 + 상추 등 닭고기 샐러드가 생깁니다. – Saad

순으로 예를 정렬 성분에 대한 설정에 약간의 순서를 정의합니다.
이 정렬 된 세트를 데이터베이스 테이블 또는 해시 테이블의 키로 사용하십시오.
완료.

출처

2012-03-10 05:26:38 actual

1-n, 1 = 계란, 2 = 닭고기 등 1-n 테이블 여러 항목을 하나의 항목 (예 : 1 + 2 + 5 = 달걀 샐러드)과 동일하게 만드는 문제를 해결하는 방법은 무엇입니까 – Saad

아마도 원래의 질문을 오해 할 수 있습니다. . 특정 하위 세트 (성분)의 모든 하위 세트 (레시피)를 찾아야합니까, 아니면 세트 (성분)가 주어진 데이터베이스 (단일 레시피)와 정확히 일치하는 세트를 찾아야합니까? – actual

설명을 업데이트 했으므로 더 명확하게 알 수 있습니다. 후자는 정확히 하나의 레서피와 동일한 재료를 사용하고 싶습니다. – Saad

짧은 답변 : 사용 비트 세트 및 해시.

답은입니다. 재료의 정수는 64입니다. 각 문자열을 0..63 사이의 정수 색인 (즉, 양파 -> 0, 치즈 -> 1, 버섯 - > 2 등. 재료 목록을 보면 각 색인을 부호없는 64 비트 정수로 매핑합니다. 즉, 양파는 64 비트 숫자 만 0 비트로 설정되고, 치즈는 64 비트 숫자가 1 비트만 설정되고, 버섯은 2 비트로 설정됩니다. 주어진 성분 세트가 주어지면 해당 UInt64를 합하여 하나의 UInt64를 갖습니다. 예를 들어, 세트 양파 + 버섯 < 접시를 나열하는 UINT64에서 해시 (사전) 구축 1 + 4 = 5에 대응 > 예 5 -> "GrilledMushroomsWithOnion"최고의 전략의 상대적 크기에 의존 할 것이다

출처

2012-03-10 08:27:35

자바에서이 작업을 수행하고 5xonions = 5 인 경우이 논리를 사용하십시오! "GrilledMushromsWithOnions" – Saad

내 솔루션은 Java 및 기타 현대 언어에서 작동하며 문제는 무엇입니까? 해시는'HashMap' 또는'HashTable' 또는 Java와 비슷한 것으로 기억하지 않습니다. 그 정확한 이름을 조회 할 수 있어야합니다. BitSet은 Java에서 정확한 이름이지만 사용하지 않아도됩니다. 테이블 양배추가 13 이상인 경우 1 << 13을 계산하고 재료를 합칠 수 있습니다. Java에서 부호없는 값이 부족하다는 점을 염두에두면 중요하지 않습니다. –

'내가 5xonions = 5! = "GrilledMushromsWithOnions"'Aah 인 경우 각 구성 요소를 두 번 이상 추가하여 다른 세트를 생성 할 수 있습니다. 너는 그 질문에 그 말을 했어야했다. –

수색의 재료 수 (k라고 부름)와 조리법의 수 (n) 대 다른 가능한 재료의 수.

가장 간단한 전략은 집합에 해시 함수를 정의하는 것입니다. 즉, 순서를 신경 쓰지 않는 해시 함수입니다. 요소에 적용되는 모든 교환 작업이이를 위해 작동합니다. 또한 목록을 해싱하는 것보다 정렬이 효과적입니다. 이렇게하면 모든 요리법을 연관 컨테이너에 저장하고 특정 재료를 검색 할 수 있습니다. 빠른 해시 함수를 사용하면 충분한 검색을 수행 할 경우 O (k) 검색 및 초기 초기 설정 비용을 상각 해 버립니다.

이 방법의 문제점은 찾고있는 재료의 하위 세트 만 가지고있는 조리법을 찾지 못한다는 것입니다. 하나의 옵션은 재료의 각 하위 집합에 대해이 알고리즘을 개별적으로 실행하는 것이지만 O (2^k)로 안내합니다.

또한 비용 모델에 따라 다릅니다. 마운틴 뷰에서 특정 회사처럼 작동하고 효과적으로 무한한 수의 프로세서를 유지하면서 실시간에 가까운 응답을 생성하려는 경우 각 레서피가 병렬로 가능한지 단순히 확인하는 것이 합리적 일 수 있습니다. 이것은 (각 레서피에 대해) 매우 신속하게 이루어질 수 있으며, 실제로 레시피가 당신의리스트에서 사용한 재료의 수를 돌려 주도록 쉽게 확장 될 수있어, 당신이 주문을 할 수있게 해줍니다.

출처

2012-03-10 09:31:03

검색 트리 순서가 중요하지 않은 곳 [recepies]

답변

관련 문제