Ordinamento di un elenco in più colonne verticali
https://stackoverflow.com/questions/175099
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Qualcuno ha un buon algoritmo per riordinare un array di valori (già pre-ordinati) in modo che possano essere visualizzati in più (N) colonne e essere letti in verticale? Questo sarebbe implementato in .Net ma preferirei qualcosa di portatile e non una funzione magica.
Un buon esempio del suo funzionamento è il rendering del controllo CheckBoxList ASP.Net come tabella con la direzione impostata su verticale.
Ecco un esempio di input e output:
Input:
Colonne = 4
Matrice = {" A " ;, " B " ;, " C " ;, " D " ;, " E " ;, " F " ;, " G "}
Output:
ACEG
BDF
Grazie!
Aggiornato (Ulteriori informazioni):
Penso che potrei dover dare qualche informazione in più su ciò che sto cercando di fare ... Principalmente questo problema è derivato dall'utilizzo dell'associazione automatica di CheckBoxList (dove è possibile specificare le colonne e la direzione per l'output e produrrebbe una tabella di articoli nell'ordine corretto) usando jQuery / AJAX per creare la griglia della casella di controllo. Quindi sto cercando di duplicare quel layout usando css con blocchi div con larghezze specificate (all'interno di un div contenitore di una larghezza nota) in modo che si avvolgano dopo N elementi (o colonne.) Questo potrebbe anche essere reso in una tabella (come come ASP .Net lo fa.)
Tutto funziona alla grande tranne che l'ordine è orizzontale e quando ottieni un gran numero di elementi nell'elenco è più facile leggere le colonne verticali.
Se l'array non ha abbastanza elementi per creare una griglia uniforme, dovrebbe generare un punto vuoto nella riga / colonna corretta della griglia.
E se un array non ha abbastanza elementi per creare anche una sola riga, quindi emettere gli articoli nel loro ordine originale in una riga.
Alcuni altri input / ouput potrebbero essere:
Colonne = 3
Matrice = {" A " ;, " B " ;, " C " ;, " D "}
ACD
B
Colonne = 5
Matrice = {" A " ;, " B " ;, " C " ;, " D " ;, " E " ;, " F " ;, " G " ;, " H "}
ACEGH
BDF
Colonne = 5
Matrice = {" A " ;, " B " ;, " C " ;, " D "}
ABCD
Soluzione
Okay, mi dispiace per la mia affermazione iniziale, ma quando vuoi che funzioni come descritto nel commento alla mia prima risposta, devi in ??effetti riordinare i dati ... un po 'bene. Potrebbe forse essere fatto senza la matrice helper, tuttavia il codice risultante è probabilmente molto complesso e fintanto che la matrice utilizzerà solo un paio di byte di memoria, perché non usare questo costrutto helper?
Quello che fa il mio codice di seguito è la creazione di una matrice. Scriviamo la matrice dall'alto verso il basso e poi da sinistra a destra (e smettiamo di riempire qualsiasi cosa tranne la prima riga quando finiamo gli elementi per riempire tutte le colonne della prima riga). Quindi lo leggiamo in un ordine diverso, da sinistra a destra e dall'alto verso il basso. Fondamentalmente quello che facciamo qui è trasporre una matrice , scrivendola in un ordine, ma leggendolo in un altro ordine. Trasporre una matrice è un'operazione matematica molto elementare (molte opere di programmazione 3D usando calcoli con matrici e trasporre è in realtà un'operazione semplice). Il trucco è come riempire inizialmente la matrice. Per essere sicuri di poter riempire la prima colonna in ogni caso, indipendentemente dal numero di colonne desiderate e dalle dimensioni dell'array, dobbiamo interrompere il riempimento della matrice nell'ordine normale se esauriamo gli elementi e riserviamo tutti gli elementi rimasti per il prima riga. Questo produrrà l'output che hai suggerito nel tuo commento.
L'intera faccenda è un po 'complicata a dire il vero, ma la teoria alla base dovrebbe essere sana e funziona benissimo MrGreen
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;
}
L'output è
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
Questo codice C dovrebbe essere facile da portare su PHP, C #, Java, ecc., Non c'è nessuna grande magia coinvolta, quindi è praticamente universale, portatile e multipiattaforma.
Una cosa importante che dovrei aggiungere:
Questo codice si arresterà in modo anomalo se imposti le colonne su zero (divisione per zero, non lo controllo), ma che senso avrebbe 0 colonne? E si bloccherà anche se hai più colonne che elementi nell'array, non controllo neanche questo. Puoi facilmente controllare per entrambi subito dopo aver ottenuto 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;
}
Inoltre dovresti anche verificare che arraySize sia 0, nel qual caso puoi saltare immediatamente fuori dalla funzione, poiché in quel caso non c'è assolutamente nulla da fare per la funzione :) L'aggiunta di questi controlli dovrebbe far oscillare il codice solida.
Avere NULL Elements nell'array funzionerà, a proposito, in quel caso non ci sono buchi nell'output risultante. Gli elementi NULL vengono semplicemente ignorati come non essere presenti. Per esempio. usiamo
char * Array[] = {"A", "B", "C", "D", "E", NULL, "F", "G", "H", "I"};
L'output sarà
ADFI
BEG
CH
for Columns == 4. Se vuoi fori , devi creare un elemento hole.
char hole = 0;
char * Array[] = {"A", "B", &hole, "C", "D", "E", &hole, "F", "G", "H", "I"};
e modifica un po 'il codice di pittura
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");
Esempi di output:
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
Altri suggerimenti
Un piccolo AGGIORNAMENTO:
L'algoritmo che sto usando qui è uno modificato che useresti per dipingere immagini. Sto fingendo che le voci dell'array siano dati pixel di un'immagine e quindi dipingo l'immagine da sinistra a destra (1. LtoR) e dall'alto verso il basso (2. TtoB), tuttavia, i dati dell'immagine vengono archiviati da dall'alto verso il basso (1. TtoB) e poi da sinistra a destra (2. LtoR); IOW in un ordine diverso. Poiché un'immagine non può avere buchi , questo è il motivo per cui non funzionerà con 5 o 6 colonne. Con 4 colonne l'output è
ACEG
BDF
Come immagine sembra così
OOOO
OOO.
Con O come pixel dell'immagine e. essendo un pixel indefinito (uno mancante). Quelli mancanti possono essere solo alla fine dell'immagine, non al centro di essa. Ciò significa che potrebbe anche assomigliare a questo
OOO
OO.
OO.
OO.
Tutti i pixel mancanti sono sempre alla fine, se leggi prima dall'alto verso il basso e quindi da sinistra a destra, perché in quel caso tutti i pixel mancanti seguono direttamente l'un l'altro alla fine. Se leggo il diagramma TtoB e poi LtoR, deve leggere in questo modo " Pixel, Pixel, Pixel, Pixel, ..., Pixel, Missing, Missing, Missing, ..., Missing " ;, potrebbe non leggere mai " Pixel, Missing, Pixel " o " Mancante, Pixel, Mancante " ;. Tutti i pixel sono uniti e anche tutti i difetti.
Con 5 colonne, come suggerisce il commento, dovrebbe apparire così
ACEFG
BD
Tuttavia, come immagine sarebbe simile a questa
OOOOO
OO...
E questo non è consentito dall'algoritmo. Se lo leggo TtoB e poi LtoR, verrà visualizzato: "Pixel, Pixel, Pixel, Pixel, Pixel, Missing, Pixel, Missing, Pixel, Missing". E come detto sopra, questo non è consentito dall'algoritmo. Quindi questo semplice approccio di pittura pixel non dipingerà tutte le colonne richieste se la pittura di quante colonne porta a buchi nell'immagine. In tal caso riempirà semplicemente i buchi, tuttavia, ciò farà sì che vengano disegnate meno colonne.
Fammi pensare a una soluzione che dipingerà sempre il numero richiesto di pixel (in una risposta separata).
Non è necessario riorganizzare i dati in memoria per quello. Basta stamparlo nell'ordine desiderato.
Qualche codice C (lo sto facendo in modo estremamente dettagliato, quindi tutti capiscono quello che sto facendo. Naturalmente questo può essere molto più compatto):
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: funziona bene con un valore di 8 (quindi tutto è dipinto in una riga) e valori di 4 e inferiori (funziona bene con 3, 2 e 1), ma non può funzionare con 5. Questo è non è colpa dell'algoritmo, è colpa del vincolo.
ADG
BE
CF
Il vincolo dice che le colonne vengono lette dall'alto verso il basso per ottenere i dati ordinati corretti. Ma sopra " EFG " è ordinato e non è dall'alto verso il basso, è da sinistra a destra. Quindi questo algoritmo ha un problema. L'uso di Columns = 3 funzionerà
AE
BF
CG
D
Anche l'uso di due funzionerà
<*>E uno metterà tutto in una colonna.
Sembra compiti a casa in ogni caso
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++;
}
