[Algorithm] 순열(Permutation)

순열

순열이란?

• n개의 요소 중 r개의 항목을 뽑는 것을 말한다.
• 순서가 다르면 다른 케이스로 간주한다.
• A, B → A, B, AB, BA

코드

• result : 결과 값을 저장하는 셋
• visited : 방문 여부를 확인하는 배열
• temp : r개를 뽑는 결과 값을 저장하는 배열
• data : 요소 배열
• r : 뽑고자 하는 개수
• depth : 재귀 호출 깊이 값

class Solution {
    public Set<String> solution(String data, int r) {
        Set<String> result = new HashSet<>();
        permutation(result, new boolean[data.length()], new char[data.length()], data.toCharArray(), r, 0);
        return result;
    }

    private static void permutation(Set<String> result, boolean[] visited, char[] temp, char[] data, int r, int depth) {
        if (r == depth) {
            result.add(IntStream.range(0, depth).mapToObj(i -> String.valueOf(temp[i])).collect(Collectors.joining()));
            return;
        }

        for (int i = 0; i < data.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                temp[depth] = data[i];
                permutation(result, visited, temp, data, r, depth + 1);
                visited[i] = false;
            }
        }
    }
}

class SolutionTest extends Specification {
    @Unroll
    def "#data, #r-> #result"() {
        expect:
        new Solution().solution(data as String, r as int) == result as Set<String>

        where:
        data  | r | result
        "ABC" | 1 | ["A", "B", "C"]
        "ABC" | 2 | ["AB", "AC", "BA", "BC", "CA", "CB"]
        "ABC" | 3 | ["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"]
    }
}

코드 - 문자열 활용

public class Solution {
    public Set<String> permutation(String text) {
        Set<String> result = new HashSet<>();
        permutation(result, "", text);
        return result;
    }

    private void permutation(Set<String> result, String prefix, String text) {
        if (!prefix.isEmpty()) {
            result.add(prefix);
        }

        for (int i = 0; i < text.length(); i++) {
            permutation(result, prefix + text.charAt(i), text.substring(0, i) + text.substring(i + 1, text.length()));
        }
    }
}

class SolutionTest extends Specification {
    @Unroll
    def "#data -> #result"() {
        expect:
        new Solution().permutation(data as String) == result as Set<String>

        where:
        data  | result
        "123" | ["1", "2", "3", "12", "13", "21", "23", "31", "32", "123", "132", "213", "231", "312", "321"]
        "ABC" | ["A", "B", "C", "AB", "AC", "BA", "BC", "CA", "CB", "ABC", "ACB", "BAC", "BCA", "CAB", "CBA"]
    }
}

중복 순열

중복 순열이란?

• 순열과 동일하나 이미 선택한 요소가 추가적으로 선택될 수 있다
• 순열 예시
  • A, B → A, B, AB, BA
• 중복 순열 예시
  • A, B → A, B, AB, BA, AA, BB

코드

• 기존 순열 코드에서 방문 여부 체크 부분만 제외해서 구현

class Solution {
    public Set<String> solution(String data, int r) {
        Set<String> result = new HashSet<>();
        permutation(result, new char[data.length()], data.toCharArray(), r, 0);
        return result;
    }

    private static void permutation(Set<String> result, char[] temp, char[] data, int r, int depth) {
        if (r == depth) {
            result.add(IntStream.range(0, depth).mapToObj(i -> String.valueOf(temp[i])).collect(Collectors.joining()));
            return;
        }

        for (int i = 0; i < data.length; i++) {
            temp[depth] = data[i];
            permutation(result, temp, data, r, depth + 1);
        }
    }
}

class SolutionTest extends Specification {
    @Unroll
    def "#data, #r -> #result"() {
        expect:
        new Solution().solution(data as String, r as int) == result as Set

        where:
        data  | r | result
        "ABC" | 1 | ["A", "B", "C"]
        "ABC" | 2 | ["AA", "BB", "CC", "AB", "BC", "AC", "CA", "BA", "CB"]
        "ABC" | 3 | ["ABA", "BBA", "ABB", "ABC", "BBC", "CBB", "BBB", "CBA", "CBC", "ACA", "ACB", "BCB", "CCA", "AAA", "ACC", "BCA", "AAB", "BAA", "CAA", "CCC", "AAC", "BAB", "BCC", "CCB", "BAC", "CAC", "CAB"]
    }
}

참고

• https://siyoon210.tistory.com/76
• https://25jay-study-blog.tistory.com/m/17
• https://gaybee.tistory.com/29