[JAVA] 순열과 조합

1. break와 continue의 개념

2. 순열/조합/중복순열/중복조합 참고링크

https://gaybee.tistory.com/29

[알고리즘/자바] 조합, 순열, 중복조합, 중복순열

---

팩토리얼( ! )

1. 기본형 메서드

  public static int fact2(int n) { // 팩토리얼 기본 식
    int p = 1;
    for(int i=1 ; i<=n ; i++) {p = p*i;}
    return p;
  }

2. 재귀형 매서드

  public static int fact(int n) {  // 팩토리얼 재귀 식
  	if (n <= 1) return n; // 재귀 base 케이스. 즉, 1까지만 곱한단 소리
    else return fact(n-1) * n; // 지금 수*하나 작은 수. 하나 작은 수는 다시 재귀로 하나 더 작은수로 곱을 반복
  }

3. 예제코드

public class Factorial {
	public static void main(String[] args) {
    	int input = 4; // 4!
        System.out.println(fact(input));
    }
    public static int fact(int n) {
    	if (n <= 1) return n; // 재귀 base 케이스. 즉, 1까지만 곱한단 소리
        else return fact(n-1) * n; // 지금 수*하나 작은 수. 하나 작은 수는 다시 재귀로 하나 더 작은수로 곱을 반복
    }
}

---

순열(P / Permutation) : 순서를 지키며 나열

1. 일반식 : nPr = n! / (n-r)!

2. 코드

 1) [for] 횟수가 정해져 있을 때, 중복을 허용하지 않을때, 코드 (for문을 여러개 사용하는 방식)

// 반복문 코드

public static ArrayList<String[]> permutationLoop() {
  // 순열 요소가 인자로 주어질 경우, 인자 그대로 사용하면 되지만, 인자가 주어지지 않고
  // 문제 안에 포함되어 있을 경우 이런 식으로 직접 적어서 사용합니다.
    String[] lookup = new String[]{"A", "B", "C", "D", "E"};
    ArrayList<String[]> result = new ArrayList<>();

    for (int i = 0; i < lookup.length; i++) {
      for (int j = 0; j < lookup.length; j++) {
        for (int k = 0; k < lookup.length; k++) {
          if (i == j || j == k || k == i) continue; // 중복이면 다음으로 넘어가라는 말
            String[] input = new String[]{lookup[i], lookup[j], lookup[k]};
            result.add(input);
        }
      }
    }
  return result;
}

 2) [for] 횟수가 정해져 있을 때, 중복을 허용하는 코드

// 반복문 1개당 1개의 요소를 뽑습니다.

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

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

 3) [재귀] 임의의 횟수에서, 재귀를 사용하는 코드 (메서드를 사용하는 쪽에 선택할 배열이 있는 경우)

import java.util.*;

public class Solution { 
	public ArrayList<Integer[]> newChickenRecipe(int[] stuffArr, int choiceNum) {
    ArrayList<Integer> freshArr = new ArrayList<>();    

    for(int i = 0; i < stuffArr.length; i++) {
      String str = String.valueOf(stuffArr[i]);
      int[] element = str.chars().filter(c -> c == '0').toArray();
      if(element.length <= 2) {       
        freshArr.add(stuffArr[i]);
      }
    }

	Collections.sort(freshArr); 

    if (freshArr.size() == 0 || freshArr.size() < choiceNum) return null;

	ArrayList<Integer[]> result = new ArrayList<>();
    boolean[] visited = new boolean[freshArr.size()];

	return permutation(choiceNum, new Integer[]{}, result, freshArr, visited, 0);
  }

  public ArrayList<Integer[]> permutation(int choiceNum, Integer[] bucket, ArrayList<Integer[]> result, ArrayList<Integer> freshArr, boolean[] visited, int depth) {

    if(depth == choiceNum) {
      result.add(bucket);
      return result;
    }

    for(int i = 0; i < freshArr.size(); i++) {
      if(!visited[i]) {
        visited[i] = true;
        Integer[] concatArray = Arrays.copyOf(bucket, bucket.length + 1);
        concatArray[concatArray.length - 1] = freshArr.get(i);

        result = permutation(choiceNum, concatArray, result, freshArr, visited, depth + 1);

		visited[i] = false;
      }
    }
    return result;
  }
}

 4) [재귀] 임의의 횟수에서, 재귀를 사용하는 코드 (메서드에 선택할 배열을 만드는 경우)

import java.util.*;

