다음과 같은 집합 S = {0,1,2,3,4,5} 에서 n개 ( n > 1)의 원소를 뽑는 것을 프로그램 할려고 합니다. 조건은 중복을 해도 되고 또한 cyclic해야 합니다. 즉 (1,2,3) = (2,3,1) = (3,1,2)로 다 같은 것으로 보고 그중 하나만 선택 해야 합니다. 어떻게 해야 할 지 .....
고수님들의 답변을 기다리며.... 미리 감사드립니다.
재귀적인 방법으로 풀면 됩니다.
N개의 원소가 있는 집합에서 M개의 원소를 선택하는 방법은
어떤 한 원소를 넣고, 나머지 꺼에서 M-1개를 선택하는 경우의 집합들과, 그 어떤 한 원소를 넣지 않고, 나머지 원소에서 M개를 선택하는 경우의 집합들을 합하면 됩니다.
ex) {1,2,3,4,5}에서 3개를 뽑는 경우는, 1을 넣고 {2,3,4,5}에서 2개를 뽑는 경우 와 1을 넣지 않고 {2,3,4,5}에서 3개를 뽑는 경우 의 합입니다.
중복을 해도 된다고 나와있네요. {1,1,2}도 허용이 된다는 말인 걸로 보입니다. 그렇다면, 어떤 한 원소를 넣고, 나머지 꺼에서 M-1개를 선택 하는 것이 아니라, 어떤 한 원소를 넣고, 전체 대상 원소에서, M-1개를 선택 으로 하시면 될 겁니다.
과자가 아닙니다. cuckoo dozen, 즉.12마리의 뻐꾸기란 뜻입니다.
~nice~
흐음...
재귀적인 방법으로 풀면 됩니다.
N개의 원소가 있는 집합에서
M개의 원소를 선택하는 방법은
어떤 한 원소를 넣고, 나머지 꺼에서 M-1개를 선택하는 경우의 집합들과,
그 어떤 한 원소를 넣지 않고, 나머지 원소에서 M개를 선택하는 경우의 집합들을
합하면 됩니다.
ex)
{1,2,3,4,5}에서 3개를 뽑는 경우는,
1을 넣고 {2,3,4,5}에서 2개를 뽑는 경우
와
1을 넣지 않고 {2,3,4,5}에서 3개를 뽑는 경우
의 합입니다.
중복을 해도 된다고 나와있네요.
{1,1,2}도 허용이 된다는 말인 걸로 보입니다.
그렇다면,
어떤 한 원소를 넣고, 나머지 꺼에서 M-1개를 선택
하는 것이 아니라,
어떤 한 원소를 넣고, 전체 대상 원소에서, M-1개를 선택
으로 하시면 될 겁니다.
과자가 아닙니다.
cuckoo dozen, 즉.12마리의 뻐꾸기란 뜻입니다.
~nice~
~nice~