Ordenar una lista en múltiples columnas verticales

Question

¿Alguien tiene un buen algoritmo para reordenar una matriz de valores (ya pre-ordenados) para que puedan ser mostrados en múltiples columnas (N) y leerse verticalmente? Esto se implementaría en .Net, pero preferiría algo portátil y no una función mágica.

Un buen ejemplo de su funcionamiento es el control ASP.Net CheckBoxList como una tabla con la dirección establecida en vertical.

Aquí hay un ejemplo de la entrada y salida:

Entrada:

Columnas = 4
Array = {" A ", " B " ;, " C " ;, " D " ;, " E " ;, F " ;, " G = quot;}

Salida:

ACEG
BDF

¡Gracias!

Actualizado (Más información):

Creo que podría tener que dar un poco más de información sobre lo que estoy tratando de hacer ... Principalmente, este problema surgió por el uso de un enlace automático CheckBoxList (donde puede especificar las columnas y la dirección de salida y generaría una tabla de elementos en el orden correcto) para usar jQuery / AJAX para crear la cuadrícula de casilla de verificación. Así que estoy tratando de duplicar ese diseño usando css con bloques div con anchos especificados (dentro de un contenedor div de un ancho conocido) para que se ajusten después de N elementos (o columnas). Esto también podría representarse en una tabla (como cómo ASP .Net lo hace.)

Todo funciona bien, excepto que el orden es horizontal y cuando se obtiene una gran cantidad de elementos en la lista, es más fácil leer columnas verticales.

Si la matriz no tiene suficientes elementos para hacer una cuadrícula uniforme, debería generar un espacio vacío en la fila / columna correcta de la cuadrícula.

Y si una matriz no tiene suficientes elementos para formar una sola fila, simplemente genere los elementos en su orden original en una fila.

Algunas otras entradas / salidas podrían ser:

Columnas = 3
Array = {" A " ;, " B " ;, " C " ;, " D "}

ACD
B

Columnas = 5
Array = {"A", "B", "C", D ", E", "F", "G", "H"}

ACEGH
BDF

Columnas = 5
Array = {" A " ;, " B " ;, " C " ;, " D "}

ABCD

Answer 1

De acuerdo, lamento mi declaración inicial, pero cuando quiera que funcione como describió en el comentario a mi primera respuesta, en realidad necesita reordenar los datos ... bueno, algo. Tal vez podría hacerse sin la matriz auxiliar, sin embargo, el código resultante probablemente sea muy complejo y siempre que la matriz solo use un par de bytes de memoria, ¿por qué no usar esta pequeña construcción auxiliar?

Lo que mi código hace a continuación es crear una matriz. Escribimos la matriz de arriba a abajo y luego de izquierda a derecha (y dejamos de llenar todo lo que no sea la primera fila cuando nos quedamos sin elementos para llenar todas las columnas de la primera fila). Luego lo leemos en un orden diferente, de izquierda a derecha y de arriba a abajo. Básicamente, lo que hacemos aquí es transponer una matriz , escribiéndola en un orden, pero leyéndolo otra orden La transposición de una matriz es una operación matemática muy elemental (muchos trabajos de programación en 3D mediante el uso de cálculos matriciales y la transposición es en realidad una operación simple). El truco es cómo inicialmente llenamos la matriz. Para asegurarnos de que podemos llenar la primera columna en cualquier caso, independientemente del número de columnas deseadas y el tamaño de la matriz, debemos dejar de llenar la matriz en el orden normal si nos quedamos sin elementos y reservamos todos los elementos que queden para el primera fila. Esto producirá la salida que has sugerido en tu comentario.

Todo esto es un poco complicado para ser honesto, pero la teoría subyacente debería ser sensata y funciona de maravilla :-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;
}

La salida es

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 debería ser fácil de portar a PHP, C #, Java, etc., no hay mucha magia involucrada, por lo que es prácticamente universal, portátil y multiplataforma.

---

Una cosa importante que debo agregar:

Este código se bloqueará si establece Columnas en cero (división por cero, no lo compruebo), pero ¿qué sentido tendría 0 Columnas? Y también se bloqueará si tiene más columnas que elementos en la matriz, tampoco lo compruebo. Puede verificar fácilmente cualquiera de los dos inmediatamente después de obtener el 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;
}

