조합 관련 질문

망치의 이미지

다음 두가지 조합에서 8C5 의 조합분을 모두 포함 할 수 있는 8C6 조합 몇가지를 추려내고 싶습니다.
예를들면 8C5 의 조합 (1,2,3,4,5) (1,2,3,4,6) (1,2,3,5,6) (1,2,4,5,6) (1,3,4,5,6) (2,3,4,5,6) 를 8C6 의 조합 (1,2,3,4,5,6) 이면 모두 포함하는것처럼요.

수학공부를 안해놔서 이런경우 어떻게 간단하게 추려낼 방법을 모르겠습니다.. 아래처럼 수가 얼마 안되면 모르겠는데 양아 많아질경우는 난감해서요..

(8C6)
0 : 1 2 3 4 5 6
1 : 1 2 3 4 5 7
2 : 1 2 3 4 6 7
3 : 1 2 3 5 6 7
4 : 1 2 4 5 6 7
5 : 1 3 4 5 6 7
6 : 2 3 4 5 6 7
7 : 1 2 3 4 5 8
8 : 1 2 3 4 6 8
9 : 1 2 3 5 6 8
10 : 1 2 4 5 6 8
11 : 1 3 4 5 6 8
12 : 2 3 4 5 6 8
13 : 1 2 3 4 7 8
14 : 1 2 3 5 7 8
15 : 1 2 4 5 7 8
16 : 1 3 4 5 7 8
17 : 2 3 4 5 7 8
18 : 1 2 3 6 7 8
19 : 1 2 4 6 7 8
20 : 1 3 4 6 7 8
21 : 2 3 4 6 7 8
22 : 1 2 5 6 7 8
23 : 1 3 5 6 7 8
24 : 2 3 5 6 7 8
25 : 1 4 5 6 7 8
26 : 2 4 5 6 7 8
27 : 3 4 5 6 7 8

(8C5)
0 : 1 2 3 4 5
1 : 1 2 3 4 6
2 : 1 2 3 5 6
3 : 1 2 4 5 6
4 : 1 3 4 5 6
5 : 2 3 4 5 6
6 : 1 2 3 4 7
7 : 1 2 3 5 7
8 : 1 2 4 5 7
9 : 1 3 4 5 7
10 : 2 3 4 5 7
11 : 1 2 3 6 7
12 : 1 2 4 6 7
13 : 1 3 4 6 7
14 : 2 3 4 6 7
15 : 1 2 5 6 7
16 : 1 3 5 6 7
17 : 2 3 5 6 7
18 : 1 4 5 6 7
19 : 2 4 5 6 7
20 : 3 4 5 6 7
21 : 1 2 3 4 8
22 : 1 2 3 5 8
23 : 1 2 4 5 8
24 : 1 3 4 5 8
25 : 2 3 4 5 8
26 : 1 2 3 6 8
27 : 1 2 4 6 8
28 : 1 3 4 6 8
29 : 2 3 4 6 8
30 : 1 2 5 6 8
31 : 1 3 5 6 8
32 : 2 3 5 6 8
33 : 1 4 5 6 8
34 : 2 4 5 6 8
35 : 3 4 5 6 8
36 : 1 2 3 7 8
37 : 1 2 4 7 8
38 : 1 3 4 7 8
39 : 2 3 4 7 8
40 : 1 2 5 7 8
41 : 1 3 5 7 8
42 : 2 3 5 7 8
43 : 1 4 5 7 8
44 : 2 4 5 7 8
45 : 3 4 5 7 8
46 : 1 2 6 7 8
47 : 1 3 6 7 8
48 : 2 3 6 7 8
49 : 1 4 6 7 8
50 : 2 4 6 7 8
51 : 3 4 6 7 8
52 : 1 5 6 7 8
53 : 2 5 6 7 8
54 : 3 5 6 7 8
55 : 4 5 6 7 8

ifree의 이미지

어렵군요.
일단 답은 여러 경우가 나올 것 같은데.

phonon의 이미지

(8C6)를 마스터
(8C5)를 일반

