[Algorithm] 순열/중복 순열 알고리즘 구현 (C++)

 

1. 순열

 

1. swap을 이용한 재귀함수 구현 => 사전순 출력x

#include <iostream>
#include <vector>
#include <algorithm> 
using namespace std;

int n;
vector<int> v(10);

void permutation(int s, int e) {
    if (s == e) {
        for (int i = 0; i < n; i++) {
            cout << v[i] << " ";
        }
        cout << endl;
    }
    else {
        for (int i = s; i <= e; i++) {
            swap(v[s], v[i]);
            permutation(s + 1, e);
            swap(v[s], v[i]);
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(nullptr);

    cin >> n;
    for (int i = 0; i < n; i++) {
        v[i] = i + 1;
    }
  
    permutation(0, n - 1);
        
}

✅ 설명 :  순열 알고리즘 (Permutation Algorithm) (tistory.com)

 

 

2. 재귀함수와 visited배열을 이용하여 구현 (dfs) => 사전 순 출력

#include <iostream>
#include <vector>
#include <algorithm> 
using namespace std;

int n;
int v[10];
bool visited[10];
int result[10];

void permutation(int depth) {
    if (depth == n) {
        for (int i = 0; i < n; i++) {
            cout << result[i] << " ";
        }
        cout << endl;
    }

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            visited[i] = 1;
            result[depth] = v[i];
            permutation(depth + 1);
            visited[i] = 0;
        }
    }

}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(nullptr);

    cin >> n;

    for (int i = 0; i < n; i++) {
        v[i] = i + 1;
    }

    permutation(0);
        
}

✅ 설명 : [알고리즘] 순열(Permutation) 알고리즘 : 네이버 블로그 (naver.com)

 

+ stl 이용(next_permutation)

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    int v[3] = { 1, 2, 3};
 
    sort(v, v+3);
 
    do {
        for(int i=0;i<3;i++)
            cout << v[i] << ' ';
        cout << endl;
    } while (next_permutation(v, v+3));
    
}

 

 

2. 중복 순열

- 방문 처리가 필요 없다.

int n, r, arr[10], result[10];
void permutation(int depth) {
    if (depth == r) {
        for (int i = 0; i < r; i++) {
            cout << result[i] << " ";
        }
        cout << "\n";
    }
    else {
        for (int i = 0; i < n; i++) {
            result[depth] = arr[i];
            permutation(depth + 1);
        }
    }
}

 

 

3. 조합

1) 재귀함수를 이용한 점화식 방법

#include <iostream>

using namespace std;

int n, m, arr[10], result[10];

void combination(int r, int idx, int depth){
    if(r==0){
        for(int i=0;i<m;i++){
            cout << result[i] << " ";
        }
        cout << "\n";
    }else if(depth == n){
        return;
    }else {
        result[idx] = arr[depth];
        combination(r-1,idx+1,depth+1); // n-1Cr-1
        combination(r, idx,depth+1);  // n-1Cr
    }
}
int main()
{
    cin >> n >> m;
    for(int i=0;i<n;i++){
        cin >> arr[i];
    }
    combination(m,0,0);
    
}

 

2) https://yabmoons.tistory.com/99