Combinatorics : 100 개 요소로 구성된 10 개의 그룹을 구축하는 반면 요소는 정렬 된 상태로 유지됩니다.

StackOverflow https://stackoverflow.com/questions/1351828

  •  20-09-2019
  •  | 
  •  

문제

조합에 관한 문제가 있습니다. 불행히도, 나는 그것을 추상적으로 설명 할 수 없으므로 이야기로 설명하려고 노력합니다. :)

문제:

  1. 학교에 100 명의 아이들이 있습니다.
  2. 값이 100-199cm라고 가정하면 모두 고유 한 높이를 가지고 있습니다.
  3. 각각 1-99 명의 어린이로 구성된 10 개의 그룹을 건설하려고합니다.
  4. 아이들이 키로 분류 해야하는 동안 어떻게 모든 그룹을 구축 할 수 있습니까?
  5. 하나의 별자리를 찾기가 어렵지 않기 때문에이 그룹에 대한 모든 가능한 솔루션이 필요합니다.

짧고 쉬운 :

100 명의 어린이 모두 나란히 서 있습니다. 그룹으로 분할 할 위치를 결정하고이를위한 모든 솔루션을 찾으면됩니다.

예제 (값은 높이) :

[120 ... 190 ... 199] ... [126 ... 137 ... 144 ... 188] 불가능합니다

[101] ... [104 ... 105 ... 112 ... 149] ... [169 ... 189] 가능합니다

나는 당신이 나를 도울 수 있기를 바랍니다. 미리 감사드립니다!

추신 : 숙제가 아닙니다. ;) 일반적으로 숫자로 이것을 수행하는 함수가 필요합니다. 그러나 나는 "모든 숫자가 분류되는 동안 숫자의 숫자를 구축하는 것"처럼 이것을 추상적으로 설명 할 수 없었습니다. 나는 당신이 이런 식으로 그것을 이해하지 못할 것이라고 생각했습니다. :) PHP의 솔루션이 가장 좋지만 다른 언어의 솔루션도 보게되어 기쁩니다. :)

도움이 되었습니까?

해결책

내가 이해할 수 있듯이, 당신은 간격 [100,199]을 10 부분으로 분할하는 방법을 효과적으로 요구하고 있습니다. 즉, 숫자 x [0], ..., x [10]을 찾으려고합니다.

x[0] = 100 < x[1] < x[2] < ... < x[9] < x[10] = 199

재귀 함수를 정의하십시오 partition(intervalSize, pieces) 주어진 간격을 분할하는 방법의 수를 계산합니다. 당신은 후에 있습니다 partition(100, 10).

다음 Java 코드는 파티션을 계산합니다 (죄송합니다. PHP를 잘 모릅니다).

public class Partitions
{
    static long[][] partitions = new long[100][10];

    private static long partition(int intervalSize, int pieces)
    {
        if (partitions[intervalSize-1][pieces-1] != 0) {
            return partitions[intervalSize-1][pieces-1];
        }
        long partition = 0L;
        if (pieces == 1) {
            partition = 1L;
        } else {
            for (int i = 1; i <= intervalSize - 1; i++) {
                partition += partition(intervalSize - i, pieces - 1);
            }
        }
        partitions[intervalSize-1][pieces-1] = partition;
        return partition;
    }

    public static void main(String[] args)
    {
        System.out.println(partition(100, 10));     
    }

}

다음 Java 코드는 실제 파티션을 인쇄합니다. 파티션의 수는 (100,10)에 너무 높기 때문에 (5,3)에 대한 답을 보여줍니다.

public class Partitions2
{
    private static void showPartitions(int sizeSet, int numPartitions)
    {
        showPartitions("", 0, sizeSet, numPartitions);
    }

    private static void showPartitions(String prefix, int start, int finish,
            int numLeft)
    {
        if (numLeft == 0 && start == finish) {
            System.out.println(prefix);
        } else {
            prefix += "|";
            for (int i = start + 1; i <= finish; i++) {
                prefix += i + ",";
                showPartitions(prefix, i, finish, numLeft - 1);
            }
        }
    }

    public static void main(String[] args)
    {
        showPartitions(5, 3);
    }
}

출력은 다음과 같습니다.

|1,|2,|3,4,5,
|1,|2,3,|4,5,
|1,|2,3,4,|5,
|1,2,|3,|4,5,
|1,2,|3,4,|5,
|1,2,3,|4,|5,

다른 팁

하나의 별자리를 찾기가 어렵지 않기 때문에이 그룹에 대한 모든 가능한 솔루션이 필요합니다.

일반적으로 100! 100 개 항목을 분출하는 방법이지만 주문을 보존하기 때문에 문제 크기를 줄일 수 있습니다. 대체로. 당신이 묘사하는 것은 정수 분할 문제. 예를 들어, 숫자 5를 가능한 모든 정수 서브 세트로 파티셔닝하고 있다고 가정 해 봅시다. ,}, {2, 2, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}.

정수 파티션의 수는 정수의 크기에 따라 기하 급수적으로 증가하지만, 지수 성장은 190,569,292 명에 불과하기 때문에 n = 100의 모든 파티션을 통해 열거 할 수있을 정도로 느리게 성장합니다. 여기서 추가적인 제약 조건은 정확히 10 개의 항목을 포함하는 세트에 대한 모든 파티션을 필터링하려는 것입니다. 이는 페러 다이어그램을 사용하여 쉽게 열거 할 수 있습니다.

숫자 20을 3 개의 버킷으로 분할하여 Ferrer 다이어그램을 시연 할 수 있습니다. 다음과 같이 20 col x 3 행 그리드로 시작하십시오.

 12345678901234567890
1******************
2*
3*

따라서 첫 번째 파티션은 {18, 1, 1}입니다.

이제 스택 상단에서 항목을 다음 슬롯으로 이동하십시오.

 12345678901234567890
1*****************
2**
3*

우리의 새로운 파티션은 {17, 2, 1}입니다. 한 스택에서 다른 스택으로 다른 항목을 사용할 수 있습니다.

 12345678901234567890
1****************
2***
3*

이제 {16, 3, 1}이 있습니다. 모든 순열을 열거 할 때 까지이 방식으로 계속됩니다 ({17, 1, 2}가 {17, 2, 1}의 뚜렷한 파티션인지 여부).

이 시점부터 필요한 알고리즘의 일반적인 개요를 구상 할 수 있어야합니다. 즉,이 기능을 처음부터 작성 해야하는 도전을 원한다면. 다른 사람들은 이미 가지고 있습니다 많은 효율적인 기능을 작성했습니다 문제를 쉽게 해결합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top