Tri d'une liste en plusieurs colonnes verticales

Question

Quelqu'un at-il un bon algorithme pour re-trier un tableau de valeurs (déjà pré-trié) afin qu’elles puissent être affichées dans plusieurs (N) colonnes et lues verticalement? Cela serait implémenté en .Net mais je préférerais quelque chose de portable et pas une fonction magique.

Un bon exemple de ce fonctionnement est le rendu du contrôle ASP.Net CheckBoxList sous forme de tableau avec la direction définie sur vertical.

Voici un exemple d'entrée et de sortie:

Entrée:

Columns = 4
Tableau = {"A", "B", "C", "D", "E", "F", "G"}

Sortie:

ACEG
BDF

Merci!

mis à jour (plus d'infos):

Je pense que je devrais peut-être donner un peu plus d'informations sur ce que j'essaie de faire ... Ce problème est principalement dû à l'utilisation de la liaison automatique d'un CheckBoxList (où vous pouvez spécifier les colonnes et le sens de la sortie). il générerait une table d’éléments dans le bon ordre) en utilisant jQuery / AJAX pour créer la grille de cases à cocher. J'essaie donc de dupliquer cette mise en page en utilisant css avec des blocs div avec des largeurs spécifiées (à l'intérieur d'un div de conteneur d'une largeur connue) afin qu'ils s'emboîtent après N éléments (ou colonnes). Cela pourrait également être restitué dans un tableau (comme ASP .Net le fait.)

Tout fonctionne bien, sauf que l'ordre est horizontal et lorsque vous obtenez un grand nombre d'éléments dans la liste, il est plus facile de lire les colonnes verticales.

Si le tableau ne contient pas suffisamment d'éléments pour créer une grille uniforme, il doit générer un emplacement vide dans la ligne / colonne correcte de la grille.

Et si un tableau ne contient pas assez d'éléments pour créer une seule ligne, il vous suffit de les afficher dans leur ordre d'origine, sur une ligne.

Une autre entrée / sortie pourrait être:

Columns = 3
Tableau = {"A", "B", "C", "D"}

ACD
B

Columns = 5
Tableau = {"A", "B", "C", "D", "E", "F", "G", "H"}

ACEGH
BDF

Columns = 5
Tableau = {"A", "B", "C", "D"}

ABCD

Answer 1

D'accord, je m'excuse pour ma déclaration initiale, mais lorsque vous souhaitez que cela fonctionne comme vous l'avez décrit dans le commentaire de ma première réponse, vous devez en fait trier à nouveau les données ... enfin un peu. Cela pourrait peut-être être fait sans la matrice d'assistance, mais le code résultant est probablement très complexe et tant que la matrice n'utilisera que quelques octets de mémoire, pourquoi ne pas utiliser cette petite construction d'assistance?

Ce que mon code fait ci-dessous crée une matrice. Nous écrivons la matrice de haut en bas, puis de gauche à droite (et arrêtons de remplir autre chose que la première ligne lorsque nous manquons d'éléments pour remplir toutes les colonnes de la première ligne). Ensuite, nous le lisons dans un ordre différent, de gauche à droite et de haut en bas. Ce que nous faisons ici est essentiellement transposer une matrice , en l'écrivant dans un ordre, mais en le lisant dans une autre commande. Transposer une matrice est une opération mathématique très élémentaire (de nombreux travaux de programmation 3D utilisant des calculs matriciels et la transposition sont en réalité une opération simple). Le truc est de savoir comment nous remplissons initialement la matrice. Pour être sûr que nous pouvons remplir la première colonne dans tous les cas, indépendamment du nombre de colonnes souhaitées et de la taille du tableau, nous devons arrêter de remplir la matrice dans l'ordre normal si nous manquons d'éléments et réserver tous les éléments restants pour la suite. première rangée. Cela produira le résultat suggéré dans votre commentaire.

Pour être honnête, le tout est un peu compliqué, mais la théorie derrière elle devrait être saine d’esprit et elle fonctionne à merveille :-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 sortie est

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

Ce code C devrait être facile à porter en PHP, C #, Java, etc., il n’ya pas de grande magie, il est donc plutôt universel, portable et multiplateforme.

Une chose importante que je devrais ajouter:

Ce code se bloquera si vous définissez les colonnes à zéro (division par zéro, je ne vérifie pas cela), mais quel sens aurait 0 colonnes? Et cela plantera aussi si vous avez plus de colonnes que d'éléments dans le tableau, je ne vérifie pas cela non plus. Vous pouvez facilement vérifier que ce soit juste après que vous ayez obtenu la valeur 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;
}

