如何将数组分成漂亮的行和列网格，其中列始终对齐（所有行都是偶数，或者都是奇数）？

Question

什么是算法（在 JavaScript/TypeScript 中），它可以将数组分成行和列，其中列总是跨行排列（即所有行要么是奇数，要么所有行都是偶数，而不是奇数和偶数的混合）？

输入是每行允许的

maxColumns

和数组。然后，它将数组分成数组的数组，不大于 maxColumns，这样所有行都是偶数，或者所有行都是奇数，and 每个后续行可以比前一行少不少于 2 个。在我看来，这使得网格看起来不错。

这里有一些要处理的例子，网格应该如何布局：

# length 6, maxColumns 5
# nope: rows are more than 2 apart
x x x x x
    x

# same, length 6, maxColumns: 5
# yep, both even *and* rows are no less than 2 apart
x x x x
  x x   

# length: 7, maxColumns: 6
# nope: can't mix even and odd...
x x x x x x
      x

# same, length: 7, maxColumns: 6
# close, but still can't mix even/odd
x x x x
  x x
   x

# same, length: 7, maxColumns: 6
# yep!, rows are no more than 2 apart, and both odd
x x x
x x x
  x

# length: 17, maxColumns: 7
# yep!, rows are no more than 2 apart, and both odd
x x x x x x x
  x x x x x
    x x x
      x
      x

# length: 17, maxColumns: 6
# yep!, rows are no more than 2 apart, and both odd
x x x x x
x x x x x
  x x x
  x x x
    x

是否有一个简单的方程或算法可以实现这一点？我花了一个多小时思考这个问题，但没有取得太大进展，因为我的头脑感觉很复杂。

据我所知：

function layout(length: number, maxColumns: number) {
  const rows: Array<number> = []
  if (length % maxColumns === 0) {
    // 7 7 7
    while (length) {
      rows.push(maxColumns)
      length -= maxColumns
    }
  } else if (isEven(maxColumns)) {
    
  }
  return rows
}

Answer 1

一些观察：

• 输出中的所有行要么都是偶数，要么都是奇数。一旦我们为第一行选择奇/偶奇偶校验，这将决定所有接下来的行的奇偶校验。

• 当

  length

  为奇数时，这意味着第一行的长度应该是奇数，否则我们永远无法匹配该长度。当

  length

  为偶数时，我们可以从任一奇偶校验开始。

• 要知道我们是否真的可以从某个行大小开始，我们应该检查如果接下来的行大小都减小的话，总数会是多少。将达到的总大小遵循数学公式：

  triangle = ((maxColumns + 1) >> 1) * ((maxColumns + 2) >> 1)
  

  其中

  triangle

  是行达到的总大小，如果

  >> 1

  表示整数除法，则可以用

  / 2

  替换。

  现在，如果该三角形的总和大于要实现的

  length

  ，我们应该减小第一行的宽度。根据奇偶校验约束，我们可以用 1 或 2 来减少（参见前面的要点）。

当用 JavaScript 编码时，这就产生了这个算法：

function* distribute(length, maxColumns) {
    let dec = 1;
    if (length % 2 > 0) { // length is odd 
        maxColumns -= 1 - (maxColumns % 2); // ensure maxColumns is odd too
        dec = 2; // Step with decreases of 2 to maintain an odd width
    }
    
    while (length > 0) {
        while (true) {
            // Calculate what the size would be if we decrease every next row from this point on:
            const triangle = ((maxColumns + 1) >> 1) * ((maxColumns + 2) >> 1);
            if (triangle <= length) break; // That would be OK...
            // No, that would overshoot the targeted length; try a different width:
            maxColumns -= dec;
            if (maxColumns <= 0) throw "this should not happen";
        }
        yield maxColumns; // Or push it to an array
        length -= maxColumns; // Consume that row
        dec = 2; // Once a row has been produced, we should maintain the same parity.
    }
}

// Some inputs...
const tests = [
    [1, 5],
    [2, 5],
    [3, 5],
    [4, 5],
    [5, 5],
    [6, 5],
    [7, 6],
    [8, 6],
    [9, 6],
    [10, 6],
    [11, 6],
    [12, 6],
    [13, 6],
    [14, 6],
    [17, 7]    
];

// Run the function with those inputs and print the outputs
for (const [length, maxColumns] of tests) {
    const result = [...distribute(length, maxColumns)];
    console.log(length, maxColumns, JSON.stringify(result));
}

此代码片段仅输出宽度数组。每个宽度代表您在示例中描绘的行的大小。