15649) n과 m(1)

문제요약

이 문제는 n과 m이 주어지고 1부터 m까지의 숫자 중 n개를 가지고 만들 수 있는 순열을 모두 출력하는 문제다

풀이

재귀 함수를 이용
순열을 순차적으로 출력해야 하므로, k길이의 순열을 구하는 함수를 이용해 길이 n부터 길이 1까지 재귀적으로 호출한다.
예를 들어, n길이를 구하는 함수에서 결과 배열에 1을 넣고 n-1길이의 순열을 구하는 함수를 호출한다. 해당 함수에서는 2를 결과 배열에 넣고 n-2길이의 순열을 구하는 함수를 호출한다. 이런식으로 1길이의 순열을 구하는 함수까지 호출한다. 1길이의 순열을 구하는 함수에서는 여태껏 저장된 결과 배열을 호출한다.

combi함수

벡터를 이용
이 함수에서는 left(결과에 들어가지 않은 남은 숫자들)을 담은 배열에서 하나씩 꺼내어 result(결과)배열에 left의 원소들을 차례로 넣는다. 이때, result배열은 길이가 하나씩 늘어나야 하고, left는 하나가 줄어야 하는데, 인덱스는 그대로 0부터 시작해야 한다. 따라서 vector를 이용해 손쉽게 해당 기능을 구현할 수 있었다.
1. 구하고자 하는 순열의 길이가 1일 경우, result배열과 left배열의 조합을 차례로 출력하면 된다.
2. 구하고자 하는 순열의 길이가 1이 아닐 경우, result 배열과 left배열을 하나 더 만든다. 이는 result 배열에 left의 원소를 하나씩 넣을 때 순서가 변경되어 상위 함수에서 원하는 원소 접근에 실패하지 않게 하기 위한 장치다.
3. 새로운 결과 배열에 이전 값들을 다 넣고 left의 첫번째 원소를 넣는다. 그리고 left에서 해당 원소는 지운다.
4. 새로운 result와 left, 순열길이-1을 전달하여 combi를 다시 호출한다.
5. 3에서 넣었던 result의 마지막 원소와 left의 원소를 바꾸어 넣는다.
6. for loop에서 빠져나와 마지막 combi 함수를 실행한다.

코드

//
//  15649.cpp
//  algorithm_study
//
//  Created by Jihyun Kyoung on 2023/08/01
//
#include <iostream>
#include <vector>
using namespace std;
template <typename T>
void combi(vector<T>* result,vector<T>* left, int m);
    
int main(){
    int n,m;
    cin>>n;
    cin>>m;
   
    vector<int> left;
    vector<int> result;
    for(int i =0;i<n;i++)
        left.push_back(i+1);
    combi(&result,&left, m);

}
template <typename T>
void combi(vector<T>* result,vector<T>* left, int m){
    int result_size = (*result).size();
    int n = left->size();


    if(m == 1){
        for(int i =0;i<n;i++){
            for(int j = 0;j<result_size;j++)
                printf("%d ", (*result)[j]);
            printf("%d\n", (*left)[i]);
            }
    }
    else{
        vector<int> *result_n= new vector<int>;
        vector<int> *left_n = new vector<int>;
        for(int i =0;i<result_size;i++){
            result_n->push_back((*result)[i]);
        }
        (*result_n).push_back((*left)[0]);
        for(int i =1;i<n;i++)
            (*left_n).push_back((*left)[i]);


        for(int i =0;i<left_n->size();i++){
            combi(result_n, left_n,  m-1);
            //swap
            int tmp = ((*result_n)[result_size]);
            (*result_n)[result_size] = (*left_n)[i];
            (*left_n)[i] = tmp;
       }
        combi(result_n, left_n,  m-1);
    }
}