public class Solution { 
	public ArrayList<String[]> rockPaperScissors(int rounds) {
    // TODO: 중복순열
    // 빈 ArrayList 객체 생성
    ArrayList<String[]> outcomes  = new ArrayList<>();
    // 총 라운드 수, 배열을 담을 새 변수, ArrayList를 담아 최종 리턴할 변수= permutation과 같은 애
    return permutation(rounds ,new String[]{}, outcomes);
	}

  // 라운드 수: 한판 할 때마다 -1될것임, 배열 : 회당 플레이 담을 배열 플레이수와 길이가 같아질것임, ArrayList : 최종 반환 시킬것이자, 재귀중에 나오는 배열을 추가해 저장할 곳
  // count=rounds이기때문에, count==3에 count+1로 재귀 돌리면, 들어오는 rounds가 이미 3보다 크기때문에 바로 리턴되버림==한판만 돎
  public static ArrayList<String[]> permutation(int count, String[] playing, ArrayList<String[]> outcome) {
    // 모든 라운드가 끝나면, ArrayList에 각 전적을 add해줌 ex) round가 3판이면, 길이가 3짜리 배열로 완성된 애들을 동시다발적으로 outcome이란 Arraylist에 add해줌
    if(count == 0) {  //base case;
      outcome.add(playing);
      return outcome;
    }

    String [] rps = new String[]{"rock","paper","scissors"};

    // 각 경우를 한바퀴씩 순회하기위한 반복문
    for(int i = 0; i < rps.length; i++) { //0, 1, 3
      // 현재 라운드의 플레이 값 
      String currentPlay = rps[i];  //r, p, s
      // 일회용 Array만들어주고, 직전 라운드에서 했던 기록넣고 기록+1의 크기로 만들어줌
      String[] plasticArray = Arrays.copyOf(playing, playing.length + 1); //[0]=>[r,0],[0]=>[p,0],[0]=>[s,0]
      // 일회용 Array에 이번판 기록 넣어줌
      plasticArray[plasticArray.length - 1] = currentPlay; //[r]=>[r,r];[r,p];[r,c], [p]=>[p,r];[p,p];[p,s], [s]=>[s,r];[s,p];[s,s]

      outcome = permutation(count - 1, plasticArray, outcome); // 이부분이 제일 이해안감
      // outcome = <[r,r,r]>에서 다시 이전 depth의 반복문 이어서 실행 => <[r,r,r], [r,r,p]>됨 => 반복
      // <{}> = permutation(2,[r],<{}>) => permutation(1,[r,r],<{}>)=>permutation(0,[r,r,r],<{}>))
      // <{}> = permutation(2,[p],<{}>) => 
      // <{}> = permutation(2,[s],<{}>) => 
    }
    return outcome; // 모든 재귀호출 끝나면, outcome = <[r,r,r],[r,r,p],[r,r,s], ... ,[s,s,s]>
  }
}

5) [재귀] visited를 사용한 방법

public static int orderOfPresentation(int N, int[] K) {
    
    ...
    
    // 변수 선언부
    int N = 3;
    int[] K = {2,3,1};
    ArrayList<int[]> list = new ArrayList<>();
    boolean[] visited = new boolean[K.length];

    // 임의의 숫자 N까지의 숫자를 배열로 만듦
    int[] base = new int[N];
    for(int i=0 ; i<N ; i++) {
        base[i] = i+1;
    }
	
    ...
    
    // 순열로 된 ArrayList를 뽑아냄
    list = perm(list, visited, 0, N, K.length, new int[]{}, base);

	...
}

    public static ArrayList<int[]> perm (ArrayList<int[]> list,boolean[] visited, int depth, int n, int r, int[] arr, int[] base) {
        // r개 뽑았을 때, list에 추가
        if(depth == r) {
            list.add(arr);
            return list;
        }
        
        // 재귀로 순열의 경우 모두 검색
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                // arr는 특성상 추가가 안되므로, 새로 만들고 복붙해줘야함
                int[] tempArr = Arrays.copyOf(arr, arr.length+1);
                tempArr[tempArr.length - 1] = base[i];
                list = perm(list, visited, depth+1, n, r, tempArr, base);
                visited[i] = false;
            }
        }
        
        // 최종 완성된 list 반환
        return list;
    }

---

조합(C / Combination) : 순서상관 없는 경우의 수

일반식 : nCr = n! / (r! * (n-r)!)

// 반복문 코드

public static ArrayList<String[]> combinationLoop() {
	// 조합 요소가 인자로 주어질 경우, 인자 그대로 사용하면 되지만, 인자가 주어지지 않고
	// 문제 안에 포함되어 있을 경우 이런 식으로 직접 적어서 사용합니다.
  String[] lookup = new String[]{"A", "B", "C", "D", "E"};
  ArrayList<String[]> result = new ArrayList<>();

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

  return result;
}

---