조합 알고리즘: R의 가능한 모든 조합을 인쇄합니다.

작성자 : 사라 첸 사라 첸
Hours 업데이트

조합이란 무엇입니까?

조합은 어떤 주어진 사물을 배열하는 일종이다. 수학적인 용어로 조합은 고유한 항목/개체 세트에서 항목을 선택하는 일련의 선택입니다. 여기서 항목의 순서는 중요하지 않습니다. 결과의 순서는 중요하지 않은 이벤트의 전체 결과를 계산하는 방법이라고도 합니다.

예를 들어, 5가지 색상의 가방이 주어지고 3가지 색상으로 패턴을 생성하라는 요청을 받았습니다. 3가지 색상 중 4가지 색상을 선택한 다음 다른 순서로 배열할 수도 있습니다.

색상이 RGYBI(R= 빨간색, G= 녹색, Y= 노란색, B= 파란색, I= 남색)이라고 가정해 보겠습니다. 따라서 가능한 패턴은 RGB, RGY 등이 될 수 있습니다.

다음 그림을 살펴보겠습니다.

색상 조합
색상 조합

설명 :

  • 4가지 색상 중 5가지 색상을 선택하여 나열하세요.
  • 4가지 색상의 각 블록에서 3가지 색상을 선택하여 모두 나열하세요. 예를 들어 그림에서는 "RGBI"만 선택하고 4가지 조합을 보여주었습니다.
  • 우리가 만들 수 있는 총 조합 수를 계산하는 데에는 이론이 있습니다. n개 중 r개 요소의 조합은 수학적으로 다음과 같이 표현될 수 있습니다.
조합의 공식

조합의 공식

그 신호 "!" 의미 계승. 예를 들어,
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
5라고 말해보세요! = 5*4*3*2*1 = 120

따라서 위 문제의 경우 n = 5를 의미하는 5가지 색상이 있으며 언제든지 3개 중 하나를 선택해야 합니다. 따라서 r = 3입니다. 계산 후 다음을 얻습니다.

복합성

위 시나리오에서는 총 10가지 색상 조합이 가능합니다.

조합에 대한 시간 복잡도 분석

이제 크기가 n인 배열이 주어지면 배열에서 r개의 요소를 가져와서 r개의 요소 조합을 수행하라는 요청을 받는다고 가정해 보겠습니다.

크기 n의 배열이 주어지면 O(n2) 작업을 수행할 시간입니다. 또한 중복 항목을 제거하려면 다음을 수행하십시오.

다음 단계를 수행해야 합니다.

단계 1) 입력 배열 데이터를 오름차순으로 정렬합니다. 정렬의 시간 복잡도는 다음과 같습니다. O(n*log(n)).

단계 2) 주어진 임시 배열 데이터의 고유 요소를 포함하는 다른 배열을 만듭니다.

단계 3) 그런 다음 결합 기능을 수행하십시오.

따라서 총 시간 복잡도는 다음과 같습니다. 의 위에2) + O(nLog(n)). 우리는 그것을 O(n)이라고 생각할 수 있습니다.2), n으로2 n*log(n)보다 훨씬 큽니다.

방법-1: 재귀를 사용하는 고정 요소

이 방법에서는 요소를 선택한 다음 r-1 요소의 조합을 찾습니다. 나머지 요소에서 요소를 선택하면 재귀적으로 수행되므로 이를 고정 요소 및 재귀라고 합니다.

다이어그램을 사용하여 알고리즘을 단계별로 살펴보겠습니다.

재귀가 포함된 고정 요소

단계는 다음과 같습니다.

단계 1) 첫 번째 레이어에서는 n-r+1개의 요소를 사용합니다. 즉, 우리는 3가지 요소를 취했습니다.

단계 2) 두 번째 레이어에서 요소를 선택하여 nr까지 가져옵니다. 따라서 "R"을 선택하면 R을 사용하여 G, Y, B를 사용할 수 있습니다.

단계 3) 세 번째 레이어에서 요소를 선택하여 n번째 요소까지 가져와 각각 3개의 요소를 포함하는 블록을 형성합니다.

위 그림은 재귀의 반환 값입니다. 마지막 레이어만 인쇄됩니다.

