Classificar uma lista em várias colunas verticais

Question

Alguém tem um bom algoritmo para re-classificar uma matriz de valores (já pré-classificadas) para que eles possam ser exibidos em várias (N) colunas e ser lido verticalmente? Este seria implementado em .net, mas eu prefiro algo portátil e não uma função mágica.

Um bom exemplo de que trabalhar é a prestação de controle ASP.Net CheckBoxList como uma tabela com o conjunto de direção para vertical.

Aqui está um exemplo da entrada e saída:

Input:

Colunas = 4
Matriz = { "A", "B", "C", "D", "E", "F", "G"}

Output:

ACEG
BDF

Obrigado!

Atualização (Mais informações):

Eu acho que eu poderia ter de dar um pouco mais informações sobre o que eu estou tentando fazer ... Principalmente este problema surgiu a partir indo de usar um CheckBoxList automático de ligação (onde você pode especificar as colunas e direção para a saída e que seria de saída uma tabela de itens na ordem correta) para usando jQuery / AJAX para criar a grade de caixa de seleção. Então, eu estou tentando duplicar esse layout usando css com blocos div com larguras especificadas (dentro de um recipiente div de largura conhecida) para que eles embrulhar depois itens N (ou colunas.) Isso também poderia ser processado em uma tabela (como como ASP .net faz isso.)

Tudo funciona muito bem, exceto a ordem é horizontal e quando você recebe um grande número de itens na lista que é mais fácil de ler colunas verticais.

Se a matriz não tem itens suficientes no-lo para fazer uma grade mesmo assim ele deve saída um local vazio na linha / coluna correta da grade.

E se um array não tem elementos suficientes para fazer mesmo uma única linha, em seguida, apenas de saída os itens em sua ordem original em uma linha.

Alguns outra entrada / saída pode ser:

Colunas = 3
Matriz = { "A", "B", "C", "D"}

ACD
B

Colunas = 5
Matriz = { "A", "B", "C", "D", "E", "F", "G", "H"}

ACEGH
BDF

Colunas = 5
Matriz = { "A", "B", "C", "D"}

ABCD

Answer 1

Ok, eu sinto muito por minha declaração inicial, mas quando você quer que ele funcione como você descreveu no comentário à minha primeira resposta, você precisa de fato re-classificar os dados ... bem pouco. Ele poderia talvez ser feito sem a matriz ajudante, no entanto, o código resultante é provavelmente muito complexo e enquanto a matriz só vai usar um par de bytes de memória, por que não usar esta construção ajudante pouco?

O que o meu código faz abaixo é a criação de uma matriz. Nós escrevemos a matriz de cima para baixo e da esquerda para a direita (e parar de encher-se qualquer coisa, mas a primeira linha quando ficarmos sem elementos para preencher todas as colunas da primeira linha). Em seguida, lê-lo em uma ordem diferente, esquerda para a direita e de cima para baixo. Basicamente o que fazemos aqui é transposição de uma matriz , escrevendo-o em uma ordem, mas lê-lo em outra ordem. Transposição de uma matriz é uma operação matemática muito elementar (lotes de 3D programação obras usando cálculos matriciais e de transposição é na verdade uma operação simples). O truque é como nós inicialmente encher a matriz. Para se certificar de que pode encher a primeira coluna, em qualquer caso, independentemente do número de colunas e tamanho da matriz desejados, devemos parar de encher a matriz na ordem normal, se ficarmos sem elementos e reservar todos os elementos de sobra para o primeira linha. Isto produzirá a saída você sugeriu em seu comentário.

A coisa toda é pouco complicado para ser honesto, mas a teoria por trás deve ser sã e funciona linda :-D

int Columns;
char * Array[] = {"A", "B", "C", "D", "E", "F", "G"};

