요약: 전체 배열 Permutation, 서브셋 subset 귀속 템플릿

두 개의 고전 귀속 템플릿, 이전에 썼던 것, 지금 다시 한 번!
기본 사고방식:
제목이 입력할 때 그룹을 입력하면 먼저 그룹을 Array List로 바꿔야 합니다. 왜냐하면 Array List는 쉽게 삽입, 삭제, 추가를 할 수 있기 때문입니다!
그 다음으로 귀속 함수의 형식은 모두 같다. 모두 3개의 매개 변수가 있는데 각각은ArrayListdone,ArrayListrest,ArrayList>ret이다.done는 처리된 데이터를 저장하고,rest는 아직 처리하지 않은 데이터를 저장하고,ret는 마지막 결과를 저장합니다.여기에서 Integer는 범용적이고 임의의 데이터 type이 될 수 있음을 주의하십시오.
구체적인 사고방식:
전체 배열: A[0,1,2,3...n]에 대해 매번 원소를 하나씩 꺼내서done에 추가한 다음,rest가 비어 있을 때까지 나머지rest에 귀속한다.그래서 전체적인 구조는 for순환 안에 하나가rest에서 데이터를 추출하고 귀속시키며 취소하는 과정이 있다.그래서 총괄적으로 말하자면, 매번 귀속할 때마다rest에서 데이터를 추출하여done에 순서대로 추가하는 것이다.
서브집합: 매번 rest의 첫 번째 요소를 꺼내서 done에 추가할지 여부를 결정합니다. 추가할 수도 있고 추가하지 않을 수도 있습니다. 그래서 두 개의 귀속이 있습니다.그래서 총괄적으로 말하면 매번 귀속할 때마다rest의 첫 번째 데이터를 취하고 두 가지 선택을 한다.

import java.util.*;

public class HelloWorld{

    public static void main(String []args){
        int[] A = {1,2,3};
        subset(A);
        permutation(A);
        
        
        String s = "abc";
        permutationStringRec(new StringBuilder(), new StringBuilder(s));
    }
     
    
    // ======================================================= permutation
    public static void permutation(int[] A) {
        ArrayList<Integer> rest = new ArrayList<Integer>();
        ArrayList<Integer> done = new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        
        for(int i : A) {
            rest.add(i);
        }
        
        permutationRec(done, rest, ret);
        System.out.println(ret);
    }
    
    public static void permutationRec(ArrayList<Integer> done, ArrayList<Integer> rest, ArrayList<ArrayList<Integer>> ret) {
        if(rest.size() == 0) {
            ret.add(new ArrayList<Integer>(done));
            return;
        }
        
        for(int i=0; i<rest.size(); i++) {
            int val = rest.get(i);      //  i ， done
            done.add(val);
            rest.remove(i);
            permutationRec(done, rest, ret);
            rest.add(i, val);
            done.remove(done.size()-1); 
        }
    }
    
    
    
    // ======================================================= subset
    public static void subset(int[] A) {
        ArrayList<Integer> rest = new ArrayList<Integer>();
        ArrayList<Integer> done = new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        
        for(int i : A) {
            rest.add(i);
        }
        
        subsetRec(done, rest, ret);
        System.out.println(ret);
    }
    
    public static void subsetRec(ArrayList<Integer> done, ArrayList<Integer> rest, ArrayList<ArrayList<Integer>> ret) {
        if(rest.size() == 0) {
            ret.add(new ArrayList<Integer>(done));
            return;
        }
        
        int first = rest.remove(0);

        //  done
        done.add(first);
        subsetRec(done, rest, ret);
        done.remove(done.size()-1);
        
        //  done
        subsetRec(done, rest, ret);
        
        
        rest.add(0, first);
    }
    
    
    
    
    
    // ======================================== permutationStringRec  StringBuilder 
    public static void permutationStringRec(StringBuilder done, StringBuilder rest){
        if(rest.length() == 0) {
            System.out.println(done.toString());
            return;
        }
        
        for(int i=0; i<rest.length(); i++) {
            char c = rest.charAt(i);
            done.append(c);
            rest.deleteCharAt(i);
            permutationStringRec(done, rest);
            rest.insert(i, c);
            done.deleteCharAt(done.length()-1);
        }
    }
    
    
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

요약: 전체 배열 Permutation, 서브셋 subset 귀속 템플릿

좋은 웹페이지 즐겨찾기