Además, también debes verificar que el arraySize sea 0, en cuyo caso puedes saltar directamente a la función, ya que en ese caso no hay absolutamente nada que hacer para la función :) Agregar estas comprobaciones debería hacer que el código se mueva sólido.

Tener elementos NULL en la matriz funcionará, por cierto, en ese caso no hay agujeros en la salida resultante. Los elementos NULOS se saltan como si no estuvieran presentes. P.ej. vamos a utilizar

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

La salida será

ADFI
BEG
CH

para Columnas == 4. Si quiere agujeros , necesita crear un elemento de agujero.

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

y modifica un poco el código de pintura

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

Muestras de salida:

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

Una pequeña ACTUALIZACIÓN:

El algoritmo que estoy usando aquí es uno modificado que usarías para pintar imágenes. Pretendo que las entradas de la matriz sean datos de píxeles de una imagen y luego pinto la imagen de izquierda a derecha (1. LtoR) y de arriba a abajo (2. TtoB), sin embargo, los datos de la imagen se almacenan desde de arriba a abajo (1. TtoB) y luego de izquierda a derecha (2. LtoR); IOW en un orden diferente. Dado que una imagen no puede tener agujeros , esta es la razón por la que no funcionará con 5 o 6 columnas. Con 4 columnas la salida es

ACEG
BDF

Como imagen, esto se ve así

OOOO
OOO.

Con O siendo un píxel de la imagen y. siendo un pixel indefinido (uno faltante). Los que faltan solo pueden estar al final de la imagen, no en el medio. Eso significa que también podría tener este aspecto

OOO
OO.
OO.
OO.

Todos los píxeles que faltan están siempre al final, si lees primero de arriba abajo y luego de izquierda a derecha, porque en ese caso, todos los píxeles que faltan siguen directamente unos a otros al final. Si leo el diagrama TtoB y luego LtoR, debe leerse así: "Pixel, Pixel, Pixel, Pixel, ..., Pixel, Missing, Missing, Missing, ..., Missing", quizás nunca se lea " Pixel, Missing, Pixel " o " Missing, Pixel, Missing " ;. Todos los píxeles están juntos y todas las faltas también.

Con 5 columnas, como sugiere el comentario, debería tener este aspecto

ACEFG
BD

Sin embargo, como imagen, esto se vería así

OOOOO
OO...

Y esto no está permitido por el algoritmo. Si lo leo TtoB y luego LtoR, leerá: "Pixel, Pixel, Pixel, Pixel, Pixel, Missing, Pixel, Missing, Pixel, Missing". Y como se indicó anteriormente, esto no está permitido por el algoritmo. Por lo tanto, este enfoque simple de pintura de píxeles no pintará tantas columnas como se solicita si pintar tantas columnas conduce a agujeros en la imagen. En ese caso, simplemente llenará los orificios, sin embargo, esto hará que se dibujen menos columnas.

Permítame pensar en una solución que siempre pintará los números de píxeles solicitados (en una respuesta por separado).

---

No tiene que reorganizar los datos en la memoria para eso en absoluto. Solo imprímelo en el orden deseado.

Algún código C (lo estoy haciendo muy detallado, para que todos entiendan lo que hago. Por supuesto, esto puede ser mucho más 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: Esto funciona bien con un valor de 8 (por lo que todo está pintado en una fila) y valores de 4 y menores (funciona bien con 3, 2 y 1), pero no puede funcionar con 5. Esto es No es culpa del algoritmo, es culpa de la restricción.

ADG
BE
CF

La restricción dice que las columnas se leen de arriba a abajo para obtener los datos ordenados corregidos. Pero arriba de " EFG " está ordenado y no es de arriba a abajo, está de izquierda a derecha. Por lo tanto este algoritmo tiene un problema. Usar Columnas = 3 funcionará

AE
BF
CG
D

Usar dos también funcionará

<*>

Y uno pondrá todo en una columna.

Answer 3

Esto se parece a las tareas asignadas de todos modos

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