Combinatorics : 100 개 요소로 구성된 10 개의 그룹을 구축하는 반면 요소는 정렬 된 상태로 유지됩니다.
-
20-09-2019 - |
문제
조합에 관한 문제가 있습니다. 불행히도, 나는 그것을 추상적으로 설명 할 수 없으므로 이야기로 설명하려고 노력합니다. :)
문제:
- 학교에 100 명의 아이들이 있습니다.
- 값이 100-199cm라고 가정하면 모두 고유 한 높이를 가지고 있습니다.
- 각각 1-99 명의 어린이로 구성된 10 개의 그룹을 건설하려고합니다.
- 아이들이 키로 분류 해야하는 동안 어떻게 모든 그룹을 구축 할 수 있습니까?
- 하나의 별자리를 찾기가 어렵지 않기 때문에이 그룹에 대한 모든 가능한 솔루션이 필요합니다.
짧고 쉬운 :
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}의 뚜렷한 파티션인지 여부).
이 시점부터 필요한 알고리즘의 일반적인 개요를 구상 할 수 있어야합니다. 즉,이 기능을 처음부터 작성 해야하는 도전을 원한다면. 다른 사람들은 이미 가지고 있습니다 많은 효율적인 기능을 작성했습니다 문제를 쉽게 해결합니다.