어떻게 자바 로 배열 조합 알고리즘 을 실현 합 니까?

수요
우리 의 데이터 시트 는 여러 차원 이 있 습 니 다.여러 차원 으로 조합 한 후에 group by 를 진행 하면'기묘 한'반응 을 일 으 킬 수 있 습 니 다.어떻게 조합 하 는 지 확실 하지 않 기 때문에 모든 조합 을 열거 하여 시도 해 야 합 니 다.
추상 적 으로 말하자면 하나의 집합 에서 임의의 원 소 를 꺼 내 유일한 조합 을 형성 하 는 것 이다.예 를 들 어[a,b,c]는[a],[b],[c],[ab],[bc],[ac],[bc]로 조합 할 수 있다.
요 구 는 다음 과 같 습 니 다.
4.567917.조합 안의 요소 수 는 0 보다 크 면 배열 의 크기 보다 작다4.567917.조합 안에 중복 요소 가 있어 서 는 안 된다.예 를 들 어[aab]는 요구 에 부합 되 지 않 는 조합 이다4.567917.조합 내 요소 의 위 치 는 자 유 롭 습 니 다.즉,[ab]와[ba]는 같은 조합 으로 간주 합 니 다여기 서 보면 고등학교 에서 배 운 배열 조합 을 생각해 야 한다.마찬가지 로 집합 에서 요 소 를 꺼 내 다른 집합 을 형성 하 는 것 이다.만약 에 집합 안의 요소 위치 가 자 유 롭 게 되면 조합 이다.b 개의 요소 에서 a 개의 요 소 를 추출 하 는 조합 은 일종 이다.만약 에 요소 의 순서 가 다 르 고 서로 다른 집합 으로 간주한다 면 배열 이다.m 개 원소 에서 n 개 원소 의 배열 은 종류 가 있다.
내 가 만난 이 수 요 는 바로 전형 적 인 조합 이다.공식 적 으로 보면 요소 의 개수 가 n 인 집합 에서 조합 을 나타 내 는 것 이다.
배열 에서 조합 까지.-궁 거.
이런 수요 에 대해 가장 먼저 생각 나 는 것 은 당연히 궁 거 다.배열 의 요구 가 비교적 적 기 때문에 실현 이 더욱 간단 하 다.만약 에 내 가 먼저 모든 배열 을 찾 은 다음 에 위치 가 다 르 기 때문에 중복 되 는 요 소 를 제거 하면 수 요 를 실현 할 수 있다.만약 에[A B C D E]다섯 가지 요소 에서 모든 조합 을 꺼 내야 한다 고 가정 하면 우 리 는 먼저 모든 요소 의 전체 배열 을 찾 은 다음 에 유사 한[A B]와[B A]두 가지 집합 을 다시 하면 된다.
우 리 는 또 알 고 있다.그러면 우 리 는 먼저 한 가지 상황 을 고려 해 보 자.가설 은 다섯 개의 요소 중에서 세 개 를 골 라 서 전체 배열 을 하 는 것 이다.
선 택 된 세 가지 요 소 는 각각 ABCDE 중 하나 가 될 수 있 고 형 성 된 집합 에서 중복 요소 가 있 는 것 을 제외 하면 5 선택 3 의 전체 배열 이다.
코드 는 다음 과 같 습 니 다:

private static Set<Set<String>> exhaustion() {
    List<String> m = Arrays.asList("a", "b", "c", "d", "e");
    Set<Set<String>> result = new HashSet<>();
    int count = 3;
    for (int a = 1; a < m.size(); a++) {
        for (int b = 0; b < m.size(); b++) {
            for (int c = 0; c < m.size(); c++) {
                Set<String> tempCollection = new HashSet<>();
                tempCollection.add(m.get(a));
                tempCollection.add(m.get(b));
                tempCollection.add(m.get(c));
                //               Set   ，   Set       3
                if (tempCollection.size() == count) {
                    result.add(tempCollection);
                }
            }
        }
    }

    return result;
}

결과 조합의 무게 에 대해 저 는 자바 에서 HashSet 의 두 가지 특성 을 빌 렸 습 니 다.
4.567917.요소 의 유일 성 은 세 가지 요 소 를 선택 하여 Set 에 넣 으 면 중복 되 는 것 이 걸 러 집 니 다.그러면 집합 크기 를 통 해 중복 요소 가 있 는 지 판단 할 수 있 습 니 다

원소 의 무질서 성,Set[A B]와 Set[B A]는 모두 Set[A B]로 표 시 됩 니 다