숫자나 문자로 비교한다면 시간이 많이 걸릴겁니다.
일단, 마스터 데이터의 자릿값을 정하지요.
1,2,3,4,5,6,7,8로 최고값을 8로 합니다.
이것을 비트로 바꾸어 봅니다.
(8C6)의 0 : 1 2 3 4 5 6 --> 11111100
(8C5)의 0 : 1 2 3 4 5 --> 11111000
마스터데이터와 일반데이터를 비트연산(&)를 하면,
11111100 & 11111000 = 11111000
원래 일반데이터와 동일한 값이 나옵니다. 그러면 마스터데이터의 부분집합임을 알 수 있겠지요.

STL나 bitfield를 이용하는 것은 개발자의 취향대로 하시면 되겠지요.
다른 분들도 더 좋은 알고리즘이 있으시면 올려 주세요.

망치의 이미지

시간이 오래 걸리더라도 포함하는 조합으로 압축할 수 있으면 됩니다.
어떻게 효과적으로 압축할 수 있을지요...

---------------------------------------
http://www.waitfor.com/
http://www.textmud.com/

netionics의 이미지

문제를 좀 더 이해해야겠지만 문득 존 벤틀리가 쓴 생각하는 프로그래밍의 전철어구를 찾는 문제가 연상이 되네요
책을 찾아보시면 힌트를 얻을 수 있을 것 같습니다. :)

:)

phonon의 이미지

전제 조건은 포함되어 있는 알파벳의 갯수와 구성 요소는 같고, 배열의 순서가 다른 경우에 해당하지 않나요?

이 문제는 한쪽이 다른 쪽의 부분집합인지 아닌지를 판단하는 문제 같습니다.

winner의 이미지

이 문제는 망치님이 질문을 정확히 하심에 따라 다 풀린 것 같아요.

auditory의 이미지


문제가 아직 잘 이해가 안되는군요...

입력, 출력이 뭔가요??

망치의 이미지

글로 설명하니 좀 어렵긴한데요.

입력은 8C6, 8C5 모두 이구요.
출력은 8C6 조합들중의 일부입니다.

---------------------------------------
http://www.waitfor.com/
http://www.textmud.com/

auditory의 이미지


8C5에 들어있는 unique한 element를 set으로 저장하고,

8C6에서 이 element들로만 구성되어있는지 하나씩 검사하면 되는거 아닌가요?

@ 웬지 아직 문제를 이해하지 못한것 같다는..

망치의 이미지

질문에서 8C5 6개의 조합이 8C6 1개 조합으로 표현됐듯듯이, 최소한의 8C6 조합으로 8C5 모두를 표현해야 합니다.

즉, 특정 8C6 조합이 특정 8C5 조합을 포함하고 있는지 비교/검사하는게 관건이 아니라,
위 8C6 리스트에서 몇번몇번 조합이면 8C5 모든 조합을 포함한다..라는 식의 결과가 나와야 됩니다.

그 과정을 어떻게 하면 쉽게 할 수 있을지가 질문이구요.

---------------------------------------
http://www.waitfor.com/
http://www.textmud.com/

auditory의 이미지


모든 8C5를 스캔해서 unique element를 모아서 set을 만듭니다. (여기까지는 위와 동일)

이제 문제는 이 set을 covering하는 super set을 8C6조합들의

minimal union으로 구하는 문제와 동일합니다.

http://en.wikipedia.org/wiki/Set_cover_problem

harisoo의 이미지

8C6조합에 8C5조합이 포함되어 있을 경우 그 곱을 나눳을때 나머지가 항상 0입니다.
이것은 소수일 경우 항상 참이지만 소수가 아닐경우
(8C6의 0번,23번 곱이 동일하므로) 맞지 않을 수 있습니다.
따라서 나머지가 0이며, 8C6조합중 소수가 아닌 숫자가 8C5조합 리스트에 포함되어 있는지
체크하는게 맞을 것 같습니다.

prio의 이미지

저도 문제를 잘 이해 못하겠는데요;;;
대강 이해한 바로는 k-clique covering 문제와 동치가 아닌가 싶기도 한데..
(물론 k-cluque covering은 set covering으로 표현가능하지요.)

"모든 8C5" 를 "최소의 8C6" 으로 커버해야 하는 것이면,
노드의 수가 8개인 complete graph 에 대한 6-clique covering 으로 풀 수 있을 것 같습니다.
(np-complete 문제니까 '풀 수 있다'고 하긴 뭐하지만;; )

