목록을 여러 수직 열로 정렬

Question

여러 (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"}

아세
BDF

열 = 5
배열 = {"A", "B", "C", "D"}

ABCD

Answer 1

좋아, 첫 번째 진술은 유감이지만 첫 번째 답변에 대한 설명에서 설명한 대로 작동하려면 실제로 데이터를 다시 정렬해야 합니다...뭐 좀.도우미 행렬 없이도 수행할 수 있지만 결과 코드는 매우 복잡할 수 있으며 행렬이 몇 바이트의 메모리만 사용하는 한 이 작은 도우미 구성을 사용하지 않는 이유는 무엇입니까?

아래 코드에서 수행하는 작업은 행렬을 만드는 것입니다.위에서 아래로, 그리고 왼쪽에서 오른쪽으로 행렬을 작성합니다(그리고 첫 번째 행의 모든 ​​열을 채울 요소가 부족해지면 첫 번째 행 이외의 항목 채우기를 중지합니다).그런 다음 왼쪽에서 오른쪽, 위에서 아래로 다른 순서로 읽습니다.기본적으로 우리가 여기서 하는 일은 행렬 전치, 한 순서로 쓰지만 다른 순서로 읽는 방식입니다.행렬을 전치하는 것은 매우 기본적인 수학 연산입니다. 많은 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으로 설정하면(0으로 나누기, 확인하지 않음) 이 코드는 충돌할 것입니다. 하지만 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

열 == 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

Answer 2

작은 업데이트 :

여기서 사용하는 알고리즘은 이미지를 그리는 데 사용하는 수정 된 알고리즘입니다. 배열 항목이 이미지의 픽셀 데이터 인 척하고 이미지를 왼쪽에서 오른쪽으로 (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"정렬되고 위쪽에서 아래로 가지 않아 왼쪽에서 오른쪽으로 오른쪽입니다. 따라서이 알고리즘은 문제가 있습니다. 열 = 3을 사용하면 작동합니다.

ADG
BE
CF

두 가지를 사용하는 것도 효과가 있습니다

AE
BF
CG
D

그리고 하나는 모든 것을 하나의 열에 넣을 것입니다.

Answer 3

어쨌든 이것은 숙제 과제처럼 보입니다

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