순열 VS 조합 vs 부분집합 코드

순열

서로 다른 n개의 원소 중에서 "중복을 허락하지 않고", "순서를 생각"하며 r개를 일렬로 나열하는 수열

출처: https://data-make.tistory.com/493 [Data Makes Our Future:티스토리]

static void perm(int depth)
	{
		if(depth==N)
		{
			//System.out.println(Arrays.toString(result));
			//return result;
			return;
		}
		
		for(int i=0;i<N;++i)
		{
			if(!visit[i])
			{
				result[depth]=arr[i];	//depth를 인덱스로 써라
				visit[i]=true;
				comb(depth+1);
				visit[i]=false;
			}
		}
		
		
	}

 

 

조합

서로 다른 n개의 원소 중에서 "중복을 허락하지 않으며" "순서를 생각하지 않고" r개를 택할 때

출처: https://data-make.tistory.com/493 [Data Makes Our Future:티스토리]

/*
	 * r : nCr의 r, r만큼 result배열 생성해라.
	 * 
	 * 
	 */
	static void comb(int depth, int start)
	{
		//result= new int[result.length][2];
		r=result.length;
		if(depth==r) 
		{
			//할일
			return;
		}
		
		for(int i=start;i<arr.length;++i)
		{
			result[depth]=arr[i];
			comb(depth+1,i+1);
		}

	}

 

부분집합

공집합을 포함한 모든 원소의 경우의 수를 의미한다. 

집합의 원소가 N개일 때, 공집합을 포함한 부분집합의 수는 2^N개

출처: https://data-make.tistory.com/493 [Data Makes Our Future:티스토리]

public static void generateSubset(int depth) 
{    
	if(depth == N) 
    {        
        for (int i = 0; i < N; i++) 
        {            
            System.out.print(isSelected[i] ? input[i] : "X");            
            System.out.print("\t");        
        }        
        System.out.println();        
        return;    
    }     
    
    // 부분집합 구성에 포함    
    isSelected[depth] = true;    
    generateSubset(depth + 1);    // 다음 원소로 넘어감    
    // 부분집합 구성에 미포함    
    isSelected[depth] = false;    
    generateSubset(depth + 1);    // 다음 원소로 넘어감
}