[Algorithm] Permutation & Combination(순열 & 조합) Algorithm

Gogh·2023년 1월 2일
0

Algorithm

목록 보기
9/10

🎯 목표 :  순열과 조합 알고리즘의 이해와 구현

📒 Permutation Algorithm(순열 알고리즘)

📌  순열

  • 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산
  • n개의 요소의 순서를 뒤섞는 경우의 수는 n! 과 같다(5! = 1x2x3x4x5)
  • 모든 경우의 수를 계산해야하는 완전 탐색 알고리즘이다.
  • {a,b,c}와 {a,c,b}는 다른 값이다.
  • 순열과 중복 순열의 차이는 자기자신을 포함 하는지에 따라 다르다.
  • 중복순열은 {a,a,b} {a,b,b}와 같이 같은 요소를 허용한다.
  • 서로 다른 n개중에 r개를 선택하는 경우의 수


📌  순열의 모든 경우의 수 구현

  • {A,B,C,D,E} 의 문자중 3개의 문자만 선택하여 순열을 구하기

👉 반복문 구현

public static ArrayList<String[]> permutationFor() {
    String[] choiceCase = new String[]{"A", "B", "C", "D", "E"};
    ArrayList<String[]> result = new ArrayList<>();

    for (int i = 0; i < choiceCase.length; i++) {
      String pick1 = choiceCase[i];
      for (int j = 0; j < choiceCase.length; j++) {
        String pick2 = choiceCase[j];
        for (letintk = 0; k < choiceCase.length; k++) {
          String pick3 = choiceCase[k];

          if (i.equals(j) || j.equals(k) || k.equals(i)) continue;
          result.add(new String[]{pick1, pick2, pick3});
       }
     }
   }
}

👉 재귀 호출 구현

  • 위의 예시에서 5개의 문자중 3개의 문자만 선택하여 순열을 구하고자 한다면,
  • finalChoiceCount \= 3 ( 3개의 문자만 선택한다)
  • choiceCount \= 3 (3개의 문자만 선택한다 하지만, 재귀 호출을 할때마다 다른 선택지를 선택하기 위해 -1을 해주며 호출한다)
  • result 모든 경우의 수를 배열로 저장할 리스트
  • choiceCase \= {A,B,C,D,E} (선택할수 있는 요소들)
  • countCase \= {3} (각 경우를 저장할 배열 길이 = 3)
  • 재귀 탈출 조건은 choiceCase가 0이 되었을때 재귀 호출을 멈추고 result 에 각 경우의 케이스 배열을 저장하며 탈출 한다.
  • 다른 선택지를 선택하기 위한 for문이 동작 할때, 앞에 저장된 요소가 이미 countCase 배열 내부에 있다면, for문을 무시하도록 하여, {A,A,A}와 같은 자기 자신이 포함된 케이스를 만들지 않도록 하였다.
    private ArrayList<String[]> pernutationNoneOverlap
            (int finalChoiceCount, int choiceCount, ArrayList<String[]> result, String[] choiceCase, String[] countCase) {
        // 순서가 다르면 다른 요소로 취급할때 ex) {a,b,c} != {b,c,a}
        // 하나의 선택 경우에서 선택할 인자가 중복이 불가능하다.
        if (choiceCount == 0) {
            result.add(countCase);
            return result;
        }
        for (String s : choiceCase) {
            // 배열 countCase 요소중에 s가 있다면 재귀 호출 하지 않음
            if (Arrays.stream(countCase).noneMatch(i -> Objects.equals(i, s))) {
                countCase[finalChoiceCount - choiceCount] = s;
                String[] cycleArr = countCase.clone();
                result = pernutationNoneOverlap
                        (finalChoiceCount, choiceCount - 1, result, choiceCase, cycleArr);
            }
        }
        return result;
    }

📌  중복 순열의 경우의 수 구현

  • {A,B,C,D,E} 의 문자중 3개의 문자만 선택하여 중복 순열을 구하기
  • {A,A,A}와 같이 자기 자신도 포함하는 순열이 중복 순열이다

👉 반복문 구현

public static ArrayList<String[]> permutationFor() {
    String[] choiceCase = new String[]{"A", "B", "C", "D", "E"};
    ArrayList<String[]> result = new ArrayList<>();

    for (int i = 0; i < choiceCase.length; i++) {
      String pick1 = choiceCase[i];
      for (int j = 0; j < choiceCase.length; j++) {
        String pick2 = choiceCase[j];
        for (letintk = 0; k < choiceCase.length; k++) {
          String pick3 = choiceCase[k];

          result.add(new String[]{pick1, pick2, pick3});
       }
     }
   }
}

