속성에 의해 순서대로 조합을 생성합니다

https://stackoverflow.com/questions/523800

22-08-2019
|

문제

단일 속성으로 순서 대상 객체의 조합을 생성하는 방법을 찾고 있습니다. 나는 사전 명령 순서가 내가 찾고있는 것이라고 생각하지 않습니다 ... 예를 들어 보려고 노력할 것입니다. 3,3,2,1로 주문하고 싶은 속성 값이있는 객체 A, B, C, D의 목록이 있다고 가정 해 봅시다. 이것은 A3, B3, C2, D1 객체를 제공합니다. 이제 2 개의 객체의 조합을 생성하고 싶지만 내림차순으로 주문해야합니다.

A3 B3
A3 C2
B3 C2
A3 D1
B3 D1
C2 D1

실제 조합을 생성하고 정렬하는 것은 허용되지 않습니다. 실제 시나리오에는 큰 세트와 수백만 개의 조합이 포함되기 때문입니다. (40 세트, 순서), 특정 임계 값 이상의 조합 만 필요합니다.

실제로 주어진 속성의 합으로 그룹화 된 임계 값 이상의 조합 수가 필요하지만, 훨씬 더 어렵다고 생각합니다. 그래서 나는 임계 값 이상의 모든 조합을 개발하고 계산하기 위해 정착합니다. 가능하다면 가능하다면.

편집 - 내 원래 질문은 그다지 정확하지 않았습니다 ... 실제로 주문한 조합이 필요하지 않습니다. 단지 임계 값 이상의 조합을 분리하는 데 도움이 될 것이라고 생각했습니다. 위의 예에서 5의 임계 값을 더 정확하게 말하면, 주어진 세트가 6 (a3 b3)의 합으로 1 개의 조합을 생성한다는 정보를 찾고 있습니다. B3 C2). 나는 실제로 조합 자체가 필요하지 않습니다.

하위 집합 문제를 조사하고 있었지만 동적 솔루션을 올바르게 이해하면 정보 만 제공 할 수 있습니다.

감사

해결책

사실, 나는 당신을 생각합니다 하다 사전 순서를 원하지만 오름차순보다는 내림차순을 원합니다. 게다가:

A, B, ... D는 귀하의 답변에서 어떤 역할을 수행한다는 것이 귀하의 설명에서 나에게 명확하지 않습니다 (값의 컨테이너 제외).
귀하의 질문 예제는 단순히 "각 정수에 대해 최소 5 개, 최대 2 값의 최대까지, 세트 {3, 3, 2, 1}의 고유 한 쌍이 그 정수의 합이 있습니까?"라고 생각합니다.
흥미로운 부분은 초기 구제 금융입니다. 일단 가능한 솔루션에 도달 할 수없는 경우 (남은 성취 가능한 금액은 너무 작습니다).

~~나중에 샘플 코드를 게시하겠습니다.~~

다음은 내가 약속 한 샘플 코드입니다. 다음은 다음과 같습니다.

public class Combos {

    /* permanent state for instance */
    private int values[];
    private int length;

    /* transient state during single "count" computation */
    private int n;
    private int limit;
    private Tally<Integer> tally;
    private int best[][];  // used for early-bail-out

    private void initializeForCount(int n, int limit) {
        this.n = n;
        this.limit = limit;
        best = new int[n+1][length+1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= length - i; ++j) {
                best[i][j] = values[j] + best[i-1][j+1];
            }
        }
    }

    private void countAt(int left, int start, int sum) {
        if (left == 0) {
            tally.inc(sum);
        } else {
            for (
                int i = start;
                i <= length - left
                && limit <= sum + best[left][i];  // bail-out-check
                ++i
            ) {
                countAt(left - 1, i + 1, sum + values[i]);
            }
        }
    }

    public Tally<Integer> count(int n, int limit) {
        tally = new Tally<Integer>();
        if (n <= length) {
            initializeForCount(n, limit);
            countAt(n, 0, 0);
        }
        return tally;
    }

    public Combos(int[] values) {
        this.values = values;
        this.length = values.length;
    }

}

서문 비고 :

이것은 Tally라는 작은 도우미 클래스를 사용하여 표를 분리합니다 (전혀 보지 않는 키에 대한 초기화 포함). 끝에 넣을 게요.

이 간결하게 유지하기 위해 "실제"코드에 대한 모범 사례가 아닌 바로 가기를 가져 왔습니다.