int main (
    int argc,
    char ** argv
) {
    // Lets thest this with all Column sizes from 1 to 7
    for (Columns = 1; Columns <= 7; Columns++) {

        printf("Output when Columns is set to %d\n", Columns);

        // This is hacky C for quickly get the number of entries
        // in a static array, where size is known at compile time
        int arraySize = sizeof(Array) / sizeof(Array[0]);

        // How many rows we will have
        int rows = arraySize / Columns;

        // Below code is the same as (arraySize % Columns != 0), but
        // it's almost always faster
        if (Columns * rows != arraySize) {
            // We might have lost one row by implicit rounding
            // performed for integer division
            rows++;
        }

        // Now we create a matrix large enough for rows * Columns
        // references. Note that this array could be larger than arraySize!
        char ** matrix = malloc(sizeof(char *) * rows * Columns);

        // Something you only need in C, C# and Java do this automatically:
        // Set all elements in the matrix to NULL(null) references
        memset(matrix, 0, sizeof(char *) * rows * Columns );

        // We fill up the matrix from top to bottom and then from
        // left to right; the order how we fill it up is very important
        int matrixX;
        int matrixY;
        int index = 0;
        for (matrixX = 0; matrixX < Columns; matrixX++) {
            for (matrixY = 0; matrixY < rows; matrixY++) {
                // In case we just have enough elements left to only
                // fill up the first row of the matrix and we are not
                // in this first row, do nothing.
                if (arraySize + matrixX + 1 - (index + Columns) == 0 &&
                        matrixY != 0) {
                    continue;
                }

                // We just copy the next element normally
                matrix[matrixY + matrixX * rows] = Array[index];
                index++;
                //arraySize--;
            }
        }

        // Print the matrix exactly like you'd expect a matrix to be
        // printed to screen, that is from left to right and top to bottom;
        // Note: That is not the order how we have written it,
        // watch the order of the for-loops!
        for (matrixY = 0; matrixY < rows; matrixY++) {
            for (matrixX = 0; matrixX < Columns; matrixX++) {
                // Skip over unset references
                if (matrix[matrixY + matrixX * rows] == NULL)
                    continue;

                printf("%s", matrix[matrixY + matrixX * rows]);
            }
            // Next row in output
            printf("\n");
        }
        printf("\n");

        // Free up unused memory
        free(matrix);
    }   
    return 0;
}

A saída é

Output when Columns is set to 1
A
B
C
D
E
F
G

Output when Columns is set to 2
AE
BF
CG
D

Output when Columns is set to 3
ADG
BE
CF

Output when Columns is set to 4
ACEG
BDF

Output when Columns is set to 5
ACEFG
BD

Output when Columns is set to 6
ACDEFG
B

Output when Columns is set to 7
ABCDEFG

Este código C deve ser fácil para a porta para PHP, C #, Java, etc., não há nenhuma grande mágica envolvida, por isso é praticamente universal, portátil e multi-plataforma.

---

Uma coisa importante que eu deveria acrescentar:

Este código irá falhar se você definir Colunas a zero (divisão por zero, eu não verificar isso), mas que sentido seria 0 Colunas fazer? E que também irá falhar se você tem mais colunas do que elementos na matriz, eu não verificar isso também. Você pode facilmente verificar se há qualquer direito depois que você tem o ArraySize:

if (Columns <= 0) {
   // Having no column make no sense, we need at least one!
   Columns = 1;
} else if (Columns > arraySize) {
   // We can't have more columns than elements in the array!
   Columns = arraySize;
}

Além disso, você também deve verificar para o ArraySize sendo 0, caso em que você pode saltar imediatamente da função, como, nesse caso, não há absolutamente nada a fazer para a função :) Adicionando estas verificações devem fazer a rocha código sólida.

Tendo elementos nulos na matriz vai funcionar, BTW, nesse caso, não há buracos na saída resultante. elementos nulos são apenas saltaram como não estar presente. Por exemplo. permite o uso

char * Array[] = {"A", "B", "C", "D", "E", NULL, "F", "G", "H", "I"};

A saída será

ADFI
BEG
CH

para Colunas == 4. Se você querem buracos , você precisa criar um elemento buraco.

char hole = 0;
char * Array[] = {"A", "B", &hole, "C", "D", "E", &hole, "F", "G", "H", "I"};

e modificar o código pintar um pouco

    for (matrixY = 0; matrixY < rows; matrixY++) {
        for (matrixX = 0; matrixX < Columns; matrixX++) {
            // Skip over unset references
            if (matrix[matrixY + matrixX * rows] == NULL)
                continue;

            if (matrix[matrixY + matrixX * rows] == &hole) {
                printf(" ");
            } else {
                printf("%s", matrix[matrixY + matrixX * rows]);
            }
        }
        // Next row in output
        printf("\n");
    }
    printf("\n");

amostras de saída:

Output when Columns is set to 2
A 
BF
 G
CH
DI
E

Output when Columns is set to 3
ADG
BEH
  I
CF

Output when Columns is set to 4
AC H
BDFI
 EG

Answer 2

Uma pequena UPDATE:

