재귀 적으로 하위 집합을 찾습니다.

Question

다음은 STL 집합에서 전달 된 모든 하위 집합을 찾는 재귀 함수입니다. 두 매개 변수는 대상을 검색하도록 설정된 STL이고 하위 집합의 크기를 지정하는 숫자 i> = 0입니다. 정수가 세트보다 크다면 빈 서브 세트를 반환하십시오.

나는 올바르게 이것을하고 있다고 생각하지 않습니다. 때로는 그것이 옳고 때로는 그렇지 않습니다. stl 세트는 잘 전달됩니다.

list<set<int> > findSub(set<int>& inset, int i) 
{ 
    list<set<int> > the_list; 

    list<set<int> >::iterator el = the_list.begin(); 
    if(inset.size()>i) 
    { 

     set<int> tmp_set; 
     for(int j(0); j<=i;j++) 
     { 
      set<int>::iterator first = inset.begin(); 
      tmp_set.insert(*(first)); 
      the_list.push_back(tmp_set); 
      inset.erase(first); 
     } 

     the_list.splice(el,findSub(inset,i)); 
    } 

    return the_list; 
} 

Answer 1

나는 실제로 주어진 세트에서 'i'요소의 모든 하위 집합을 생성하려고한다는 것을 알고 있습니까?

입력 세트를 수정하면 문제가 생길 수 있으므로 수정하지 않는 것이 좋습니다.

나는 그 생각이 아주 간단하다고 생각하지만, 당신은 그것을 거꾸로 가지고 있다고 말할 수 있습니다. 당신은 반복해야합니다으로

• 먼저 낮은 순위의 하위 집합을 생성 : 키 포인트는)

  generate_subsets(set, sizeOfSubsets) # I assume sizeOfSubsets cannot be negative 
              # use a type that enforces this for god's sake! 
      if sizeOfSubsets is 0 then return {} 
      else if sizeOfSubsets is 1 then 
      result = [] 
      for each element in set do result <- result + {element} 
      return result 
      else 
      result = [] 
      baseSubsets = generate_subsets(set, sizeOfSubsets - 1) 
      for each subset in baseSubssets 
       for each element in set 
       if no element in subset then result <- result + { subset + element } 
      return result 
  

  를, 그것은 숙제처럼 보이는 때문에, 나는 당신에게 C++ 알고리즘을 제공하지 않습니다 이미있는 경우 그들을

• 이 부분 집합의 요소를 삽입하려고하지 마십시오, 당신이 이해를해야하고 '에 트랜스거야,

지금 당신에게 잘못된 크기의 부분 집합을 줄 것이다 진짜 '코드.

Answer 2

나는 몇 분 동안이 응시 한 나는 생각의 기차가이 것 일을 생각하기위한 무엇인지 알아낼 수 없습니다. 참여할 수있는 모든 가능한 하위 집합을 탐색하기 전에 입력 목록의 여러 구성원을 영구히 제거하고 있습니다.

의사 코드로하려는 솔루션을 시도하고 stl 간섭없이 문제를 볼 수 있는지 확인하십시오.

Answer 3

나는 또한 이것이 성취하기로되어있는 것을 볼 수 없습니다.

특정 제한이있는 숙제가 아닌 경우 임시 std::set (std::includes())을 테스트 해 보시기 바랍니다.

Answer 4

당신이 할 수있는 일은 모든 파워 세트 (모든 서브 세트 세트)를 계산 한 다음 그 세트에서 조건을 충족하는 서브 세트 만 선택하는 것입니다.

Wikipedia Power set page 및 Math Is Fun에 대한 계산 방법을 찾을 수 있습니다. (위 링크는 외부 링크 섹션에 있으며 Power Set in Math는 재미 있고 스팸 방지 메커니즘으로 직접 게시 할 수 없습니다) . 수학에 재미는 주로 섹션 바이너리.