두 가지 전체 배열 (중복수와 무중복수) 의 귀속 실현

1522 단어 Algorithm
1. 중복수가 없습니다. 예: abc, 출력: abc\acb\bac\bca\cab\cba.
분석: 순서는 매번 알파벳을 첫 번째 문자로 취하고 뒤의 하위 문자열은 이 과정을 반복하며 전형적인 귀착이다.
2. 중복수가 있습니다. 예: abb, 출력: abb\bab\bba
분석: 교환 여부를 판단하는 함수 isSwap()을 추가하여 122, 첫 번째 수 1과 두 번째 수 2를 교환하여 212를 얻은 다음에 첫 번째 수 1과 세 번째 수 2를 교환하는 것을 고려한다. 이때 세 번째 수는 두 번째 수와 같기 때문에 첫 번째 수는 세 번째 수와 교환하지 않는다.212를 고려하면 두 번째 수와 세 번째 수의 교환은 해결될 수 있다.이 때 전체 배열이 생성됩니다.이렇게 해서 우리는 전체 배열에서 중복을 없애는 규칙을 얻었다. 중복을 없애는 전체 배열은 첫 번째 숫자부터 각 숫자가 그 뒤에 중복되지 않은 숫자와 교환되는 것이다.프로그래밍으로 설명하면 i수와 j수를 교환할 때 [i, j) 중 j수와 같은 수가 없도록 요구합니다.
코드:
package bytedance.bytedance;
import java.util.Arrays;
import java.util.Collections;
// , , isSwap 
public class AllSort {
    public static void permutation(char[] s,int from,int to) {
        if(to <= 1)
            return;
        if(from == to) {
            System.out.println(s);
        } else {
            for(int i=from; i<=to; i++) {
            if(isSwap(s,from,i)){// 
                swap(s,i,from); // , 
                permutation(s, from+1, to);
                swap(s,from,i); // , 
            }
            }
        }
    }
    public static void swap(char[] s,int i,int j) {
        char tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
    }
    public static void main(String[] args) {
        char[] s = {'c','b','b','c'};
        permutation(s, 0, 3);
    }
    private static boolean isSwap(char[] s,int i,int j){
        for (int k = i; k 

좋은 웹페이지 즐겨찾기