혹시 운이 좋아 complete graph에 대한 k-clique covering이 P 문제일 수도 있을텐데...
그럴거 같기도 하고 아닐 거 같기도 하고;;

redneval의 이미지

1. Power(l)을 {1,2,...,l}의 power set이라 합시다.
예를 들면, Power(3) = { {},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} }

2. Comb(l,m)을 P(l)중에서 원소의 개수가 m인 집합을 모아놓은 집합이라고 합시다.
예를 들면, Comb(3,2) = { {1,2},{1,3},{2,3} }

3. 집합 A의 모든 원소가, 집합 b의 부분집합일 때, 이를 `A는 b에 포함된다'고 합시다.
예를 들면, { {1,2},{1,3},{2,3} }는 {1,2,3}에 포함됩니다.

4. 집합 A의 어떠한 원소든지, 집합 C의 원소 중 최소한 하나에 포함된다고 할때,
이를 `C는 A보다 크다'고 합시다.
예를 들면, { {1,2,3},{1,2,4} }는 { {1,2},{1,3},{2,3},{1,4} }보다 큽니다.

5. Comb(l,n)보다 큰 Comb(l,m) 중에서 원소의 수가 가장 적은 집합을 MinSet_k(l,m,n)라고 합시다.
이러한 집합은 여러 개일 수 있으므로 아래첨자(subscription) k로 구분합니다.
예를 들면,
MinSet_1(3,2,1) = { {1,2}, {1,3} }
MinSet_2(3,2,1) = { {1,2}, {2,3} }
MinSet_1(3,3,2) = { {1,2,3} }
MinSet_1(4,3,2) = { {1,2,3}, {1,2,4}, {1,3,4} }
... 등등

(제가 본문의 질문을 제대로 이해한 것이 맞다면)
본문의 질문은, MinSet_1(8,6,5)를 구하는 문제입니다.
--------------------------------------------------------------------------

그러면 다음이 성립합니다.

case 1) l == m
MinSet_1(l,m,n) = { {1,2,...,l} }
case 2) n == 0
MinSet_1(l,m,0) = { {1,2,...,m} }
case 3) 위의 경우가 아닌 나머지 경우
MinSet_1(l,m,n) = MinSet_1(l-1,m,n) U ( MinSet_1(l-1,m-1,n-1) x {{l}} )
(여기서 U는 Union을, x는 Cartesian product를 나타냄)

--------------------------------------------------------------------------

다음은 하스켈 코드입니다.

-- MinSet_1(8,6,5)를 구하는 프로그램. 숫자를 바꾸면 MinSet_1(l,m,n)을 구할 수 있음.
module Main where
prod x y = [a ++ b | a <- x, b <- y]
minSet :: Int -> Int -> Int -> [[Int]]
minSet l m n
    | l == m    = [[1 .. l]]
    | n == 0    = [[1 .. m]]
    | otherwise = minSet (l-1) m n
                  ++ (minSet (l-1) (m-1) (n-1)) `prod` [[l]]
main = mapM_ print $ minSet 8 6 5

실행결과는 다음과 같습니다.

[1,2,3,4,5,6]
[1,2,3,4,5,7]
[1,2,3,4,6,7]
[1,2,3,5,6,7]
[1,2,4,5,6,7]
[1,3,4,5,6,7]
[1,2,3,4,5,8]
[1,2,3,4,6,8]
[1,2,3,5,6,8]
[1,2,4,5,6,8]
[1,3,4,5,6,8]
[1,2,3,4,7,8]
[1,2,3,5,7,8]
[1,2,4,5,7,8]
[1,3,4,5,7,8]
[1,2,3,6,7,8]
[1,2,4,6,7,8]
[1,3,4,6,7,8]
[1,2,5,6,7,8]
[1,3,5,6,7,8]
[1,4,5,6,7,8]

--------------------Signature--------------------
Light a candle before cursing the darkness.

망치의 이미지

음.. 조금 어렵네요;; 혹시 C 문법으로도 볼 수 있을까요?;

---------------------------------------
http://www.waitfor.com/
http://www.textmud.com/

sliver의 이미지

최적의 답이 안나옵니다. minSet 4 2 1이 [[1,2],[1,3],[1,4]]가 나오네요.

