Sortieren einer Liste in mehrere vertikale Spalten
https://stackoverflow.com/questions/175099
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Hat jemand einen guten Algorithmus für Umsortierung ein Array von Werten (bereits vorsortiert), so dass sie in mehr (N) Spalten angezeigt werden und vertikal gelesen werden? Dies würde in .NET implementiert werden, aber ich würde etwas tragbar und nicht einige magische Funktion bevorzugen.
Ein gutes Beispiel dafür ist die Arbeits ASP.Net CheckBoxList Steuer Rendering als eine Tabelle mit der Richtung senkrecht zu setzen.
Hier ist ein Beispiel für die Eingabe und Ausgabe:
Input:
Columns = 4
Array = { "A", "B", "C", "D", "E", "F", "G"}
Ausgabe:
ACEG
BDF
Danke!
Aktualisiert (Mehr Info):
Ich glaube, ich könnte ein wenig mehr Informationen darüber geben, was ich ... Meistens dieses Problem zu tun, ich versuche, kam aus gehe ein CheckBoxList automatische Bindung verwenden (wo Sie die Spalten und Richtung Ausgang angeben und es wäre eine Tabelle der Elemente in der richtigen Reihenfolge output) zu jQuery / AJAX das Ankreuzfeld Raster zu erstellen. Also versuche ich, mit bestimmten Breiten, dass das Layout mit CSS mit div Blöcken zu duplizieren (in einem Container div eine bekannte Breite), so dass sie wickeln nach N Artikeln (oder Spalten). Dies auch in einer Tabelle wiedergegeben werden kann (wie, wie ASP .Net tut es.)
Alles funktioniert gut, außer die Reihenfolge horizontal ist und wenn Sie eine große Anzahl von Elementen in der Liste bekommen ist es einfacher, vertikale Spalten zu lesen.
Wenn das Array nicht genügend Elemente darin ein noch Gitter zu machen, dann sollte es gibt eine leere Stelle in der richtigen Zeile / Spalte des Gitters.
Und wenn ein Array nicht genügend Elemente auch nur eine einzige Zeile dann nur ausgegeben, um die Elemente in ihrer ursprünglichen Reihenfolge in einer Reihe zu machen.
Einige andere Input / Output könnte sein:
Spalten = 3
Array = { "A", "B", "C", "D"}
ACD
B
Columns = 5
Array = { "A", "B", "C", "D", "E", "F", "G", "H"}
ACEGH
BDF
Columns = 5
Array = { "A", "B", "C", "D"}
ABCD
Lösung
Okay, es tut mir leid für meine erste Aussage, aber wenn Sie es wollen arbeiten, wie Sie in den Kommentar zu meiner ersten Antwort beschrieben, müssen Sie in der Tat die Daten neu sortieren ... na ja etwas. Es könnte vielleicht ohne die Helfer Matrix durchgeführt werden, aber der resultierende Code wahrscheinlich sehr komplex ist und solange die Matrix nur ein paar Bytes Speichers verwenden wird, warum diese kleinen Helfer bauen nicht mit?
Was meinen Code unten tut, ist die Schaffung einer Matrix. Wir schreiben die Matrix von oben nach unten und von da links nach rechts (und stoppen alles andere als die erste Zeile füllt, wenn wir aus Elementen laufen alle Spalten der ersten Reihe zu füllen). Dann lesen wir es in einer anderen Reihenfolge, von links nach rechts und von oben nach unten. Im Grunde, was wir hier tun, ist eine Matrix umgesetzt werden, indem sie sie in eine Reihenfolge zu schreiben, aber lesen auf eine andere Reihenfolge. Transponieren einer Matrix eine sehr elementare mathematische Operation ist (viele 3D-Werke Programmierung von Matrixberechnungen und Transponieren ist eigentlich eine einfache Bedienung). Der Trick ist, wie wir zunächst die Matrix aufzufüllen. Um sicherzustellen, dass wir die erste Spalte in jedem Fall füllen können, unabhängig von der Anzahl der gewünschten Spalten und Größe des Arrays, müssen wir stoppen, die Matrix in der normalen Reihenfolge Füllen wenn wir aus Elementen und Reserve alle Elemente übrig blieben für den Lauf erste Reihe. Dies wird produziert die Ausgabe, die Sie in Ihrem Kommentar vorgeschlagen haben.
Das Ganze ist etwas kompliziert, ehrlich zu sein, aber die Theorie dahinter sollte gesund sein und es funktioniert schöne :-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;
}
Die Ausgabe ist
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
Dieser C Code sollte in dem Hafen zu PHP, C #, Java, usw. einfach sein, gibt es keine große Magie beteiligt, so ist es ziemlich universell, tragbar und Cross-Plattform.
Eine wichtige Sache, die ich hinzufügen sollte:
Dieser Code wird abstürzen, wenn Sie Spalten auf Null (Division durch Null, überprüfe ich nicht dafür) gesetzt, aber welchen Sinn würde 0 Spalten machen? Und es wird auch abstürzen, wenn Sie mehr Spalten als Elemente im Array haben, überprüfe ich auch nicht dafür. Sie können leicht überprüfen, entweder direkt nach bekommen die 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;
}
Ferner sollten Sie auch für die Arraysize überprüfen 0 zu sein, in dem Fall, dass Sie sofort von der Funktion springen heraus, wie in diesem Fall gibt es absolut nichts für die Funktion zu tun ist :) diese Kontrollen Hinzufügen soll den Code Rock machen Feststoff.
NULL Elemente im Array Mit funktionieren wird, BTW, in diesem Fall gibt es keine Löcher in der resultierenden Ausgabe. NULL Elemente werden übersprungen, wie nicht vorhanden ist. Z.B. verwenden lässt
char * Array[] = {"A", "B", "C", "D", "E", NULL, "F", "G", "H", "I"};
Der Ausgang wird
ADFI
BEG
CH
für Columns == 4. Wenn Sie wollen Löcher , müssen Sie ein Loch Element erstellen.
char hole = 0;
char * Array[] = {"A", "B", &hole, "C", "D", "E", &hole, "F", "G", "H", "I"};
und ändern Sie den Code Malerei ein bisschen
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");
Ausgabeproben:
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
Andere Tipps
Eine kleine UPDATE:
Der Algorithmus ich benutze hier ist eine modifizierte, die Sie für die Malerei Bilder verwenden würde. Ich vorgibt, die Array-Einträge Pixeldaten eines Bildes zu sein, und dann vom Anstreichen ich das Bild links nach rechts (1. LtoR) und von oben nach unten (2. TtoB), jedoch werden die Bilddaten gespeichert, aus von oben nach unten (1 TtoB) und dann von links nach rechts (2. LtoR); IOW in einer anderen Reihenfolge. Da ein Bild nicht hat Löcher , das ist der Grund, warum es nicht mit 5 oder 6 Spalten arbeiten. Mit 4 Spalten ist der Ausgang
ACEG
BDF
Als Bild dies wie folgt aussieht
OOOO
OOO.
Mit O ein Pixel des Bildes und mehr. ein undefiniertes Pixel ist (a fehlt eins). Fehlend diejenigen, können erst am Ende des Bildes sein, nicht in der Mitte. Das heißt, es auch so aussehen könnte
OOO
OO.
OO.
OO.
Alle fehlenden Pixel sind immer am Ende, wenn Sie lesen erster von oben nach unten und und von links nach rechts, da in diesem Fall alle fehlenden Pixel direkt folgen miteinander an dem Ende. Wenn ich das Diagramm TtoB und dann LtoR lesen, es ist wie dieser "Pixel, Pixel, Pixel, Pixel, ..., Pixel, fehlt, fehlt, fehlt, ..., fehlt" lesen muss, könnte es nie „Pixel lesen, fehlende, Pixel“oder "Fehlendes, Pixel, fehlt". Alle Pixel sind zusammen und alle Missings sind, auch.
Mit 5 Spalten, wie der Kommentar schon sagt, soll es so aussehen
ACEFG
BD
Doch wie Bild dies würde wie folgt aussehen
OOOOO
OO...
Und dies wird nicht durch den Algorithmus erlaubt. Wenn ich es TtoB und dann LtoR lesen, es wird gelesen: "Pixel, Pixel, Pixel, Pixel, Pixel, fehlt, Pixel, fehlende Pixel, fehlt". Und wie bereits erwähnt, ist dies nicht durch den Algorithmus erlaubt. So diese einfache Pixel Malerei Ansatz wird nicht so viele Spalten malen wie gewünscht, wenn die Malerei, die viele Spalten Löcher im Bild führt. In diesem Fall wird es einfach, die Löcher füllen, jedoch wird dies dazu führen, weniger Spalten gezogen werden.
Lassen Sie mich von einer Lösung denke, dass die angeforderte Anzahl von Pixeln (in einer separaten Antwort) wird immer malen.
Sie müssen nicht, dass überhaupt die Daten im Speicher neu zu ordnen. drucken Sie es einfach in der gewünschten Reihenfolge.
Einige C-Code (ich tue es sehr ausführlich, so dass jeder versteht, was so ich tue Natürlich kann diese wesentlich kompakter sein.):
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;
}
Hinweis: Diese mit einem Wert von 8 funktionieren gut und Werte von 4 (also alles innerhalb einer Reihe gemalt wird) und unten (funktioniert mit 3, 2 und 1), aber es kann mit 5 nicht funktioniert Das ist nicht die Schuld des Algorithmus ist es die Schuld des constrain.
ACEFG
BD
Die Einschränkung sagt die Spalten von oben nach unten gelesen werden die korrigierten sortierten Daten zu erhalten. Aber vor „ EFG “ sortiert ist und es ist oben nicht nach unten, wird es links nach rechts. So hat dieser Algorithmus ein Problem. Verwendung von Spalten = 3 funktioniert
ADG
BE
CF
zwei Verwendung wird auch funktionieren
AE
BF
CG
D
Und man wird alles in eine Spalte setzen.
Das sieht aus wie Hausaufgaben sowieso
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++;
}