의사 코드

function combination:
pass in: inputArray, combinationArray, start, end, index, r
if index is equal to r:
for each element in combinationArray:
print each element
return
for i = start:
if i <=end and end -i+1 > r-index:
combinationArray[index] = inputArray[i]
call combination function again with updated parameter

C/로 구현C++

#include<bits/stdc++.h>
#include<stdio.h>
void Combination(char inputArray[], char combinationArray[], int start, int end, int index, int r) {
  if (index == r) {
    for (int i = 0; i & lt; r; i++) {
      printf("%c", combinationArray[i]);
    }
    printf("\n");
    return;
  }
  for (int i = start; i & lt; = end & amp; & amp; end - i + 1 & gt; = r - index; i++) {
    combinationArray[index] = inputArray[i];
    Combination(inputArray, combinationArray, i + 1, end, index + 1, r);
  }
}
int main() {
  char inputArray[] = {'R','G','Y','B','I'};
  int n = sizeof(inputArray) / sizeof(inputArray[0]);
  int r = 3;
  char combinationArray[r];
  printf("Combinations:\n");
  Combination(inputArray, combinationArray, 0, n - 1, 0, r);
}

출력:

Combinations:
RGY
RGB
RGI
RYB
RYI
RBI
GYB
GYI
GBI
YBI

에서 구현 Python

def Combination(inputArray, combinationArray, start, end, index, r):
    if index == r:
    for item in combinationArray:
    print(item, end = " ")
print()
return
i = start
while (i & lt; = end and end - i + 1 & gt; = r - index):
    combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, i + 1, end, index + 1, r)
i += 1
inputArray = "RGYBI"
n = len(inputArray)
r = 3
combinationArray = [0] * r
Combination(inputArray, combinationArray, 0, n - 1, 0, r)

출력:

R G Y 
R G B
R G I
R Y B
R Y I
R B I
G Y B
G Y I
G B I
Y B I

관련 기사

방법 2(모든 요소 포함 및 제외)

이 방법은 파스칼의 항등성에 기초합니다. 이전에는 nCr을 계산하기 위해 재귀를 사용했습니다. 여기서는 복잡한 루프 대신 분할된 방법만 사용합니다.

파스칼의 신원에 따르면,

nCr = (n-1)Cr + (n-1)C(r-1)

따라서 재귀 알고리즘에는 주어진 크기 n의 배열에서 r 요소의 조합을 찾는 2개의 재귀 논리가 있습니다.

  1. 요소가 현재 조합에 포함되어 있습니다.
  2. 현재 조합에서 요소가 제외되었습니다.

의사 코드

function combination:
pass in: inputArray, combinationArray, n, r, index, i
if the index is equal to r:
for each element in combination array:
print each element
if i>=n:
return
  combinationArray[index] = inputArray[i]
  combination(inputArray, combinationArray, n, r, index+1, i+1)
  combination(inputArray, combinationArray, n, r, index, i+1)

C/로 구현C++

#include<bits/stdc++.h>
#include<stdio.h>
void Combination(char inputArray[], char combinationArray[], int n, int r, int index, int i) {
  if (index == r) {
    for (int j = 0; j & lt; r; j++) {
      printf("%c", combinationArray[j]);
    }
    printf("\n");
    return;
  }
  if (i & gt; = n)
    return;
  combinationArray[index] = inputArray[i];
  Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
  Combination(inputArray, combinationArray, n, r, index, i + 1);
}
int main() {
  char inputArray[] = {'R','G','Y','B','I'};
  int n = sizeof(inputArray) / sizeof(inputArray[0]);
  int r = 3;
  char combinationArray[r];
  printf("Combinations:\n");
  Combination(inputArray, combinationArray, n, r, 0, 0);
}

출력:

Combinations:
RGY
RGB
RGI
RYB
RYI
RBI
GYB
GYI
GBI
YBI

에서 구현 Python

def Combination(inputArray, combinationArray, n, r, index, i):
    if index == r:
    for item in combinationArray:
    print(item, end = " ")
print()
return
if i & gt; = n:
    return
combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
Combination(inputArray, combinationArray, n, r, index, i + 1);
inputArray = "RGYBI"
n = len(inputArray)
r = 3
combinationArray = [""] * r
Combination(inputArray, combinationArray, n, r, 0, 0)