badragon의 이미지

case 1) l == m
MinSet_1(l,m,n) = { {1,2,...,l} }
case 2) n == 0
MinSet_1(l,m,0) = { {1,2,...,m} }
case 3) 위의 경우가 아닌 나머지 경우
MinSet_1(l,m,n) = MinSet_1(l-1,m,n) U ( MinSet_1(l-1,m-1,n-1) x {{l}} )
(여기서 U는 Union을, x는 Cartesian product를 나타냄)

위의 해가 min 값이 된다는 것을 어떻게 알 수 있나요?

그냥 n의 갯수의 집합원을 갖는 set을 m의 갯수로 확장하는 것으로 보이는데요.

실제로도 minSet 8 6 1 으로 수정해서 결과를 보면

[ 1, 2, 3, 4, 5, 6 ]
[ 1, 2, 3, 4, 5, 7 ]
[ 1, 2, 3, 4, 5, 8 ]

이 나옵니다.

해가 여러개 일 수 있겠지만

[ 1, 2, 3, 4, 5, 6 ]
[ 1, 2, 3, 4, 7, 8 ]

제가 문제를 제대로 이해했다면,

위의 경우가 맞는 답의 하나로 보이는데요.

badragon의 이미지

원 문제에는 최적의 값을 구하라는 얘기는 없군요.

제가 문제를 풀이한 분의 설명과 함수 minSet 에서 min 이라는 단어에 너무 집착했나 봅니다.

최적의 값을 구하는 문제가 아니라면 위에 제시된 방법을 쓰셔도 될 듯 하군요.

redneval의 이미지

sliver님과 badragon님이 지적하신대로,
제가 위에 쓴 풀이방법은 최적해가 아니고 근사해입니다.
아무튼 제가 실수했던 것은 사실이고, 혼란을 일으켜서 죄송합니다.

badragon님이 죄송해하실 필요는 없습니다. ^^;

--------------------Signature--------------------
Light a candle before cursing the darkness.

sliver의 이미지

그냥 brute-force하게 8C5들 중 합칠 수 있는 것들은 최대한 합치는 방식으로 하면
[[1,2,3,4,5,6],[1,2,3,4,5,7],[1,2,3,4,6,7],[1,2,3,5,6,7],[1,2,4,5,6,7],[1,2,3,4,5,8],
[1,2,3,4,6,8],[1,2,3,5,6,8],[1,2,4,5,6,8],[1,2,3,4,7,8],[1,2,3,5,7,8],[1,2,4,5,7,8],
[1,2,3,6,7,8],[1,2,4,6,7,8],[1,2,5,6,7,8],[3,4,5,6,7,8]]
이 나옵니다.
관건은 이게 최적의 답이냐 하는 점인듯 한데, 심증으론 이런 방법이 옳을 것 같은데 증명은...쉽게 못하겠네요.

망치의 이미지

제가 미처 말씀을 못드렸네요..
최소-최적의 답을 구해야 합니다. 어떻게 확인할 수 있을지, 저런 조합이 몇가지나 나올지 확인할 수 있는 방법을 생각해내는게 많이 어렵네요;

---------------------------------------
http://www.waitfor.com/
http://www.textmud.com/

auditory의 이미지

아직 문제 정의조차 제대로 되어있지 않습니다.

입력이 8C5 조합 중 일부와 8C6조합 중 일부이고, 출력은 입력에 있는 8C6조합 중 일부라고 하셨습니다.

위에 논의되는 방법은 입력이 8,6,5 같은 숫자이고요..

원질문자가 문제를 잘 설명하지 않으면,

답변자들이 문제 자체를 상상해서 각각의 문제를 푸는 방법을 제시하게 됩니다.

좀더 명확하게 문제를 설명하시다보면 해결책도 자연스럽게 찾아질것으로 보입니다.

망치의 이미지

위에 리플로 달았듯이 입력은 8C6, 8C5 모두입니다. (일부가 아닙니다)
출력은 8C6 조합중의 일부조합이 맞습니다.

---------------------------------------
http://www.waitfor.com/
http://www.textmud.com/

망치의 이미지