또한 요소 의 유일 성 으로 인해 Set[A B]라 고 표 시 된 여러 개의 집합 은 하나만 보존 할 수 있 기 때문에 전체 배열 을 조합 으로 전환 하 는 데 도움 을 줄 수 있다

위의 프로그램 에서 count 인 자 는 죽 었 다 고 쓰 여 있 습 니 다.4 개의 요 소 를 꺼 내 려 면 4 층 순환 으로 끼 워 넣 어야 합 니 다.가 져 온 요소 가 가 변 적 이면 일반적인 인 코딩 방식 은 적합 하지 않 습 니 다.
주:가 변 층수 의 순환 은 재 귀 로 이 루어 질 수 있 습 니 다.
배열 에서 조합 까지.-분할.
궁 거 는 결국 너무 폭력 적 이기 때문에 우 리 는 분 치 사상 을 통 해 이 문 제 를 다시 한번 고려 해 보 자.
분 치 사상
분 치 된 사상 은 전체적으로 말 하면'큰 일 은 작 게 하고 작은 일 은 작 게 한다'는 것 이다.복잡 한 문 제 를 간단하게 구분 하고 직접적 으로 해결 할 수 있 는 문제 로 나 눌 때 까지 이 직접적 으로 해결 할 수 있 는 문제 에서 위로 모 아서 마지막 에 문 제 를 해결 하 는 것 이다.
M 개의 요소 에서 N 개의 요 소 를 추출 하 는 것 은 전체 문제 가 매우 복잡 하기 때문에 분 치 사상 으로 이해 할 수 있다.

우선,만약 에 우리 가 M 에서 원 소 를 하나 꺼 냈 다 면 집합 에 M-1 개가 남 았 고 필요 한 원 소 는 N-1 개 만 남 았 다

4.567917.아직 해결 되 지 않 으 면 우 리 는 M-1 에서 하나의 요 소 를 꺼 냈 다 고 가정 하고 집합 에 M-2 개가 남 았 으 며 취해 야 할 요 소 는 N-2 개 만 남 았 다4.567917.우리 가 M-N+1 번 을 취 했 을 때 까지 취해 야 할 요 소 는 하나 밖 에 남지 않 았 다.그리고 나머지 집합 에서 취 하 는 것 은 간단 한 문제 이다.간단 하 다.취 법 은 M-N+1 가지 가 있다4.567917.만약 에 우리 가 이 문 제 를 해결 했다 면 마지막 으로 M-N+1 가지 임시 집합 이 생 겼 고 M-N+2 개의 요소 에서 원 소 를 취 하 는 것 을 고려 하면 M-N+2 가지 가능성 도 있다4.567917.이런 것들 을 한 곳 에 모 아서 N 개의 요 소 를 얻 을 때 까지 이 문 제 는 해결 된다아니면 5 개의 요소 에서 3 개의 요 소 를 추출 하 는 예제 입 니까?
4.567917.5 개의 요소 에서 3 개의 요 소 를 추출 하 는 것 은 복잡 한 문제 이다.이 를 간소화 하기 위해 우 리 는 이미 하나의 요 소 를 추출 했다 고 생각한다.그리고 나머지 4 개의 요소 에서 2 개 를 추출 해 야 한다.구 해 공식 은 다음 과 같다4.567917.4 개의 요소 에서 2 개 를 꺼 내 는 것 은 여전히 해결 하기 어렵다.그러면 우 리 는 다시 하나의 요 소 를 꺼 냈 다 고 가정 하고 다음 문 제 는 어떻게 3 개의 요소 에서 하 나 를 꺼 내 는 지,공식 은..4.567917.세 가지 요소 중에서 하 나 를 취 하 는 것 은 이미 간단 한 문제 이다.세 가지 가능성 이 있 는데 다시 위로 거 슬러 올 라 가 4 에서 1,5 에서 1 을 취 하 는 가능성 과 곱 해서 이 문 제 를 해결한다코드 구현
코드 로 다음 과 같이 구현:

public class Combination {

    public static void main(String[] args) {
        List<String> m = Arrays.asList("a", "b", "c", "d", "e");
        int n = 5;

        Set<Set<String>> combinationAll = new HashSet<>();
        //            、   ...      
        for (int c = 1; c <= n; c++) {
            combinationAll.addAll(combination(m, new ArrayList<>(), c));
        }

        System.out.println(combinationAll);
    }