De plus, vous devriez aussi vérifier que arraySize est à 0, auquel cas vous pouvez sauter tout de suite à la fonction, car dans ce cas, il n’ya absolument rien à faire pour la fonction :) Ajouter ces vérifications devrait rendre le code rock solide.

Avoir NULL Elements dans le tableau va fonctionner, BTW, dans ce cas, il n'y a pas de trous dans la sortie résultante. Les éléments NULL sont simplement ignorés comme s'ils n'étaient pas présents. Par exemple. permet d'utiliser

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

Le résultat sera

ADFI
BEG
CH

for Columns == 4. Si vous voulez des trous , vous devez créer un élément de trou.

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

et modifiez un peu le code de peinture

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

Exemples de sortie:

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

Une petite mise à jour:

L'algorithme que j'utilise ici est un algorithme modifié que vous utiliseriez pour peindre des images. Je fais semblant que les entrées de tableau sont des données de pixel d'une image, puis je peins l'image de gauche à droite (1. LtoR) et de haut en bas (2. TtoB). Cependant, les données d'image sont stockées dans de haut en bas (1. TtoB), puis de gauche à droite (2. LtoR); IOW dans un ordre différent. Puisqu'une image ne peut pas avoir de trous , c'est la raison pour laquelle elle ne fonctionnera pas avec 5 ou 6 colonnes. Avec 4 colonnes, le résultat est

ACEG
BDF

Comme une image, cela ressemble à ceci

OOOO
OOO.

O étant un pixel de l’image et. être un pixel indéfini (manquant). Les données manquantes peuvent être uniquement à la fin de l'image, pas au milieu. Cela signifie que cela pourrait aussi ressembler à ceci

OOO
OO.
OO.
OO.

Tous les pixels manquants sont toujours à la fin, si vous lisez d'abord de haut en bas et puis de gauche à droite, car dans ce cas, tous les pixels manquants suivent directement l'autre à la fin. Si je lis les diagrammes TtoB puis LtoR, il doit se lire comme suit: "Pixel, Pixel, Pixel, Pixel, ..., Pixel, manquant, manquant, manquant, ..., manquant", il se peut qu'il ne lise jamais " Pixel, manquant, Pixel " ou "Manquant, Pixel, Manquant". Tous les pixels sont ensemble et tous les manquants le sont également.

Avec 5 colonnes, comme le suggère le commentaire, il devrait ressembler à ceci

ACEFG
BD

Cependant, comme image, cela ressemblerait à ceci

OOOOO
OO...

Et cela n’est pas autorisé par l’algorithme. Si je le lis TtoB puis LtoR, il se lira: "Pixel, Pixel, Pixel, Pixel, Pixel, manquant, Pixel, manquant, Pixel, manquant". Et comme indiqué ci-dessus, cet algorithme ne le permet pas. Ainsi, cette approche simple de peinture au pixel ne permet pas de peindre autant de colonnes que demandé si peindre autant de colonnes conduit à des trous dans l’image. Dans ce cas, les trous seront simplement comblés, mais cela entraînera moins de colonnes.

Permettez-moi de penser à une solution qui peindra toujours les nombres de pixels demandés (dans une réponse distincte).

Vous n'avez pas besoin de réorganiser les données en mémoire pour cela. Imprimez-le simplement dans l'ordre souhaité.

Certains codes C (je le fais extrêmement verbeux pour que tout le monde comprenne ce que je fais. Bien sûr, cela peut être beaucoup plus compact):

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

Remarque: cela fonctionne bien avec une valeur de 8 (donc tout est peint dans une rangée) et des valeurs de 4 et moins (fonctionne bien avec 3, 2 et 1), mais cela ne peut pas fonctionner avec 5. Ceci est pas la faute de l'algorithme, c'est la faute de la contrainte.

ADG
BE
CF

La contrainte indique que les colonnes sont lues de haut en bas pour obtenir les données triées corrigées. Mais au-dessus de EFG " est trié et ce n’est pas de haut en bas, c’est de gauche à droite. Donc, cet algorithme a un problème. Utiliser des colonnes = 3 fonctionnera

AE
BF
CG
D

L'utilisation de deux fonctionnera également

<*>

Et on mettra tout dans une colonne.

Answer 3

Cela ressemble à des devoirs de toute façon

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