6

有没有人有一个很好的算法来重新排序一个值数组（已经预先排序），以便它们可以显示在多个（N）列中并垂直读取？这将在 .Net 中实现，但我更喜欢便携的东西，而不是一些神奇的功能。

它工作的一个很好的例子是 ASP.Net CheckBoxList 控件呈现为一个方向设置为垂直的表格。

这是输入和输出的示例：

输入：

列 = 4
数组 = {“A”、“B”、“C”、“D”、“E”、“F”、“G”}

输出：

ACEG
BDF

谢谢！

更新（更多信息）：

我想我可能需要提供更多关于我正在尝试做的事情的信息......大多数情况下，这个问题来自使用 CheckBoxList 的自动绑定（您可以在其中指定输出的列和方向，它会输出以正确顺序的项目表）使用 jQuery/AJAX 创建复选框网格。因此，我尝试使用带有指定宽度的 div 块（在已知宽度的容器 div 内）的 css 复制该布局，以便它们在 N 个项目（或列）之后包装。这也可以在表格中呈现（就像 ASP .Net 做到了。）

一切都很好，除了顺序是水平的，当您在列表中获得大量项目时，更容易阅读垂直列。

如果数组中没有足够的项目来制作一个均匀的网格，那么它应该在网格的正确行/列中输出一个空点。

如果一个数组没有足够的项目来组成一行，那么只需在一行中按原始顺序输出项目。

其他一些输入/输出可能是：

列 = 3
数组 = {“A”、“B”、“C”、“D”}

ACD
乙

列 = 5
数组 = {“A”、“B”、“C”、“D”、“E”、“F”、“G”、“H”}

ACEGH
BDF

列 = 5
数组 = {“A”、“B”、“C”、“D”}

A B C D

4

3 回答 3

6

好的，我很抱歉我最初的声明，但是当您希望它按照您在我的第一个答案的评论中描述的那样工作时，您实际上需要重新排序数据......好吧。它可以在没有辅助矩阵的情况下完成，但是生成的代码可能非常复杂，只要矩阵只使用几个字节的内存，为什么不使用这个小辅助构造呢？

我的代码在下面做的是创建一个矩阵。我们从上到下然后从左到右编写矩阵（当我们用完元素来填充第一行的所有列时，停止填充除第一行以外的任何内容）。然后我们以不同的顺序阅读它，从左到右，从上到下。基本上我们在这里做的是转置一个矩阵, 以一种顺序写入，但以另一种顺序读取。转置矩阵是一个非常基本的数学运算（许多 3D 编程通过使用矩阵计算来工作，转置实际上是一个简单的运算）。诀窍是我们最初如何填充矩阵。为了确保我们在任何情况下都可以填充第一列，与所需的列数和数组的大小无关，如果我们用完元素，我们必须停止按正常顺序填充矩阵并保留所有剩余的元素第一排。这将产生您在评论中建议的输出。

老实说，整个事情有点复杂，但它背后的理论应该是理智的，而且效果很好:-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 等，没有什么大魔法，所以它几乎是通用的、可移植的和跨平台的。

我应该补充一件重要的事情：

如果将 Columns 设置为零（除以零，我不检查），此代码将崩溃，但是 0 Columns 有什么意义呢？如果您的列数多于数组中的元素，它也会崩溃，我也不检查这一点。获得 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

对于 Columns == 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
于 2008-10-07T10:45:19.023 回答
3

一个小更新：

我在这里使用的算法是一种修改后的算法，您将使用它来绘制图像。我假装数组条目是图像的像素数据，然后我从左到右（1.LtoR）和从上到下（2.TtoB）绘制图像，但是，图像数据存储自从上到下（1. TtoB）然后从左到右（2. LtoR）；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

约束表示从上到下读取列以获取更正的排序数据。但是上面的“ EFG ”是排序的，不是从上到下，而是从左到右。所以这个算法有问题。使用 Columns = 3 将起作用

ADG
BE
CF

使用两个也可以

AE
BF
CG
D

并且会将所有内容放在一列中。

于 2008-10-06T18:29:32.347 回答
1

无论如何，这看起来像是家庭作业

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++;
}
于 2008-10-06T18:15:37.350 回答