순열-조합(C++, Python, Java)

C++

순열: next_permutation()을 이용한다. 주로 do~while문화 함께 쓰인다.

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3};

    std::sort(vec.begin(), vec.end());

    do {
        for (int i : vec) {
            std::cout << i << " ";
        }
        std::cout << std::endl;
    } while (std::next_permutation(vec.begin(), vec.end()));

    return 0;
}

조합: 재귀 함수를 이용하여 직접 구현한다.

#include <iostream>
#include <vector>

void generateCombinations(std::vector<int>& nums, int k, int start, std::vector<int>& combination) {
    if (k == 0) {
        for (int num : combination) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
        return;
    }

    for (int i = start; i < nums.size(); ++i) {
        combination.push_back(nums[i]);
        generateCombinations(nums, k - 1, i + 1, combination);
        combination.pop_back();
    }
}

int main() {
    std::vector<int> vec = {1, 2, 3};
    int k = 2; // 조합의 크기

    std::vector<int> combination;
    generateCombinations(vec, k, 0, combination);

    return 0;
}

 

Python

순열: itertools에서 불러올 수 있다.

from itertools import permutations

nums = [1, 2, 3]

for perm in permutations(nums):
    print(perm)

조합: itertools에서 불러올 수 있다.

from itertools import combinations

nums = [1, 2, 3]
k = 2  # 조합의 크기

for comb in combinations(nums, k):
    print(comb)

 

 

Java

순열: 직접 구현한다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class PermutationsExample {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>();
        nums.add(1);
        nums.add(2);
        nums.add(3);

        Collections.sort(nums);

        do {
            for (int num : nums) {
                System.out.print(num + " ");
            }
            System.out.println();
        } while (nextPermutation(nums));
    }

    private static boolean nextPermutation(List<Integer> nums) {
        int i = nums.size() - 2;
        while (i >= 0 && nums.get(i) >= nums.get(i + 1)) {
            i--;
        }

        if (i < 0) {
            return false;
        }

        int j = nums.size() - 1;
        while (nums.get(j) <= nums.get(i)) {
            j--;
        }

        Collections.swap(nums, i, j);

        Collections.reverse(nums.subList(i + 1, nums.size()));

        return true;
    }
}

 

조합: 직접 구현한다.

import java.util.ArrayList;
import java.util.List;

public class CombinationsExample {
    public static void generateCombinations(List<Integer> nums, int k, int start, List<Integer> combination) {
        if (k == 0) {
            for (int num : combination) {
                System.out.print(num + " ");
            }
            System.out.println();
            return;
        }

        for (int i = start; i < nums.size(); ++i) {
            combination.add(nums.get(i));
            generateCombinations(nums, k - 1, i + 1, combination);
            combination.remove(combination.size() - 1);
        }
    }

    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>();
        nums.add(1);
        nums.add(2);
        nums.add(3);

        int k = 2; // 조합의 크기
        List<Integer> combination = new ArrayList<>();

        generateCombinations(nums, k, 0, combination);
    }
}