배열 과 조합 문제

배열 과 조합 문 제 는 알고리즘 에서 흔히 볼 수 있 는 문제 로 이 절 에서 우 리 는 흔히 볼 수 있 는 배열 과 조합 문 제 를 연구 할 것 이다.
(1) 주어진 숫자 자릿수 와 진법 으로 모든 조합 을 출력 합 니 다.
이 문제 에 대해 사람의 생각 에 따 르 면 숫자의 모든 위치 에 대해 끊임없이 값 을 선택 하 는 것 이다. 예 를 들 어 3 자리 2 진수 와 같이 우 리 는 먼저 가장 높 은 위 치 를 0 으로 취한 다음 에 다음 의 높 은 위 치 를 선택 하고 다음 의 높 은 위 치 를 선택 한 다음 에 가장 낮은 위 치 를 0 으로 한다. 이때 이미 모든 위치 에 대해 값 을 다 취하 고 직접 출력 하면 된다.모든 값 을 저장 하기 위해 서 는 배열 을 미리 설명 해 야 합 니 다.출력 이 끝 난 후에 가장 낮은 비트 가 모든 바 이 너 리 수 를 다 옮 겨 다 녔 다 면, 가장 높 은 비트 가 모든 진 수 를 옮 겨 다 닐 때 까지 다시 삭 제 됩 니 다.
프로그램 은 다음 과 같 습 니 다:

package com.majing.test;

public class test1 {
	
	public static void main(String[] args) 
	{
		print(3,2);
	}
	
	private static int[] array=null;
	public static void print(int n,int b)
	{
		assert n>0 && b>1;
		if(null==array)
		{
			array=new int[n];
		}
		print(n,n,b);
	}
	public static void print(int n,int cur,int b)
	{
		
		if(cur<=0)
		{
			for(int i=n-1;i>=0;i--)
			{
				System.out.print(array[i]);
			}
			System.out.println();
			return;
		}
		for(int i=0;i<b;i++)
		{
			array[cur-1]=i;
			print(n,cur-1,b);
		}
	}
}

테스트 결 과 는 다음 과 같다.

000
001
010
011
100
101
110
111

 
(2) N 개 수 를 정 하고 N 개 수의 전체 배열 을 출력 합 니 다 (N 개 수 는 각각 다 릅 니 다)
이 문제 에 대해 우 리 는 재 귀적 인 방식 으로 구 해 를 할 수 있다. 이 N 개 수 를 크기 가 N 인 배열 에 저장 하고 N 개의 수의 전체 배열 에 대해 우 리 는 이 를 N - 1 개의 수의 전체 배열 로 축소 할 수 있다. 구체 적 인 방법 은 이 N 개 수 를 모두 첫 번 째 숫자 와 교환 하 는 것 이다 (물론 첫 번 째 수 는 교환 할 필요 가 없다. 그들 둘 이 겹 치기 때문이다).예 를 들 어 1 과 2, 1 과 3,..............................................................................
프로그램:

/**
	 *   [1-n] N      
	 */
	private static int[] arrayfull={1,2,3,4};
	public static void printfull(int[] array)
	{
		assert array!=null && array.length!=0;
		printfull(arrayfull,arrayfull.length,0);
	}
	private static void printfull(int[] array,int n,int cur)
	{
		if(cur==n)
		{
			System.out.println(Arrays.toString(arrayfull));
			return;
		}
		for(int i=cur;i<n;i++)
		{
			swap(arrayfull,cur,i);
			printfull(arrayfull,n,cur+1);
			swap(arrayfull,cur,i);
		}
	}

	private static void swap(int[] array,int i,int j)
	{
		int tmp=array[i];
		array[i]=array[j];
		array[j]=tmp;
	}

실행 결 과 는 다음 과 같 습 니 다.

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 3, 2]
[1, 4, 2, 3]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 3, 1]
[2, 4, 1, 3]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 2, 3, 1]
[4, 2, 1, 3]
[4, 3, 2, 1]
[4, 3, 1, 2]
[4, 1, 3, 2]
[4, 1, 2, 3]

(3) N 개 수 에 대해 이 N 개 수의 전체 배열 을 구하 십시오. (숫자 는 중복 할 수 있 습 니 다)
이 문제 에 대해 저 는 위의 문제 보다 더 쉽다 고 생각 합 니 다. 모든 숫자 에 대해 가능 한 값 을 모두 옮 겨 다 니 면 됩 니 다. 여기 서 우 리 는 여전히 재 귀적 인 방식 을 사용 합 니 다.
프로그램:

/**
	 *  N      ，    
	 */
	private static int[] arrayfull2={1,2,3};
	public static void printfull2(int[] array)
	{
		assert array!=null && array.length!=0;
		int[] arr=new int[array.length];
		printfull2(array,arr,arrayfull2.length,0);
	
	}
	private static void printfull2(int[] array,int[] arr,int n,int cur)
	{
		if(cur==n)
		{
			System.out.println(Arrays.toString(arr));
			return;
		}
		for(int i=0;i<n;i++)
		{
			arr[cur]=array[i];
			printfull2(arrayfull2,arr,n,cur+1);
		}
	}

실행 결과:

[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 2, 1]
[1, 2, 2]
[1, 2, 3]
[1, 3, 1]
[1, 3, 2]
[1, 3, 3]
[2, 1, 1]
[2, 1, 2]
[2, 1, 3]
[2, 2, 1]
[2, 2, 2]
[2, 2, 3]
[2, 3, 1]
[2, 3, 2]
[2, 3, 3]
[3, 1, 1]
[3, 1, 2]
[3, 1, 3]
[3, 2, 1]
[3, 2, 2]
[3, 2, 3]
[3, 3, 1]
[3, 3, 2]
[3, 3, 3]

(4) 미 완성 계속...