👉 재귀 호출 구현

  • 위의 예시에서 5개의 문자중 3개의 문자만 선택하여 중복 순열을 구하고자 한다면,
  • finalChoiceCount \= 3 ( 3개의 문자만 선택한다)
  • choiceCount \= 3 (3개의 문자만 선택한다 하지만, 재귀 호출을 할때마다 다른 선택지를 선택하기 위해 -1을 해주며 호출한다)
  • result 모든 경우의 수를 배열로 저장할 리스트
  • choiceCase \= {A,B,C,D,E} (선택할수 있는 요소들)
  • countCase \= {3} (각 경우를 저장할 배열 길이 = 3)
  • 재귀 탈출 조건은 choiceCase가 0이 되었을때 재귀 호출을 멈추고 result 에 각 경우의 케이스 배열을 저장하며 탈출 한다.
  • 순열에서의 재귀 호출 코드와 반대로 다른 선택지를 선택하기 위한 for문이 동작할때 앞에 저장된 요소가 이미 countCase 배열 내부에 있더라도 조건 없이 동작하도록 하였다.
    public ArrayList<String[]> permutationOverlap
            (int finalChoiceCount, int choiceCount, ArrayList<String[]> result, String[] choiceCase, String[] countCase) {
        // 선택지를 가지고 선택할수 있는 모든 경우의 수
        if (choiceCount == 0) {
            result.add(countCase);
            return result;
        }
        for (String s : choiceCase) {
            countCase[finalChoiceCount - choiceCount] = s;
            String[] cycleArr = countCase.clone();
            result = permutationOverlap
                    (finalChoiceCount, choiceCount - 1, result, choiceCase, cycleArr);
        }
        return result;
    }

📒 Combination Algorithm(조합 알고리즘)

📌 조합

  • 순열에서 나온 경우의 수 중 {a,b,c}와 {a,c,b}는 같은 값으로 취급한다.
  • 순열에서 나온 경우의 수, 예를 들어 5개의 숫자중 3개의 숫자를 골라 조합의 경우의 수를 구하고자 한다면,
  • (1x2x3x4x5) / ((1x2x3) / (1x2)) = 10이 된다.
  • 서로 다른 n개중에 r개를 선택하는 경우의 수


📌  조합의 구현

  • {A,B,C,D,E} 의 문자중 3개의 문자만 선택하여 조합의 경우 구하기

👉 반복문 구현

  • 반복문이 순회할때  i = 0, j = i + 1, k = j + 1의 조건이 있으며,
  • 이 조건은 한번 조합 요소는 고려하지 않는 조건이다.
  • 하나의 요소로 만들수 있는 모든 경우의 수를 구한다음, 그 요소를 다음 반복에 포함하지 않는다.
public static ArrayList<String[]> combinationFor() {
  String[] choiceCase = new String[]{"A", "B", "C", "D", "E"};
  ArrayList<String[]> result = new ArrayList<>();

  for(int i = 0; i < choiceCase.length; i++) {
    for(int j = i + 1; j < choiceCase.length; j++) {
      for(int k = j + 1; k < choiceCase.length; k++) {
        String[] input = new String[]{choiceCase[i], choiceCase[j], choiceCase[k]};
				result.add(input);
      }
    }
  }

  return result;
}

👉 재귀 호출 구현

  • 위의 예시에서 5개의 문자중 3개의 문자만 선택하여 조합을 구하고자 한다면,
  • finalChoiceCount \= 3 ( 3개의 문자만 선택한다)
  • choiceCount \= 3 (3개의 문자만 선택한다 하지만, 재귀 호출을 할때마다 다른 선택지를 선택하기 위해 -1을 해주며 호출한다)
  • result 모든 경우의 수를 배열로 저장할 리스트
  • choiceCase \= {A,B,C,D,E} (선택할수 있는 요소들)
  • countCase \= {3} (각 경우를 저장할 배열 길이 = 3)
  • 재귀 탈출 조건은 choiceCase가 0이 되었을때 재귀 호출을 멈추고 result 에 각 경우의 케이스 배열을 저장하며 탈출 한다.
  • 다른 선택지를 선택하기 위한 for문이 동작 할때, 앞에 저장된 요소가 이미 countCase 배열 내부에 있다면, for문을 무시하도록 하여, {A,A,A}와 같은 자기 자신이 포함된 케이스를 만들지 않도록 하였다.
  • 또한, 위 for문이 동작할때마다, 이미 재귀 호출에서 countCase에 삽입한 요소는 고려하지 않기 위해 새로운 1회용 배열을 생성하여 앞 재귀 호출에서 삽입한 요소를 빼고 다음 재귀 호출로 넘겨준다. 
    private ArrayList<String[]> combination
            (int finalChoiceCount, int choiceCount,ArrayList<String[]> result, String[] choiceCase, String[] countCase) {
        // 순서가 달라도 같은 요소로 취급할때 ex) {a,b,c} == {b,c,a}
        // 조합 문제 - 같은 요소는 result에 넣지않는다
        if (choiceCount == 0) {
                result.add(countCase);
                return result;
        }
        for (int i = 0; i<choiceCase.length; i++) {
            // 배열 countCase 요소중에 s가 하나라도 있으면 안된다.
            int finalI = i;
            // 배열 countCase 요소중에 s가 하나라도 있으면 안된다.
            if (Arrays.stream(countCase).noneMatch(t -> Objects.equals(t, choiceCase[finalI]))) {
                countCase[finalChoiceCount - choiceCount] = choiceCase[i];
                // 다음 재귀에서 이미 삽입한 요소를 빼고 호출하기 위해 새로운 1회용 배열 생성
                String[] cycleCase = Arrays.copyOfRange(choiceCase,i,choiceCase.length);
                String[] cycleArr = countCase.clone();
                result = combination
                        (finalChoiceCount, choiceCount - 1, result, cycleCase, cycleArr);
            }
        }
        return result;
    }