O algoritmo que estou usando aqui é uma modificação que você usaria para pintar imagens. Eu estou fingindo as entradas de matriz a ser dados de pixel de uma imagem e, em seguida, eu estou pintando a imagem da esquerda para a direita (1. LtoR) e de cima para baixo (2. TtoB), no entanto, os dados de imagem é armazenada a partir de cima para baixo (1. TtoB) e, em seguida, da esquerda para a direita (2. LtoR); IOW em uma ordem diferente. Uma vez que uma imagem não pode ter buracos , esta é a razão por que ele não irá trabalhar com 5 ou 6 colunas. Com 4 colunas a saída é

ACEG
BDF

Como uma imagem Isto parece este

OOOO
OOO.

Com o sendo um pixel da imagem e. sendo um pixel não definido (uma falta). que faltam só podem ser no final da imagem, não no meio dela. Isso significa que ele também pode ter esta aparência

OOO
OO.
OO.
OO.

Todos os pixels que faltam são sempre no final, se você ler início de cima para baixo e seguida, da esquerda para a direita, porque, nesse caso, todos os pixels que faltam siga diretamente uns aos outros no final. Se eu ler a TtoB diagrama e, em seguida, LtoR, deve ler como este "Pixel, Pixel, Pixel, Pixel, ..., Pixel, falta, falta, faltando, ..., Missing", que poderia nunca leu "Pixel, faltando, Pixel" ou "Missing, Pixel, faltando". Todos os pixels estão juntos e todos os desaparecidos são, também.

Com 5 colunas, como o comentário sugere, ele deve olhar como este

ACEFG
BD

No entanto, como esta imagem ficaria assim

OOOOO
OO...

E isso não é permitido pelo algoritmo. Se eu lê-lo TtoB e depois LtoR, ele irá ler: "Pixel, Pixel, Pixel, Pixel, Pixel, faltando, Pixel, faltando, Pixel, Missing". E como dito acima, isso não é permitido pelo algoritmo. Portanto, esta abordagem de pixel simples pintura não vai pintar as colunas solicitado se pintura que muitas colunas leva aos buracos na imagem. Nesse caso, ele vai simplesmente encher os buracos, no entanto, isso fará com que menos colunas a ser desenhado.

Deixe-me pensar em uma solução que sempre vai pintar os números solicitados de pixels (em uma resposta em separado).

---

Você não tem que re-organizar os dados na memória para que em tudo. Basta imprimi-lo na ordem desejada.

Alguns Código C (eu estou fazendo isso extremamente detalhado, então todo mundo entende o que eu estou fazendo isso Claro que isso pode ser muito mais compacto.):

int Columns = 4;
char * Array[] = {"A", "B", "C", "D", "E", "F", "G"};

int main (
    int argc,
    char ** argv
) {
    // This is hacky C for quickly get the number of entries
    // in a static array, where size is known at compile time
    int arraySize = sizeof(Array) / sizeof(Array[0]);

    // How many rows are we going to paint?
    int rowsToPaint = (arraySize / Columns) + 1;

    int col;
    int row;

    for (row = 0; row < rowsToPaint; row++) {
        for (col = 0; col < Columns; col++) {
            int index = col * rowsToPaint + row;

            if (index >= arraySize) {
                // Out of bounds
                continue;
            }

            printf("%s", Array[index]);
        }
        printf("\n"); // next row
    }
    printf("\n");
    return 0;
}

Nota: Esta multa trabalha com um valor de 8 (por isso tudo é pintado dentro de uma linha) e os valores de 4 e abaixo (funciona bem com 3, 2 e 1), mas pode não funcionar com 5. Este é não a falha do algoritmo, é culpa do constrangimento.

ACEFG
BD

A restrição diz que as colunas são lidas de cima para baixo para obter os dados corrigidos ordenados. Mas, acima de " EFG " é ordenada e não é de cima para baixo, é esquerda para a direita. Assim, este algoritmo tem um problema. Usando colunas = 3 vai funcionar

ADG
BE
CF

Usando dois vai funcionar tão bem

AE
BF
CG
D

E um vai colocar tudo em uma coluna.

Answer 3

Isto parece tarefas de casa de qualquer maneira

array<String^>^  sArray = {"A", "B", "C", "D", "E", "F", "G"};
double Columns = 4;
double dRowCount = Convert::ToDouble(sArray->Length) / Columns;
int rowCount = (int) Math::Ceiling(dRowCount);
int i = 0;
int shift = 0;
int printed = 0;
while (printed < sArray->Length){
    while (i < sArray->Length){
        if (i % rowCount == shift){
            Console::Write(sArray[i]);
            printed++;
        }
        i++;
    }
    Console::Write("\n");
    i = 0;
    shift++;
}