    private static Set<Set<String>> combination(List<String> remainEle, List<String> tempCollection, int fetchCount) {
        if (fetchCount == 1) {
            Set<Set<String>> eligibleCollections = new HashSet<>();
            //            ，                        
            for (String ele : remainEle) {
                Set<String> collection = new HashSet<>(tempCollection);
                collection.add(ele);
                eligibleCollections.add(collection);
            }
            return eligibleCollections;
        }

        fetchCount--;
        Set<Set<String>> result = new HashSet<>();
        //       ，          ，        ，     count--    。
        for (int i = 0; i < remainEle.size(); i++) {
            List<String> collection = new ArrayList<>(tempCollection);
            List<String> tempRemain = new ArrayList<>(remainEle);
            collection.add(tempRemain.remove(i));
            result.addAll(combination(tempRemain, collection, fetchCount));
        }
        return result;
    }
}

그 실현 은 바로 재 귀 이다.재 귀 와 분 치 에 관 해 관심 이 있 으 면 숨겨 진 편:재 귀 와 분 치 를 볼 수 있다.
직 격 본질-비트 연산
원소 의 전체 배열 에서 전체 조합 을 찾 는 것 이 궁 거 보다 약간 좋 지만 가장 좋 은 방법 은 아니다.왜냐하면 그것 은'한 번 돌 았 기 때문이다'.
많은 알고리즘 이 비트 연산 을 통 해 교묘 하 게 해결 할 수 있 는데 그 장점 은 주로 두 가지 가 있다.하 나 는 비트 연산 이 컴퓨터 에서 집행 효율 이 매우 높 고 다른 하 나 는 비트 연산 의 의미 가 간단 하기 때문에 알고리즘 은 대부분 본질 을 가리킨다.
조합 알고리즘 도 비트 연산 을 통 해 이 루어 질 수 있다.
사상
다시 한 번 전체 조합의 수 요 를 고려 하여 M 개의 요소 에서 임의의 요 소 를 취하 여 조합 을 이 루 고 조합 안의 요 소 는 중복 되 지 않 으 며 요소 의 위치 와 무관 하 다.
이전의 방법 은 모두 결과 조합 이 요 구 를 만족 시 키 는 지 여 부 를 고려 하고 조합 에 중복 요소 가 있 는 지,같은 조합 이 있 는 지 등 조건 을 고려 했다.생각 을 바 꾸 면 선택 할 요소 에서 고려 해 볼 까요?
모든 요소 에 있어 서 그 상 태 는 훨씬 간단 하 다.조합 에 넣 거나 조합 에 넣 지 않 는 다.모든 원 소 는 이렇게 두 가지 상태 가 있다.5 개의 요소 중에서 N 개의 요 소 를 임의로 조합 하면 모든 요소 가 조합 에 들 어 갈 지 여 부 를 바 이 너 리 로 표시 합 니 다.바로:
A  B  C  D  E
0  0  0  0  1   [E] = 1
A  B  C  D  E
0  0  0  1  0   [D] = 2
A  B  C  D  E
0  0  0  1  1   [DE] = 3
...
여기 서 보시 면 잘 아 시 겠 지만 모든 조합 은 N 개의 바 이 너 리 표현 형식 으로 분해 할 수 있 고 모든 바 이 너 리 조합 은 10 진 숫자 를 동시에 대표 하기 때문에 모든 10 진 숫자 는 하나의 조합 을 대표 할 수 있 습 니 다.
10 진법 숫자의 수 를 우 리 는 쉽게 계산 할 수 있 습 니 다.00000...부터 11111.................................................................
코드 구현
다음은 자바 코드 의 실현 입 니 다.

public class Combination {

    public static void main(String[] args) {
        String[] m = {"A", "B", "C", "D", "E"};
        Set<Set<String>> combinationAll = combination(m);
        System.out.println(combinationAll);

    }

    private static Set<Set<String>> combination(String[] m) {
        Set<Set<String>> result = new HashSet<>();

        for (int i = 1; i < Math.pow(2, m.length) - 1; i++) {
            Set<String> eligibleCollections = new HashSet<>();
            //       i   2^n    ，    n      1
            for (int j = 0; j < m.length; j++) {
                if ((i & (int) Math.pow(2, j)) == Math.pow(2, j)) {
                    eligibleCollections.add(m[j]);
                }
            }
            result.add(eligibleCollections);
        }
        return result;
    }
}

작은 매듭
배열 과 조합 알고리즘 은 실제 응용 에서 흔히 볼 수 있 고 그들의 실현 방법 도 참고 가치 가 있다.전체적으로 말 하면 배열 은 재 귀,조합 용 비트 연산 을 사용한다.
이상 은 자바 로 배열 조합 알고리즘 을 어떻게 실현 하 는 지 에 대한 상세 한 내용 입 니 다.자바 로 배열 조합 알고리즘 을 실현 하 는 데 관 한 자 료 는 우리 의 다른 관련 글 에 관심 을 가 져 주 십시오!