Сортировка списка на несколько вертикальных столбцов
https://stackoverflow.com/questions/175099
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Есть ли у кого-нибудь хороший алгоритм повторной сортировки массива значений (уже предварительно отсортированного), чтобы их можно было отображать в нескольких (N) столбцах и читать вертикально?Это было бы реализовано в .Net, но я бы предпочел что-то портативное, а не какую-то волшебную функцию.
Хорошим примером его работы является отображение элемента управления ASP.Net CheckBoxList в виде таблицы с вертикальным направлением.
Вот пример ввода и вывода:
Вход:
Столбцы = 4
Массив = {"A", "B", "C", "D", "E", "F", "G"}
Выход:
АСЕГ
БДФ
Спасибо!
Обновлено (дополнительная информация):
Думаю, мне придется дать немного больше информации о том, что я пытаюсь сделать...В основном эта проблема возникла из-за перехода от использования автоматической привязки CheckBoxList (где вы можете указать столбцы и направление вывода, и она будет выводить таблицу элементов в правильном порядке) к использованию jQuery/AJAX для создания сетки флажков.Итак, я пытаюсь продублировать этот макет, используя CSS с блоками div с указанной шириной (внутри контейнера div известной ширины), чтобы они переносились после N элементов (или столбцов). Это также можно отобразить в таблице (например, как ASP .Net делает это.)
Все работает отлично, за исключением того, что порядок горизонтальный, а при большом количестве элементов в списке легче читать вертикальные столбцы.
Если в массиве недостаточно элементов для создания ровной сетки, он должен вывести пустое место в правильной строке/столбце сетки.
А если в массиве недостаточно элементов, чтобы составить хотя бы одну строку, просто выведите элементы в исходном порядке в одной строке.
Некоторые другие входы/выходы могут быть:
Столбцы = 3
Массив = {"A", "B", "C", "D"}
АКД
Б
Столбцы = 5
Массив = {"A", "B", "C", "D", "E", "F", "G", "H"}
АСЕГ
БДФ
Столбцы = 5
Массив = {"A", "B", "C", "D"}
АВСD
Решение
Хорошо, извините за мое первоначальное утверждение, но если вы хотите, чтобы оно работало так, как вы описали в комментарии к моему первому ответу, вам фактически нужно пересортировать данные...ну несколько.Возможно, это можно было бы сделать и без вспомогательной матрицы, однако результирующий код, вероятно, будет очень сложным, и, поскольку матрица будет использовать всего пару байт памяти, почему бы не использовать эту маленькую вспомогательную конструкцию?
Мой код ниже создает матрицу.Мы пишем матрицу сверху вниз, а затем слева направо (и перестаем заполнять что-либо, кроме первой строки, когда у нас заканчиваются элементы для заполнения всех столбцов первой строки).Дальше читаем в другом порядке: слева направо и сверху вниз.По сути, то, что мы здесь делаем, это транспонирование матрицы, записывая его в одном порядке, а читая в другом порядке.Транспонирование матрицы — это очень элементарная математическая операция (во многих трехмерных программах используются матричные вычисления, а транспонирование на самом деле является простой операцией).Хитрость в том, как мы изначально заполняем матрицу.Чтобы убедиться, что мы можем заполнить первый столбец в любом случае, независимо от количества желаемых столбцов и размера массива, мы должны прекратить заполнение матрицы в обычном порядке, если у нас закончатся элементы, и зарезервировать все оставшиеся элементы для Первая строка.Это даст результат, который вы предложили в своем комментарии.
Честно говоря, все это немного сложно, но теория, лежащая в основе этого, должна быть разумной, и она прекрасно работает :-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;
}
Выход:
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
Этот код C должен быть легко перенесен на PHP, C#, Java и т. д., здесь не требуется никакой магии, поэтому он в значительной степени универсален, портативен и кроссплатформен.
Я должен добавить одну важную вещь:
Этот код выйдет из строя, если вы установите для столбцов значение 0 (деление на ноль, я это не проверяю), но какой смысл будет иметь 0 столбцов?А также произойдет сбой, если в массиве будет больше столбцов, чем элементов, я это тоже не проверяю.Вы можете легко проверить любой из них сразу после получения 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;
}
Кроме того, вам также следует проверить, что arraySize равен 0, и в этом случае вы можете сразу выйти из функции, так как в этом случае с функцией абсолютно нечего делать :) Добавление этих проверок должно сделать код очень надежным.
Наличие NULL-элементов в массиве будет работать, кстати, в этом случае в результирующем выводе нет дыр.Элементы NULL просто пропускаются, как будто их нет.Например.давайте использовать
char * Array[] = {"A", "B", "C", "D", "E", NULL, "F", "G", "H", "I"};
Результат будет
ADFI
BEG
CH
для столбцов == 4.Если вы хочу дырок, вам нужно создать элемент отверстия.
char hole = 0;
char * Array[] = {"A", "B", &hole, "C", "D", "E", &hole, "F", "G", "H", "I"};
и немного измените код рисования
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");
Выходные образцы:
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
Другие советы
Небольшое ОБНОВЛЕНИЕ:
Алгоритм, который я здесь использую, представляет собой модифицированный алгоритм, который вы бы использовали для рисования изображений.Я притворяюсь, что записи массива представляют собой пиксельные данные изображения, а затем рисую изображение слева направо (1.LtoR) и сверху вниз (2.TtoB), однако данные изображения сохраняются сверху вниз (1.TtoB), а затем слева направо (2.ЛтоР);IOW в другом порядке.Поскольку изображение не может иметь дыры, именно по этой причине он не будет работать с 5 или 6 столбцами.С 4 столбцами результат будет
ACEG
BDF
На изображении это выглядит так
OOOO
OOO.
Где O — это пиксель изображения, а .быть неопределенным пикселем (отсутствующим).Отсутствующие могут быть только в конце изображения, а не в его середине.Это означает, что это также может выглядеть так
OOO
OO.
OO.
OO.
Все недостающие пиксели всегда в конце, если читать первый сверху вниз и затем слева направо, потому что в этом случае все недостающие пиксели следуют друг за другом в конце.Если я прочитаю диаграмму TtoB, а затем LtoR, она должна читаться так: «Пиксель, Пиксель, Пиксель, Пиксель, ..., Пиксель, Отсутствует, Отсутствует, Отсутствует, ..., Отсутствует», она может никогда не читаться «Пиксель, Отсутствует пиксель» или «Отсутствует, пиксель, отсутствует».Все пиксели вместе и все недостающие тоже.
С 5 столбцами, как следует из комментария, это должно выглядеть так
ACEFG
BD
Однако на изображении это будет выглядеть так
OOOOO
OO...
А это не допускается алгоритмом.Если я прочитаю это TtoB, а затем LtoR, то будет написано:«Пиксель, пиксель, пиксель, пиксель, пиксель, пропал, пиксель, пропал, пиксель, пропал».И как сказано выше, это не допускается алгоритмом.Таким образом, этот простой подход к рисованию пикселей не будет рисовать столько столбцов, сколько требуется, если рисование такого количества столбцов приводит к появлению дыр в изображении.В этом случае он просто заполнит дыры, однако это приведет к тому, что будет нарисовано меньше столбцов.
Позвольте мне подумать о решении, которое всегда будет рисовать запрошенное количество пикселей (в отдельном ответе).
Для этого вам вообще не нужно переупорядочивать данные в памяти.Просто распечатайте его в нужном порядке.
Некоторый код C (я делаю это очень подробно, поэтому все понимают, что я делаю.Конечно, это может быть гораздо компактнее):
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;
}
Примечание:Это прекрасно работает со значением 8 (так что все рисуется в пределах одной строки) и значениями 4 и ниже (отлично работает со значениями 3, 2 и 1), но не может работать со значением 5.Это не вина алгоритма, это вина ограничений.
ACEFG
BD
Ограничение гласит, что столбцы читаются сверху вниз, чтобы получить исправленные отсортированные данные.Но выше»ЭФГ" сортируется не сверху вниз, а слева направо.Таким образом, этот алгоритм имеет проблему.Использование Columns = 3 будет работать
ADG
BE
CF
Использование двух тоже будет работать
AE
BF
CG
D
И все поместишь в одну колонку.
В любом случае это выглядит как домашние задания
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++;
}