이것은 null 값 배열 등을 확인하지 않습니다.
값 배열은 이미 초기 베일 아웃 기술에 필요한 하강 순서로 정렬되었다고 가정합니다. (좋은 생산 코드에는 정렬이 포함됩니다.)
과도 데이터를 인스턴스 변수에 넣는 대신 인스턴스 변수를 지원하는 개인 방법 중에 인수로 전달합니다. count. 그것은이 클래스를 비 스레드 안전을 만듭니다.

설명:

인스턴스 Combos 결합 할 정수의 (내림차순) 배열로 만들어집니다. 그만큼 value 배열은 인스턴스 당 한 번 설정되지만 여러 통화 count 인구 규모와 한계로 다양한 인구 규모로 만들 수 있습니다.

그만큼 count 메소드는 (대부분) 고유 한 조합의 표준 재귀 횡선을 트리거합니다. n 정수 values. 그만큼 limit 인수는 관심의 합계에 대한 하한을 제공합니다.

그만큼 countAt 방법은 정수의 조합을 검사합니다 values. 그만큼 left 논쟁은 얼마나 많은 정수가 여전히 구성 해야하는지입니다 n 합계의 정수, start 위치입니다 values 검색 할 때 sum 부분 합계입니다.

초기 베일 아웃 메커니즘은 컴퓨팅을 기반으로합니다 best, 주어진 상태에서 도달 할 수있는 "최고"합계를 지정하는 2 차원 배열. 값 best[n][p] 가장 큰 합계입니다 n 위치에서 시작하는 가치 p 원본의 values.

재귀 countAt 올바른 모집단이 축적되었을 때 바닥; 이것은 전류를 추가합니다 sum (의 n 값)에게 tally. 만약에 countAt 바닥이 나오지 않고 쓸어냅니다 values ~로부터 start-현재 부분을 증가시키는 위치 sum, 하는 한:

충분한 위치가 남아 있습니다 values 지정된 모집단을 달성하기 위해
그만큼 best (가장 큰) 남은 나머지는 limit.

질문 데이터와 함께 실행되는 샘플 :

    int[] values = {3, 3, 2, 1};
    Combos mine = new Combos(values);
    Tally<Integer> tally = mine.count(2, 5);
    for (int i = 5; i < 9; ++i) {
        int n = tally.get(i);
        if (0 < n) {
            System.out.println("found " + tally.get(i) + " sums of " + i);
        }
    }

지정한 결과를 생성합니다.

found 2 sums of 5
found 1 sums of 6

다음은 탈리 코드입니다.

public static class Tally<T> {
    private Map<T,Integer> tally = new HashMap<T,Integer>();
    public Tally() {/* nothing */}
    public void inc(T key) {
        Integer value = tally.get(key);
        if (value == null) {
            value = Integer.valueOf(0);
        }
        tally.put(key, (value + 1));
    }
    public int get(T key) {
        Integer result = tally.get(key);
        return result == null ? 0 : result;
    }
    public Collection<T> keys() {
        return tally.keySet();
    }
}

다른 팁

나는 이항 계수로 작업하기위한 일반적인 기능을 처리하기위한 수업을 작성했습니다. 이는 문제가 발생하는 문제의 유형입니다. 다음과 같은 작업을 수행합니다.

모든 k-indexes를 모든 k-indexes를 좋은 형식으로 출력하여 모든 n을 파일에 선택합니다. K- 인덱스는보다 설명적인 문자열 또는 문자로 대체 될 수 있습니다. 이 방법은 이러한 유형의 문제를 매우 사소하게 만듭니다.
K- 인덱스를 분류 된 이항 계수 테이블에서 항목의 적절한 색인으로 변환합니다. 이 기술은 반복에 의존하는 구형 출판 기술보다 훨씬 빠릅니다. 파스칼의 삼각형에 내재 된 수학적 특성을 사용하여이를 수행합니다. 내 논문은 이것에 대해 이야기합니다. 나는이 기술을 처음 발견하고 출판 한 사람이라고 믿지만 틀릴 수 있습니다.
정렬 된 이항 계수 테이블에서 인덱스를 해당 K- 인덱스로 변환합니다.
용도 마크 도미너스 이항 계수를 계산하는 방법, 오버플로가 훨씬 적고 더 많은 숫자로 작동합니다.
이 클래스는 .NET C#로 작성되며 일반 목록을 사용하여 문제 (있는 경우)와 관련된 객체를 관리하는 방법을 제공합니다. 이 클래스의 생성자는 true가 관리 할 객체를 보유 할 일반 목록을 작성하는 inittable이라는 부울 값을 취합니다. 이 값이 False 인 경우 테이블을 생성하지 않습니다. 위의 4 가지 방법을 수행하기 위해 테이블을 만들 필요가 없습니다. 테이블에 액세스하기 위해 액세서 방법이 제공됩니다.
클래스를 사용하는 방법과 그 방법을 보여주는 관련 시험 클래스가 있습니다. 그것은 2 건으로 광범위하게 테스트되었으며 알려진 버그는 없습니다.

