가능한 모든 n 요소 집합을 찾는 방법은 무엇입니까?

-1

k -elements 집합의 경우 가능한 모든 n -element 하위 집합 (n < k)을 찾아야합니다.가능한 모든 n 요소 집합을 찾는 방법은 무엇입니까?

이 문제는 어떻게 해결해야합니까?

그냥 도움이 될 것입니다. 감사합니다!

출처

2013-07-02 user1315305

라고'어떻게이 problem.' 접근해야 펜과 종이는 알고리즘을 생각할 때 가장 잘 작동합니다. –

@nickecarlo 정말 도움이 되셨습니다. 감사합니다 ... – user1315305

@ user1315305 잘못된 태그와 질문이 나에게도 일반적이기 때문에 질문이 있습니다. –

톱 코더의 알고리즘 자습서에서이 부분을 보았습니다. 어떻게 작동하는지 이해하십시오. 모든 K 개의 요소 서브 세트를 통해

대하여 반복 {0, 1, ... N-1}

int s = (1 << k) - 1; 
    while (!(s & 1 << N)) 
    { 
    // do stuff with s 
    int lo = s & ~(s - 1);  // lowest one bit 
    int lz = (s + lo) & ~s;  // lowest zero bit above lo 
    s |= lz;      // add lz to the set 
    s &= ~(lz - 1);    // reset bits below lz 
    s |= (lz/lo/2) - 1;  // put back right number of bits at end 
    }

출처

2013-07-02 21:11:04 Aravind

대개 매우 효율적이지만 비트 마술은 알고리즘 아이디어를 전달하기에 좋지 않은 방법입니다. –

@ G.Bach : 문제를 천천히 해결하는 알고리즘보다 신속하게 문제를 해결하는 알고리즘을 전달하는 것이 좋습니다. 특히 이해할 수 있도록 댓글을 달았습니다. 아니? – tmyklebu

@tmyklebu 물론, 더 나은 복잡성을 갖는 알고리즘이 바람직하며 주석이 도움이됩니다. 그러나이 코드가 무엇을 성취해야하는지 알지만, 나는 그것이 어떻게 작동하는지 이해하지 못합니다. –

Java에서 String ArrayList의 모든 조합 (또는 하위 집합)을 가져와야 할 때이 메서드를 사용했습니다.

public static List<List<String>> powerset(ArrayList<String> list) { 
     List<List<String>> ps = new ArrayList<List<String>>(); 
     ps.add(new ArrayList<String>()); 

     // for every item in the original list 
     for (String item : list) { 
      List<List<String>> newPs = new ArrayList<List<String>>(); 

      for (List<String> subset : ps) { 
       // copy all of the current powerset's subsets 
       newPs.add(subset); 

       // plus the subsets appended with the current item 
       List<String> newSubset = new ArrayList<String>(subset); 
       newSubset.add(item); 
       newPs.add(newSubset); 
      } 

      // powerset is now powerset of list.subList(0, list.indexOf(item)+1) 
      ps = newPs; 
     } 
     return ps; 
}

이것은 값 비싼 작업이며 상황에 맞는 완벽한 솔루션이 아닙니다. 그러나 솔루션을 신속하게 마련하려고한다면이 라인을 따라 뭔가를 할 것입니다. newSubset이 n보다 작 으면 원하는 하위 집합의 크기를 확인하고 보다 작은 경우 item 만 추가 할 수 있습니다. 그러면 n보다 큰 부분 집합이 생성되지 않습니다. 마지막으로 ps을 반복하고 n보다 작은 arraylist를 제거 할 수 있습니다. 다시 말하지만,이 솔루션은 완벽한 방법은 아닙니다. 그러나 트릭을해야합니다.

출처

2013-07-02 20:21:02 sunrize920

나는이 조합 접근법을 좋아하고, 그것이 당신이 건설하고있는 힘의 집합이라고 생각할 때, 나에게 그렇게 나쁘지 않게 보입니다. 그러나 작업이 고정 된 수의 요소로 서브 세트를 얻는 것만이라면 파워 세트를 구성하는 것이 기하 급수적으로 더 비쌉니다. –

@ sunrize920 감사합니다! – user1315305

아쉽게도 하위 집합 크기 = 21로 메모리가 부족하여 크기를 60으로 설정하여 좀 더 나은 솔루션을 찾아야합니다. – user1315305

구문 : 집합 A가 이하로 작성 10

보다 정수의 설정 :

A={0,1,2,3,4,5,6,7,8,9}

이 목록 또는 명부 방법

출처

2014-06-04 12:34:35 Chloe

가능한 모든 n 요소 집합을 찾는 방법은 무엇입니까?

답변

관련 문제