リストを複数の縦列に並べ替える

Question

値の配列 (すでにソート済み) を再ソートして、値を複数 (N) 列に表示し、垂直方向に読み取ることができる優れたアルゴリズムを持っている人はいますか?これは .Net で実装されますが、魔法の機能ではなく、ポータブルなものを希望します。

これが機能する良い例は、方向が垂直に設定されたテーブルとしてレンダリングされる ASP.Net CheckBoxList コントロールです。

入力と出力の例を次に示します。

入力：

列 = 4
配列 = {"A"、"B"、"C"、"D"、"E"、"F"、"G"}

出力：

ACEG
BDF

ありがとう！

更新済み (詳細情報):

私がやろうとしていることについて、もう少し詳しい情報を提供する必要があるかもしれないと思います...ほとんどの場合、この問題は、CheckBoxList の自動バインディング (出力する列と方向を指定でき、正しい順序で項目のテーブルが出力される) を使用することから、jQuery/AJAX を使用してチェックボックス グリッドを作成することに至るまでに発生しました。そこで、CSSを使用して、指定された幅のdivブロック（既知の幅のコンテナdiv内）を使用してそのレイアウトを複製しようとしています。これにより、N個の項目（または列）の後に折り返されます。これは、テーブルにレンダリングすることもできます（ASPの方法のように） .Net がそれを行います。)

順序が水平であることを除けば、すべてうまく機能します。リストに多数の項目がある場合は、垂直列が読みやすくなります。

配列に均等なグリッドを作成するのに十分な項目がない場合は、グリッドの正しい行/列に空のスポットを出力する必要があります。

また、配列に 1 行を作成するのに十分な項目がない場合は、項目を元の順序で 1 行に出力するだけです。

他の入出力は次のとおりです。

列 = 3
配列 = {"A"、"B"、"C"、"D"}

ACD
B

列 = 5
配列 = {"A"、"B"、"C"、"D"、"E"、"F"、"G"、"H"}

アセグ
BDF

列 = 5
配列 = {"A"、"B"、"C"、"D"}

あいうえお

Answer 1

さて、最初の声明で申し訳ありませんが、最初の回答のコメントで説明したように機能させるには、実際にデータを並べ替える必要があります...ヘルパーマトリックスなしでも実行できますが、結果のコードはおそらく非常に複雑であり、マトリックスが数バイトのメモリしか使用しない限り、この小さなヘルパー構成を使用しないのはなぜですか？

以下で私のコードが行うことは、マトリックスの作成です。マトリックスを上から下、次に左から右に記述します（最初の行のすべての列を埋めるために要素がなくなると、最初の行以外の要素の埋めを停止します）。次に、左から右、上から下の順で読みます。基本的にここで行うのは、マトリックスの転置です。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などに簡単に移植できるはずです。大きな魔法は関係ないので、ほとんど普遍的で、移植性があり、クロスプラットフォームです。

---

追加する必要がある1つの重要なこと：

Columnsをゼロに設定すると、このコードはクラッシュします（ゼロ除算、チェックしません）が、Columnsは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

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 (つまり、すべてが 1 行内に描画される) および値 4 以下 (3、2、1 で正常に動作) では正常に機能しますが、5 では正常に機能しません。これはアルゴリズムのせいではなく、制約のせいです。

ACEFG
BD

この制約では、修正された並べ替えデータを取得するために列が上から下に読み取られることが規定されています。しかし、上記では「EFG」はソートされており、上から下ではなく、左から右にソートされています。したがって、このアルゴリズムには問題があります。Columns = 3 を使用すると機能します

ADG
BE
CF

2つ使用しても効果的です

AE
BF
CG
D

そして、すべてを 1 つの列に入れます。

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