오늘 고민을 많이 해봤습니다. 이정도면 질문도 어느정도 이해가 쉽고 답에도 근접하게 된것같습니다.
정확히 이해하신분도 계시지만 제 설명이 부족해서 명확하게 이해하기 힘든부분도 있는게 사실입니다..

경우의 수를 줄여서 5C4 조합을 이용하여 5C3 의 조합을 모두 포함하는 조합을 만들어보겠습니다.
5C3 리스트의 우측 번호는 해당 조합을 포함하고 있는 5C4 조합의 번호입니다.

5C4

(1): 1 2 3 4
(2): 1 2 3 5
(3): 1 2 4 5
(4): 1 3 4 5
(5): 2 3 4 5

5C3

1 2 3 - (1) (2)
1 2 4 - (1)     (3)
1 2 5 -     (2) (3)
1 3 4 - (1)         (4)
1 3 5 -     (2)     (4)
1 4 5 -         (3) (4)
2 3 4 - (1)             (5)
2 3 5 -     (2)         (5)
2 4 5 -         (3)     (5)
3 4 5 -             (4) (5)

이렇게 어떤 조합에 포함되는지는 확인이 됐습니다.
답은 여러가지가 나올 수 있습니다.

(1) (2) (3) (4)
(1) (2) (3) (5)
.
.

최소 4개의 조합이 있어야 5C3 조합을 모두 포함 할 수 있게 됩니다..

---------------------------------------
http://www.waitfor.com/
http://www.textmud.com/

망치의 이미지

움.. 더이상 의견주시는 분이 안계시네요..
조언좀 부탁드려요. ㅠㅠ

---------------------------------------
http://www.waitfor.com/
http://www.textmud.com/

winner의 이미지

하여간 이 문제는 다른 분이 설명하셨듯 계산복잡도가 높은 문제로 보입니다.
결국 다 해봐야 한다는 거죠.
집합형태의 자료구조를 활용해서 문제를 풀면 그렇게 어렵지 않습니다.

설명을 위해 위의 5C4, 5C3를 예로 들겠습니다.
위에서 설명하실때 사용한 테이블을 만드신 후(이곳이 NP 문제로 보입니다.)

다음부터는 이해하기에는 정보가 부족하지만 Wikipedia에서 설명하듯
욕심쟁이 알고리즘(Greedy Algorithm)으로 생각보다 빠르게 찾을 수 있습니다.

(n)은 5C4의 수열집합을 나타낸다고 합시다.
즉 (1)은 5C4의 첫번째 수열집합 {1, 2, 3, 4}를 나타내고
(2)은 두번째 수열집합 {1, 2, 3, 5},
그리고 계속해서 (5)까지 있겠지요.

[m]은 5C3의 수열집합을 나타낸다고 합시다.
즉 [1]은 5C3의 첫번째 수열집합 {1, 2, 3}을 나타내고
[2]는 {1, 2, 4}, 그리고 계속해서 [10]까지 있습니다.

{} 그러니까 공집합에서 시작합니다.
이 공집합은 5C3 중 어떤 수열도 커버하지 못합니다.

다음은 위의 공집합에 5C4의 수열집합 (1) 에서 (5)를 하나의 원소로 갖는 집합들을 만들고요.
그러면 이 과정에서 만들어지는 집합은
{(1)} - [1], [2], [4], [7] 커버
{(2)} - [1], [3], [5], [8] 커버
.... 그리고 계속해서 {(5)} - [7], [8], [9], [10] 커버
이렇게 5개가 나옵니다.

다음은 위의 5개의 집합에서 똑같이 (1)에서 (5)까지의 원소를 추가로 넣어봅니다.
위 과정의 첫번째 집합 {(1)}에다가 (1)을 다시 넣어봐야 변화는 없으므로 이건 빼고,
(2)를 넣어보면 {(1), (2)} - [1], [2], [3], [4], [5], [7], [8] 커버
(3)을 넣어보면 {(1), (3)} - [1], [2], [3], [4], [6], [7], [9] 커버
물론 마지막은 {4}에다가 (5)를 넣은
{(4), (5)} - [4], [5], [6], [7], [8], [9], [10] 커버
{(5)}는 더이상 새로운 집합형태를 만들지 못하므로 버립니다.
이런 식으로 원래 커버하는 녀석들을 원소로 갖는 집합의 합집합을 구해서 전체 [1] ~ [10]을 커버하는지 봅니다..

