[알고리즘] java로 순열, 중복순열, 조합, 중복조합 구하기

java로 순열, 중복순열, 조합, 중복조합 구하기

기본 베이스는 LinkedList 로 구현하도록 했습니다.

더 자세한 설명을 원하실 경우 아래링크를 참고하세요~

2019/03/23 - [프로그래밍/Java] - [JAVA] 조합,중복조합,순열,중복순열 소스

 

아래는 전체 소스입니다.

 

package CASEOFNUMBER;

import java.util.LinkedList;
import java.util.Scanner;

public class CaseOfNumber2 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int r = sc.nextInt();
		
		int arr[] = new int[n];
		for(int i=1; i<=n; i++) arr[i-1] = i;
	
		LinkedList<Integer> list = new LinkedList<>();
		
		//순열
		//4C3 (3! : 6가지)
		
		int check[] = new int[n];
		System.out.println("****순  열****");
		permutation(list, check, n, r);
		list.clear();
		
		//중복순열
		System.out.println("****중복순열****");
		rePermutation(list, n, r);
		list.clear();
		
		//조합
		System.out.println("****조  합****");
		combination(list, n, r, 0);
		list.clear();
		
		//중복조합
		System.out.println("****중복조합****");
		reCombination(list, n, r, 0);

	}
	
    //중복조합
	private static void reCombination(LinkedList<Integer> list, int n, int r, int index) {
		if(r == 0){
			for(int i : list){
				System.out.print(i+" ");
			}
			System.out.println();
			return;
		}
		if(index == n) return;
		
		list.add(index);
		reCombination(list, n, r-1, index);
		list.removeLast();
		reCombination(list, n, r, index+1);
	}

	//조합
	private static void combination(LinkedList<Integer> list, int n, int r, int index) {
		if(r == 0){//r이 0이면 다 뽑았다는 뜻
			for(int i : list){
				System.out.print(i+" ");
			}
			System.out.println();
			return;
		}
		if(index == n) return; //다 탐색했으면 종료..
		
		list.add(index);
		combination(list, n, r-1, index+1);//뽑았으니 ,r-1
		list.removeLast();
		combination(list, n, r, index+1);//안뽑았으니, r
	}

	//중복순열
	private static void rePermutation(LinkedList<Integer> list, int n, int r) {
		if(list.size() == r){
			for(int i : list){
				System.out.print(i+" ");
			}
			System.out.println();
			return;
		}
		for(int i=0; i<n; i++){
			list.add(i);
			rePermutation(list, n, r);
			list.removeLast();//해당 넘버를 다시 제거 (즉,뽑지 않고 다음 번호 뽑기위함)
		
		}
		
	}

	//순열
	private static void permutation(LinkedList<Integer> list, int[] check, int n, int r) {
		if(list.size() == r){
			for(int i : list){
				System.out.print(i+" ");
			}
			System.out.println();
			return;
		}
		for(int i=0; i<n; i++){//**중복 순열과 다른 점
			if(check[i] == 0){//자기자신을 못뽑게 해야지 중복이 안됨(이미 뽑은 것은 뽑지 않도록 체크)
				check[i] = 1;//자기자신을 못뽑게 해야지 중복이 안됨
				list.add(i);
				permutation(list, check, n, r);
				list.removeLast();//해당 넘버를 다시 제거 (즉,뽑지 않고 다음 번호 뽑기위함)
				check[i] = 0;
			}
		}
		
	}

}

 

결과값

3과 2를 입력받는경우

 

3 2
***순열(0,1,2)***
0 1 
0 2 
1 0 
1 2 
2 0 
2 1 
***중복순열(0,1,2)***
0 0 
0 1 
0 2 
1 0 
1 1 
1 2 
2 0 
2 1 
2 2 
***조합(0,1,2)***
0 1 
0 2 
1 2 
***중복조합(0,1,2)***
0 0 
0 1 
0 2 
1 1 
1 2 
2 2