전체 배열, 조합 (문자열 또는 숫자) 사전 순서

1808 단어
중복 문자가 없는 전체 배열과 조합 수량 문제(이런 문제는 일반적으로 귀속으로 문제를 1+n-1로 분해하고 n-1부분에 대해 계속 귀속으로 분해한다)
  • 조합: n자의 조합수는 2^n종으로 각각 빈 집합, 1자의 n종, 2자의 n(n-1)/2종...더하기
  • 전체 배열: n 자 이내, 12...*n종 = n!

  • 조합: 각 문자는 한 조합에서 나타날 수도 있고 나타나지 않을 수도 있기 때문에 한 문자에 대해 상태는 0 또는 1, 0비트가 나타나지 않고 1비트가 나타납니다.따라서 2진법으로 대표되는 숫자로 조합의 모든 해석을 실현할 수 있다
    예를 들어 abc,000은 공중집합을 나타내고 001은 a,010은 b,011은 ab->이런 질서정연한 조합을 모두 구하고 시간 복잡도 O(n*2^n)를 나타낸다.
    public static  void Combination( ) {
            String str = "abc";
            int n = str.length();
            int counts= 1<

    전체 배열 귀속 방식: 주로 문자열에 중복된 문자가 없는 배열 문제에 사용되며, 각 문자는 배열에 나타나지만 위치는 다르다.첫 번째 문자는 변하지 않고 뒷부분의 문자열을 모두 배열하여 한 번에 뒤의 각 문자로 귀속시켜 모든 배열을 얻을 수 있다.
    예를 들어 abc, a는 abc, acb를 얻을 수 있다.b와 a를 교환한 후bac,bca,c와 a를 교환하면 cba,cab를 얻는다
    비귀속 방식: 모든 배열을 풀고 규칙이 순환하는 것을 발견하여 이번 배열의 다음 사전 서열의 배열을 찾아내면 중복 문자의 배열 문제를 해결할 수 있습니다. 이때 배열 수량은 n보다 적습니다!
    현재 배열된 마지막 정렬 대 AB(위치는 i, i+1)를 찾을 때마다 끝에서 앞으로 A보다 큰 첫 번째 문자 C를 찾아 AC 교환 위치를 찾습니다. 이때 i 뒤의 전체 하위 열을 i의 뒤에 거꾸로 연결하면 다음 사전 배열의 문자열을 얻을 수 있습니다.이 방법을 이용하면 사전 서열의 전체 배열 문제를 해결할 수 있다. 예를 들어 12354->12453->12435, 알 수 있듯이 12435 사전 서열에 따라 12354 뒤에 있는 배열이다.
    // 
    class Solution{
        public static void main(String args[]) throws Exception { 
            String s = "abc";
            String result = "";
            permutation(s, result, s.length());
        }
    
        public static void permutation(String str ,String result ,int len){
            if(result.length()==len){
                System.out.println(result);
            }
            else{
                // , 
                for(int i=0;i

    좋은 웹페이지 즐겨찾기