위 과정으로 [1] ~ [10]을 커버하는 녀석은 나오지 않고 끝낼 수 없으므로
다시 위 과정에서 만들어진 10개의 집합에다가 다시 똑같은 과정을 해봅시다.
이제 일반화를 해서 넣을 원소는 (n)에서 가장 큰 n, 즉 가장 큰 원소보다 1 큰 수가 있으면 넣으면 됩니다.
그러니까 {(1), (2)} 는 (2)가 가장 크므로 (3)을 넣으면 되고, {(1), (3)}은
(3)이 크니까 1 큰 (4)를 넣어보고, {(4), (5)} 처럼 (5)를 가진 집합은 더 큰 수가
없으므로 다음 과정에 참여하는 기반집합으로 삼을 수가 없습니다.

이런 식으로 반복적으로 [1] ~ [10]을 커버하는 녀석이 있는지 확인하면 됩니다.

redneval님께 부탁이 있습니다. 이걸 재귀표현을 하고 싶습니다만 제가 재주가 없네요.
수학적 재귀표현과 함께 흥미로운 code 부탁드립니다.

grassman의 이미지

일단 중간 결과는 다음과 같이 나옵니다. (실제 계산해보니 경우의 수가 생각보다 많아서 계산을 끝까지 못하겠더군요. 출력 결과는 보기 좋게 다시 편집했습니다.)

{ 
 { 1 2 3 4 5 6 } 
 { 1 2 3 4 5 7 } 
 { 1 2 3 4 5 8 } 
 { 1 2 3 4 6 7 } 
 { 1 2 3 4 6 8 } 
 { 1 2 3 4 7 8 } 
 { 1 2 5 6 7 8 } 
 { 1 3 5 6 7 8 } 
 { 1 4 5 6 7 8 } 
 { 2 3 5 6 7 8 } 
 { 2 4 5 6 7 8 } 
 { 3 4 5 6 7 8 }
}

코드는 다음과 같습니다.
STL은 잘 사용하지 못하는지라 최적화고 뭐고 없습니다.

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
 
using namespace std;
 
// Types
typedef set<int>                                SetGenerator;
typedef set<int>::iterator                      SetGeneratorIt;
typedef set<SetGenerator>                       Set;
typedef set<SetGenerator>::iterator             SetIt;
typedef set<Set>                                ResultSet;
typedef set<Set>::iterator                      ResultSetIt;
 
// Display class
class CDisplay
{
public:
    static void DisplaySet(const Set &s);
    static void DisplayAll(const ResultSet &rs);
};
 
void CDisplay::DisplaySet(const Set &s)
{
    SetIt sit;
    SetGeneratorIt sgit;
 
    cout << "{ ";
    for( sit = s.begin(); sit != s.end(); sit++ )
    {
        cout << "{ ";
        for( sgit = sit->begin(); sgit != sit->end(); sgit++ )
            cout << *sgit << " ";
        cout << "} ";
    }
    cout << "}" << endl;
}
 
void CDisplay::DisplayAll(const ResultSet &rs)
{
    ResultSetIt rsit;
 
    for( rsit = rs.begin(); rsit != rs.end(); rsit++ )
        DisplaySet(*rsit);
}
 
// Combination generator class
class CCombination
{
public:
    inline CCombination(int n, int r) { SetGenerator s; Generate(s, n, r); };
 
    inline Set &GetResult(void) { return mySet; };
 
private:
    Set mySet;
 
    void Generate(SetGenerator s, int n, int r);
};
 
void CCombination::Generate(SetGenerator s, int n, int r)
{
    if( r == 0 )
    {
        if( mySet.find(s) == mySet.end() )
            mySet.insert(s);
 
        return;
    }
 
    for( int i = 1; i <= n; i++ )
    {
        if( s.find(i) == s.end() )
        {
            s.insert(i);
            Generate(s, n, r - 1);
            s.erase(i);
        }
    }
}
 
// Comparison class
class CCompareSet
{
public:
    static bool IsSubSet(const SetGenerator &orig, const SetGenerator &comp);
    static ResultSet GetMinimalSet(const Set &orig, const Set &comp);
 
private:
    static void InnerComparator(ResultSet &s, Set cs, const Set &orig, const Set &comp);
};
 
