Combinatoria: Construindo 10 grupos de 100 elementos enquanto os elementos permanecem classificados

Question

Eu tenho um problema sobre a combinatória. Infelizmente, não posso descrevê -lo abstrato, então tento explicá -lo como uma história. :)

Problema:

1. Existem 100 crianças no pátio da escola.
2. Todos eles têm alturas únicas, assumindo que os valores sejam 100-199 cm.
3. Você deseja construir 10 grupos, cada um composto por 1-99 crianças.
4. Como você pode construir todos os grupos enquanto as crianças devem ser classificadas por sua altura?
5. Preciso de todas as soluções possíveis para esses grupos, pois não é difícil encontrar uma constelação.

Curto e fácil:

Todas as 100 crianças estão lado a lado. Você só precisa decidir onde dividi -los em grupos e encontrar todas as soluções para isso.

Exemplo (valores são as alturas):

[120 ... 190 ... 199] ... [126 ... 137 ... 144 ... 188] não é possível

[101] ... [104 ... 105 ... 112 ... 149] ... [169 ... 189] é possível

Espero que você possa me ajudar. Muito obrigado antecipadamente!

PS: Não é lição de casa. ;) Normalmente, preciso de uma função que faça isso com números. Mas não pude descrever isso abstrivelmente como "construir grupos K de números enquanto todos os números são classificados". Eu pensei que você não entenderia dessa maneira. :) Uma solução no PHP seria melhor, mas eu ficaria feliz em ver soluções em outros idiomas também. :)

Answer 1

Pelo que entendi, você está efetivamente pedindo maneiras de particionar o intervalo [100.199] em 10 partes, ou seja, você quer encontrar números x [0], ..., x [10] tal que:

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

Defina uma função recursiva partition(intervalSize, pieces) que conta o número de maneiras de particionar um determinado intervalo. Você está atrás partition(100, 10).

O código Java a seguir conta as partições (desculpe, não conheço o PHP tão bem):

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));     
    }

}

O código Java a seguir imprime as partições reais. Como o número de partições é tão alto para (100,10), estou ilustrando a resposta para (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);
    }
}

A saída é:

|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,

Answer 2

Preciso de todas as soluções possíveis para esses grupos, pois não é difícil encontrar uma constelação.

Normalmente, aí 100! Maneiras de permitir 100 itens, mas como você está preservando o pedido, você pode reduzir o tamanho do seu problema para baixo substancialmente. O que você está descrevendo é um Problema de particionamento inteiro. Por exemplo, digamos que você estivesse particionando o número 5 em todos os subconjuntos inteiros possíveis que somam até 5, você obteria os conjuntos {5}, {4, 1}, {3, 2}, {3, 1, 1 ,}, {2, 2, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}.

O número de partições inteiras cresce exponencialmente com o tamanho do número inteiro, mas o crescimento exponencial é lento o suficiente para que você possa enumerar em todas as partições de n = 100, pois existem apenas 190.569.292 deles. A restrição adicional aqui é que você deseja filtrar todas as suas partições para conjuntos contendo exatamente 10 itens, o que é fácil de enumerar usando um diagrama Ferrer.

Eu posso demonstrar um diagrama de Ferrer por particionar o número 20 em 3 baldes: comece com uma grade de 20 cols x 3 linhas da seguinte forma:

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

Então, a primeira partição é {18, 1, 1}

Agora mova um item do topo da pilha para o próximo slot:

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

Nossa nova partição é {17, 2, 1}. Podemos outro item de uma pilha para a outra:

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

Agora temos {16, 3, 1}. Você continua dessa maneira até enumerar todas as permutações (cabe a você se {17, 1, 2} é uma partição distinta de {17, 2, 1}).

A partir deste ponto, você poderá imaginar o esboço geral do algoritmo necessário - ou seja, se você quiser o desafio de escrever essa função do zero. Outras pessoas já fizeram Escrito muitas funções eficientes para resolver o problema facilmente.