순열 & 조합

순열 & 조합 (Permutation & combination)

수를 나열함에 있어서 순서를 생각하느냐 아니냐에 따라 순열과 조합을 구분할 수 있다.

순열(nPr)

​ n개의 수에서 r개의 수를 뽑아 순서를 생각하고 나열하는 방법

• 반복문을 이용한 순열

public class Permutation {
    public static void main(String[] args) {
        int arr[] = {1,2,3};

        for (int i = 0; i < arr.length; i++) {
//            int i1=arr[i];
            for (int j = 0; j < arr.length; j++) {
//                int i2 = arr[j];
                if(i!=j) {
                    for (int k = 0; k < arr.length; k++) {
                        if(k!=i&&k!=j) {
                            System.out.println(arr[i]+" "+arr[j]+ " "+ arr[k]);
                        }
                    }
                }

            }

        }
    }
}

결과
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

• 재귀함수를 이용한 순열

  • swap을 이용한 재귀함수 구현

  public static void per(int n, int k) {
  
          if(k==n)
              System.out.println(Arrays.toString(arr));
          else {
              for (int i = k; i < n; i++) {
                  int temp=arr[i];
                  arr[i]=arr[k];
                  arr[k]=temp;
                  per(n,k+1);
                  temp=arr[i];
                  arr[i]=arr[k];
                  arr[k]=temp;
              }
          }
      }

  • list를 이용한 재귀함수 구현

  static void per2(int n, int k) {
          if(k==n) {
              System.out.println(al);
              return;
          }
          for(int i=0; i<n; i++) {
              if(visited[i]==0) {
                  visited[i]=1;
                  al.add(arr[i]);
  
                  per2(n, k+1);
                  al.remove(al.size()-1);
                  visited[i]=0;
              }
          }
      }

  visited 배열을 이용하 방문한 다음 수를 list에 추가하면서 나열을 표한하는 방식

  • nPr 구현

  public class Permutation2 {
      static int [] arr = {1,2,3,4,5};
      static int[] visited;
      static ArrayList<Integer> al = new ArrayList<>(); 
      public static void main(String[] args) {
          visited = new int[5];
          per2(5,0,3);
  
  

  static void per2(int n, int k, int r) {
      if(k==r) {//몇개를 뽑을건지를 결정
          System.out.println(al);
          return;
      }
      for(int i=0; i<n; i++) {
          if(visited[i]==0) {
              visited[i]=1;
              al.add(arr[i]);

              per2(n, k+1,r);
              al.remove(al.size()-1);
              visited[i]=0;
          }
      }
  }

  [1, 2, 3]
  [1, 2, 4]
  [1, 2, 5]
  . . .
  [5, 4, 1]
  [5, 4, 2]
  [5, 4, 3]

  - 중복 순열 구현

  ```java
  //순열에서 visited를 제거
  public class Permutation2 {
      static int [] arr = {1,2,3,4,5};
      static int[] visited;
      static ArrayList<Integer> al = new ArrayList<>(); 
      public static void main(String[] args) {
          visited = new int[5];
          per2(5,0,3);


      }

      static void per2(int n, int k, int r) {
          if(k==r) {//몇개를 뽑을건지를 결정
              System.out.println(al);
              return;
          }
          for(int i=0; i<n; i++) {
              al.add(arr[i]);                
              per2(n, k+1,r);
              al.remove(al.size()-1);            
          }
      }
  }

  1 [1, 1, 1]
  2 [1, 1, 2]
  3 [1, 1, 3]
  . . .
  123 [5, 5, 3]
  124 [5, 5, 4]
  125 [5, 5, 5]

조합(nCr)

​ 수를 순서를 고려하지 않고 나열

• 재귀함수를 이용한 조합

  • list를 이용한 조합

  static void com(int n, int k, int index) {
          if(k==3) {
              System.out.println(al);
              return;
          }
          for(int i=index; i<n; i++) {//k부터 시작을 하면서 순서를 고려 x
              if(visited[i]==0) {
                  visited[i]=1;
                  al.add(arr[i]);
  
                  com(n, k+1);
                  al.remove(al.size()-1);
                  visited[i]=0;
              }
          }
      }

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

• nCr 구현

  public static void comb(int n, int k, int index) {
      if(al.size()==k) {
            a++;
          System.out.println(a+" "+ al);
          return;
      }
      for(int i=index; i<n; i++) {
          if(visited[i]==0) {
              visited[i]=1;
              al.add(arr[i]);
              comb(n, k, i+1);
              al.remove(al.size()-1);
              visited[i]=0;
          }
     }
  }