bool CCompareSet::IsSubSet(const SetGenerator &orig, const SetGenerator &comp)
{
    if( orig.size() < comp.size() )
        return false;
 
    for( SetGeneratorIt it = comp.begin(); it != comp.end(); it++ )
    {
        if( orig.find(*it) == orig.end() )
            return false;
    }
 
    return true;
}
 
// Greedy algorithm
void CCompareSet::InnerComparator(ResultSet &s, Set cs, const Set &orig, const Set &comp)
{
    int s1, s2;
    SetIt it, it2;
    vector<SetGenerator> eraseList;
    vector<SetGenerator>::iterator vit;
    Set o, o2, c;
 
    if( comp.empty() )
    {
        s1 = cs.size();
 
        if( s.begin() == s.end() )
            s2 = 0x7fffffff;
        else
            s2 = s.begin()->size();
 
        if( s1 > s2 )
            return;
 
        if( s1 < s2 )
            s.clear();
 
        s.insert(cs);
 
        // this result can be updated during calculation
        cout << "Interim sets: " << endl;
        CDisplay::DisplayAll(s);
 
        return;
    }
 
    s2 = 0;
    o.clear();
    for( it = orig.begin(); it != orig.end(); it++ )
    {
        for( s1 = 0, it2 = comp.begin(); it2 != comp.end(); it2++ )
        {
            if( IsSubSet(*it, *it2) )
                s1++;
        }
 
        if( s1 < s2 )
            continue;
 
        if( s1 > s2 )
            o.clear();
 
        o.insert(*it);
        s2 = s1;
    }
 
    for( it = o.begin(); it != o.end(); it++)
    {
        o2 = orig;
        o2.erase(*it);
        cs.insert(*it);
 
        c = comp;
        eraseList.clear();
        for( it2 = comp.begin(); it2 != comp.end(); it2++ )
        {
            if( IsSubSet(*it, *it2) )
                eraseList.push_back(*it2);
        }
 
        for( vit = eraseList.begin(); vit != eraseList.end(); vit++)
                c.erase(*vit);
 
        InnerComparator(s, cs, o2, c);
 
        cs.erase(*it);
    }
}
 
ResultSet CCompareSet::GetMinimalSet(const Set &orig, const Set &comp)
{
    Set currentSet;
    ResultSet minimalSet;
 
    InnerComparator(minimalSet, currentSet, orig, comp);
 
    return minimalSet;
}
 
// Main
int main(void)
{
    CCombination c1(8,6), c2(8,5); // two nCr value sets
    ResultSet rs;
 
    // calcuate minimal set
    rs = CCompareSet::GetMinimalSet(c1.GetResult(), c2.GetResult());
 
    // final result
    cout << "Result: " << endl;
    CDisplay::DisplayAll(rs);
 
    return 0;
}

winner의 이미지

본 것 중에 CCombination이 특히 제가 생각한 것과는 달라서 이해가 안 되는군요.
그리고 CCompareSet::IsSubSet 은 includes 가 있습니다.
http://www.sgi.com/tech/stl/includes.html

항상 set을 사용하지 말고, bitset을 적절히 섞으면 성능이 좀 나올 것 같아요.

grassman의 이미지

includes는 모르고 있었군요. 감사합니다.

사실 코드가 저렇게 된 건 만들다가 귀찮아진게 가장 큰 원인입니다. :)
bitset에 배열 할당해서 마스킹해가면서 하려고 하니 어차피 매 과정마다 배열의 복사가 발생할 건 틀림없는지라 그냥 편하게 구현하려고 하다 보니 저렇게 걸래 비슷한 코드가 되어 버렸습니다.

CCombination은 그냥 생각나는대로 만든겁니다. integer의 set을 선언하고 각 재귀호출 과정에서 set 내에 중복되지 않는 숫자를 추가로 조합하는 것이 기본 알고리즘입니다. 저렇게 하지 않고 set에 대한 permutation으로 만들 수도 있을거라고 봅니다.

p.s. 변수 타입이나 변수 명을 멋대로 지은 것도 난독성의 주 원인입니다만 되는대로 코딩하기 시작한 코드가 다 그런거 아니겠습니까? :)

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.