[Leet Code] 046 Permutations

https://leetcode.com/problems/permutations/

Permutations - LeetCode

 

 

1. BackTracking

참고자료

https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

Backtracking을 사용하여 아래 그림을 구현해본다. DFS로 한 쪽 끝을 방문한 이후 다시 올라가서 다른 끝을 찾아간다.

참고 동영상

https://www.youtube.com/watch?v=IPWmrjE1_MU 

 

1) List

class Solution {
    void permute(vector<int> &nums, vector<vector<int>> &result, int start)
    {
        if( start == nums.size() ) result.push_back(nums);
        else
        {
            for(int i=start; i<nums.size(); ++i)
            {
                swap(nums, start, i);
                permute(nums, result, start+1);
                swap(nums, start, i);
            }
        }
    }
    
    void swap(vector<int> &nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        permute(nums, result, 0);
        return result;
    }
};

 

2) String

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

void permute(string &prefix , string &suffix, vector<string> &result)
{
    if(suffix.length() == 0)
    {
        result.push_back(prefix);
        return;
    }
    for(int i=0 ; i<suffix.length() ; i++)
    {
        prefix += suffix[i];
        suffix = suffix.substr(0,i) + suffix.substr(i+1);
        permute(prefix , suffix, result);
        suffix = suffix.insert(i, 1, prefix[prefix.size()-1] );
        prefix = prefix.substr(0,prefix.size()-1);
    }
}

int main()
{
    string suffix = "123";
    string prefix = "";
    vector<string> result;

    permute(prefix, suffix,result);

    for(string s:result)
        cout << s << endl;

    cout << "size=" << result.size();

    return 0;
}

 

2. Next Permutation

1) next Permutation 구현

- 역순으로 탐색해서 k가 0보다 작아졌다면 배열은 내림차순으로 정리되어 있다.

이때 if k>=0 코드 이하로 진입하면 nums[k] 때문에 에러가 난다.

 

- 남은 경우의 수를 모두 탐색하기 위해 reverse 혹은 sort를 사용하여 정렬해주면 된다. 

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

void nextPermutation(vector<int>& nums) {
    int n = nums.size(), k, l;
    
    // 끝에서 역순으로 탐색한다.
    // 오름차순대로 정렬되어있지 않은 값을 가진 Index K를 찾는다
    for (k = n - 2; k >= 0; k--)
        if (nums[k] < nums[k + 1])
            break;

    // 다시 끝에서 역순으로 탐색한다.
    // Index K의 값과 해당 값을 비교한다.
    // Index K값보다 큰 값의 Index를 찾는다.
    if (k >= 0){
        for (l = n - 1; l > k; l--)
        {
            if (nums[l] > nums[k])
                break;
        } 
        // Index K의 값과 비교 값을 바꾼다.
        swap(nums[k], nums[l]);
        // Index K 다음 값부터 끝값까지 모두 정렬해준다.
        // reverse, sort 둘 중 하나 고르면 된다
        reverse(nums.begin() + k + 1, nums.end());
        // sort(nums.begin()+k+1, nums.end());
    }
    // K < 0 일 때 첫 번째에서 검색ㅎ
    else{
        reverse(nums.begin(), nums.end());
        // sort(nums.begin(), nums.end());
    }
}

int main()
{
    vector<int> nums = {1,2,3,4};
    for(int i=0; i<24; ++i)
    {
        for(int i:nums)
            cout << i << " ";
        cout << endl;
        nextPermutation(nums);
    }
}

 

2) 문제풀이

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        
        vector<vector<int>> result;
        
        for(int i=0; i<factorial(nums.size()); ++i)
        {
            result.push_back(nums);
            nextPermutation(nums);
        }
        return result;
    }
    
private:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size(), k, l;

        for (k = n - 2; k >= 0; k--)
            if (nums[k] < nums[k + 1])
                break;

        if (k >= 0){
            for (l = n - 1; l > k; l--)
                if (nums[l] > nums[k])
                    break;
            
            swap(nums[k], nums[l]);
            reverse(nums.begin() + k + 1, nums.end());
        }
        else
            reverse(nums.begin(), nums.end());
    }
    
    int factorial(int n) {
        int f = 1;
        
        while (n > 1)
            f *= n--;
        
        return f;
    }
};

index, index+1대신

index-1, index를 사용

 

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {

        vector<vector<int>> result;
        
        int factorial_size = 1;
        for(int i= nums.size(); 0<i;  --i)
        {
            factorial_size *= i;
        }
        
        for(int i=0; i<factorial_size; ++i)
        {
            result.push_back(nums);
            nextPermutation(nums);
        }
        
        return result;
    }
    
private:
    void nextPermutation(vector<int> &nums)
    {
        int l,r;
        int n = nums.size();

        for(l = n-1; 0<l; --l)
            if(nums[l-1] < nums[l])
                break;

        if(l-1<0)
        {
            reverse(nums.begin(), nums.end());
            return;
        }

        for(r = n-1; 0<r; --r){
            if(nums[l-1] < nums[r])
                break;

        swap(nums[l-1], nums[r]);
        reverse(nums.begin()+l, nums.end());
    }
};