이 수업에 대해 읽고 코드를 다운로드하려면 이항 계수를 정제합니다.

StackoverFlow 에서이 질문을 확인하십시오. 모든 조합을 반환하는 알고리즘에스

또한 방금 아래의 Java 코드를 사용하여 모든 순열을 생성했지만 고유 한 조합을 생성하는 데 쉽게 사용할 수 있습니다.

public static <E> E[] permutation(E[] s, int num) {//s is the input elements array and num is the number which represents the permutation

    int factorial = 1;

    for(int i = 2; i < s.length; i++)
        factorial *= i;//calculates the factorial of (s.length - 1)

    if (num/s.length >= factorial)// Optional. if the number is not in the range of [0, s.length! - 1] 
        return null;

    for(int i = 0; i < s.length - 1; i++){//go over the array

        int tempi = (num / factorial) % (s.length - i);//calculates the next cell from the cells left (the cells in the range [i, s.length - 1])
        E temp = s[i + tempi];//Temporarily saves the value of the cell needed to add to the permutation this time 

        for(int j = i + tempi; j > i; j--)//shift all elements to "cover" the "missing" cell
            s[j] = s[j-1];

        s[i] = temp;//put the chosen cell in the correct spot

        factorial /= (s.length - (i + 1));//updates the factorial

    }

    return s;
}

이 문제에 대한 효율적인 솔루션을 찾을 수 없다고 말하면서 (의견의 모든 설명을 한 모든 의견을 마친 후) 매우 죄송합니다. 나는 지난 1 시간 동안 결과없이 시도했다.

그 이유는이 문제가 여행 세일즈맨 문제와 같은 문제와 매우 유사하기 때문입니다. 모든 조합을 시도하지 않으면 어떤 속성이 임계 값에 추가 될지 알 수있는 방법이 없습니다.

이 클래스의 문제를 해결할 수있는 영리한 트릭은없는 것 같습니다.

여전히 실제 코드에 대해 할 수있는 많은 최적화가 있습니다.

속성에 따라 데이터를 정렬하십시오. 더 높은 값이 임계 값을 만족시킬 수 없다는 것을 알게되면 목록에서 일부 값을 처리하지 않을 수 있습니다 (따라서 모든 낮은 값을 제거 할 수 있음).

C#을 사용하는 경우 상당히 좋은 제네릭 라이브러리가 있습니다. 여기. 일부 순열의 생성은 사전 순서가 아닙니다.

여기에 대한 재귀적인 접근 방식이 있습니다 세다 이러한 하위 집합의 수 : 기능을 정의합니다. count(minIndex,numElements,minSum) 크기의 서브 세트 수를 반환합니다 numElements 누구의 금액입니다 minSum, 인덱스가있는 요소를 포함합니다 minIndex 또는 더 큰.

문제 설명에서와 같이, 우리는 요소를 내림차순 순서 (예 : [3,3,2,1)로 분류하고 첫 번째 인덱스 0을 호출하고 총 요소 N을 호출합니다. 합계가 5 이상인 2 개의 서브 세트를 모두 찾으려면 count(0,2,5).

샘플 코드 (자바):

int count(int minIndex, int numElements, int minSum)
{
    int total = 0;

    if (numElements == 1)
    {
        // just count number of elements >= minSum
        for (int i = minIndex; i <= N-1; i++)
            if (a[i] >= minSum) total++; else break;
    }
    else
    {
        if (minSum <= 0)
        {
            // any subset will do (n-choose-k of them)
            if (numElements <= (N-minIndex))
                total = nchoosek(N-minIndex, numElements);
        }
        else
        {
            // add element a[i] to the set, and then consider the count
            // for all elements to its right
            for (int i = minIndex; i <= (N-numElements); i++)
                total += count(i+1, numElements-1, minSum-a[i]);
        }
    }

    return total;
}

BTW, 나는 40 개의 요소와 Size-8 서브 세트로 위의 위를 실행하고 일관되게 1 초도 안되는 결과를 얻었습니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow