조합 순열 부분집합

  • java에서는 따로 라이브러리가 없어서 구현해야 한다.
  • 조합
    • combination
    • nCr
    • 순서X, 중복X
    • 예
      • 카드n에서 r만큼 꺼낼때 나오는 경우
  • 순열
    • permutation
    • nPr
    • 순서O
    • 예
      • 카드n에서 r만큼 꺼내서 순서대로 나열했을때의 경우
  • 부분집합
    • powerset
    • n개의 요소에서 나오는 모든 부분집합
      • 모든 조합이라 할 수 있다.

코드

조합

//arr 조합을 할 배열
//save 조합 한 결과가 들어갈 배열
//idx save의 index값
//start arr을 순회할때 idx의 시작값
static public void combination(int[] arr, int[] save, int idx, int start){
    if(idx==save.lenth){
        //save에 조합의 결과가 저장된다.
        return;
    }
    
    for(int i=start;i<arr.length;i++){//start부터 모든 arr을 순회
        save[idx] = arr[i];//요소 선택
        //idx+1이 되고, 다음 조합으로 i+1부터 순회를 시작한다.
        combination(arr,save, idx+1, i+1);
    }
}

순열

//arr 순열을 할 배열
//save 순열 결과가 들어갈 배열
//visited 순열 선택여부
//idx save의 index값
static public void combination(int[] arr, int[] save, boolean[] visited,int idx){
    if(idx==save.lenth){
        //save에 순열의 결과가 저장된다.
        return;
    }
    
    for(int i=0;i<arr.length;i++){//모든 arr을 순회
        if(visited[i]) continue;
        visited[i] = true;//방문처리
        save[idx] = arr[i];//요소 선택
        combination(arr, save, visited, idx+1);
        visited[i] = false;//방문처리 복구
    }
}

파워셋

//arr 원본 배열
//save true,false로 하여 부분집합을 확인
//idx save의 index값
static public void powerset(int[] arr, boolean[] save,int idx){
    if(idx==arr.lenth){
        //모든 부분집합을 확인할 수 있다.
        //true와 false로 구분하여 부분집합을 만든다.
        return;
    }
    
    save[i] = true;//방문한경우
    powerset(arr, save, idx+1);
    save[i] = false;//방문안한경우
    powerset(arr, save, idx+1);
}