출력:

R G Y
R G B
R G I
R Y B
R Y I
R B I
G Y B
G Y I
G B I
Y B I

중복 조합 처리

때로는 입력 배열에 중복된 요소가 있을 수 있습니다.

예를 들어,

  • 입력 배열에는 n = {5, 2, 3, 1, 5}가 포함됩니다.
  • 여기서는 5가 2번 존재함을 알 수 있습니다.
  • 이제 이 배열에 대한 코드를 실행하려면 일부 조합이 반복됩니다.
  • {5, 2, 5}, {5, 2, 3} 등을 찾거나 5를 포함하는 모든 조합이 반복됩니다.

다음 두 가지 방법을 사용할 수 있습니다.

  • 입력 배열을 정렬합니다. 정렬에는 O(nlog(n)) 시간이 걸립니다.
  • 그런 다음 i 값을 늘리고 i 값과 i+1 값은 동일합니다. 기본적으로 다음 두 줄의 코드를 조합 함수에 넣습니다.
// For c/c++
while(inputArray[i] == inputArray[i+1]){
  i++;
}

# for python
  while inputArray[i]==inputArray[i+1]:
    i+=1

사전 또는 순서가 지정되지 않은 지도를 사용하여 중복 조합 추적

따라서 중복 추적을 위해 요소를 정렬하지 않으려면 주어진 단계를 따를 수 있습니다.

단계 1) 전역 사전 또는 해시맵을 선언합니다.
단계 2) 생성된 조합을 해시맵에 푸시하고 값을 XNUMX만큼 늘립니다. 조합은 키이고 해당 조합의 발생은 값입니다.
단계 3) 함수 실행이 끝나면 간단히 해시맵이나 사전의 모든 키를 인쇄합니다.

Python으로 구현한 내용은 다음과 같습니다.

unique_combination = dict()
def Combination(inputArray, combinationArray, n, r, index, i):
    if index == r:
    temp_combination = ""
for item in combinationArray:
    temp_combination += item
unique_combination[temp_combination] = unique_combination.get(temp_combination, 0) + 1
return
if i & gt; = n:
    return
combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
Combination(inputArray, combinationArray, n, r, index, i + 1);
inputArray = "RGYBIB"
n = len(inputArray)
r = 3
combinationArray = [""] * r
Combination(inputArray, combinationArray, n, r, 0, 0)
for item in unique_combination.keys():
    print(item)

출력: 

RGY
RGB
RGI
RYB
RYI
RBI
RBB
RIB
GYB
GYI
GBI
GBB
GIB
YBI
YBB
YIB
BIB

여기서는 입력이 “RGYBIB”인 것을 볼 수 있습니다. 일반적으로 일부 중복된 조합이 발생해야 합니다. 하지만 사전을 사용하고 각 조합을 키로 처리했기 때문에 고유한 조합만 인쇄할 수 있습니다.

이제 "print(unique_combination)"라고 쓰면 각 조합의 빈도를 알 수 있습니다. 다음과 같이 표시됩니다.

{'RGY': 1, 'RGB': 2, 'RGI': 1, 'RYB': 2, 'RYI': 1, 'RBI': 1, 'RBB': 1, 'RIB': 1, 'GYB': 2, 'GYI': 1, 'GBI': 1, 'GBB': 1, 'GIB': 1, 'YBI': 1, 'YBB': 1, 'YIB': 1, 'BIB': 1}

따라서 RGB, RYB, GYB가 2번 발생했음을 알 수 있습니다. 키를 사전에 삽입하는 시간 복잡도는 기본적으로 O(1)입니다. 따라서 사전을 사용하는 경우 코드를 실행하는 총 시간 복잡도는 다음과 같습니다.

O(1) + O(n*n)

O(n*n)과 동일합니다.

이전 방법을 사용하여 중복을 추적하려면 정렬에 O(n*log(n))이 필요하고 비교에는 O(n)이 필요하며 함수 자체는 O(n*n)을 사용합니다. 총 시간 복잡도는 다음과 같습니다.

O(n*log(n)) + O(n) +O(n*n)