📒 종합 코드

  • 반복문 코드는 제외 하였다.
public class PermutationStudy {
    public static void main(String[] args) {
        PermutationStudy a = new PermutationStudy();
        ArrayList<String[]> result = new ArrayList<>();
        String[] choiceCase = new String[]{"A", "B", "C", "D", "E"};
        int finalChoiceCount = 3;
        int choiceCount = 3;
        String[] countCase = new String[finalChoiceCount];
        a.permutationOverlap(finalChoiceCount,choiceCount,result,choiceCase,countCase);
        a.pernutationNoneOverlap(finalChoiceCount,choiceCount,result,choiceCase,countCase);
        a.combination(finalChoiceCount,choiceCount,result,choiceCase,countCase);
    }

    private ArrayList<String[]> permutationOverlap
            (int finalChoiceCount, int choiceCount, ArrayList<String[]> result, String[] choiceCase, String[] countCase) {
        // 선택지를 가지고 선택할수 있는 모든 경우의 수
        if (choiceCount == 0) {
            result.add(countCase);
            return result;
        }
        for (String s : choiceCase) {
            countCase[finalChoiceCount - choiceCount] = s;
            String[] cycleArr = countCase.clone();
            result = permutationOverlap
                    (finalChoiceCount, choiceCount - 1, result, choiceCase, cycleArr);
        }
        return result;
    }

    private ArrayList<String[]> pernutationNoneOverlap
            (int finalChoiceCount, int choiceCount, ArrayList<String[]> result, String[] choiceCase, String[] countCase) {
        // 순서가 다르면 다른 요소로 취급할때 ex) {a,b,c} != {b,c,a}
        // 하나의 선택 경우에서 선택할 인자가 중복이 불가능하다.
        if (choiceCount == 0) {
            result.add(countCase);
            return result;
        }
        for (String s : choiceCase) {
            // 배열 countCase 요소중에 s가 있다면 재귀 호출 하지 않음
            if (Arrays.stream(countCase).noneMatch(i -> Objects.equals(i, s))) {
                countCase[finalChoiceCount - choiceCount] = s;
                String[] cycleArr = countCase.clone();
                result = pernutationNoneOverlap
                        (finalChoiceCount, choiceCount - 1, result, choiceCase, cycleArr);
            }
        }
        return result;
    }
    private ArrayList<String[]> combination
            (int finalChoiceCount, int choiceCount,ArrayList<String[]> result, String[] choiceCase, String[] countCase) {
        // 순서가 달라도 같은 요소로 취급할때 ex) {a,b,c} == {b,c,a}
        // 조합 문제 - 같은 요소는 result에 넣지않는다
        if (choiceCount == 0) {
                result.add(countCase);
                return result;
        }
        for (int i = 0; i<choiceCase.length; i++) {
            // 배열 countCase 요소중에 s가 하나라도 있으면 안된다.
            int finalI = i;
            // 배열 countCase 요소중에 s가 하나라도 있으면 안된다.
            if (Arrays.stream(countCase).noneMatch(t -> Objects.equals(t, choiceCase[finalI]))) {
                countCase[finalChoiceCount - choiceCount] = choiceCase[i];
                // 다음 재귀에서 이미 삽입한 요소를 빼고 호출하기 위해 새로운 1회용 배열 생성
                String[] cycleCase = Arrays.copyOfRange(choiceCase,i,choiceCase.length);
                String[] cycleArr = countCase.clone();
                result = combination
                        (finalChoiceCount, choiceCount - 1, result, cycleCase, cycleArr);
            }
        }
        return result;
    }
}
profile
컴퓨터가 할일은 컴퓨터가

0개의 댓글