将项目均匀分配到3列的算法

Question

我正在寻找一种算法，可以将1到多个项目均匀地分配到三列中。任何一列都不能比其他列多一个项目。我在下面列出了一个示例，Col1、Col2和Col3的总和应该等于ItemCount。

编辑：此外，这些项目是字母数字，并且必须按列顺序排序。列中的最后一个项目必须小于下一列中的第一个项目。

Items         Col1,Col2,Col3
A             A
AB            A,B
ABC           A,B,C
ABCD          AB,C,D
ABCDE         AB,CD,E
ABCDEF        AB,CD,EF
ABCDEFG       ABC,DE,FG
ABCDEFGH      ABC,DEF,GH
ABCDEFGHI     ABC,DEF,GHI
ABCDEFHGIJ    ABCD,EFG,HIJ
ABCDEFHGIJK   ABCD,EFGH,IJK

- Brian Bolton

---

请先花些时间发表正确的问题。七位人员为回答你的问题付出了很大的努力，现在问题已经改变，使得他们的工作大部分都白费了。 - RichieHindle

ABCD的分布可能是A|BC|D还是A|B|CD？ - christopheml

Answer 1

这里是 Python 的代码：

NumCols = 3
DATA = "ABCDEFGHIJK"

for ItemCount in range(1, 12):
    subdata = DATA[:ItemCount]

    Col1Count = (ItemCount + NumCols - 1) / NumCols
    Col2Count = (ItemCount + NumCols - 2) / NumCols
    Col3Count = (ItemCount + NumCols - 3) / NumCols

    Col1 = subdata[:Col1Count]
    Col2 = subdata[Col1Count:Col1Count+Col2Count]
    Col3 = subdata[Col1Count+Col2Count:]

    print "%2d   %5s  %5s  %5s" % (ItemCount, Col1, Col2, Col3)

# Prints:
#  1       A              
#  2       A      B       
#  3       A      B      C
#  4      AB      C      D
#  5      AB     CD      E
#  6      AB     CD     EF
#  7     ABC     DE     FG
#  8     ABC    DEF     GH
#  9     ABC    DEF    GHI
# 10    ABCD    EFG    HIJ
# 11    ABCD   EFGH    IJK

- RichieHindle

---

很抱歉第一次没有理解清楚问题。我认为你的答案可以解决问题。我可以先使用任何算法对项目进行排序，然后使用你的方法来确定每列应该有多少个项目。再次对问题不够清晰表示歉意。 - Brian Bolton

@Brian：没问题。现在已经更新以回答你的更新问题。 - RichieHindle

Answer 2

由于提问者在我回答后决定更改问题，所以这个答案现在已经过时。我懒得删除它。

function getColumnItemCount(int items, int column) {
    return (int) (items / 3) + (((items % 3) >= (column + 1)) ? 1 : 0);
}

- Bombe

---

一旦我弄清楚“column”是从0开始计数而不是序数列号，这就很有用了。 :D - pchap10k

大多数答案在处理少量内容时都不起作用。尝试使用带有5个值的批准解决方案，您最终将只得到两列！这个解决方案似乎始终可靠，无论您投入什么 - 如果您将其泛化以传递3作为列计数变量，则对于任何用例都是完美的(: - pospi

Answer 3

这个问题是我找到的与我的问题最接近的，所以我将发布我想出来的解决方案。使用JavaScript：

var items = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K']
var columns = [[], [], []]
for (var i=0; i<items.length; i++) {
  columns[Math.floor(i * columns.length / items.length)].push(items[i])
}
console.log(columns)

- gsf

Answer 4

仅为您提供提示（它很容易，所以自己想出来）

将ItemCount除以3取整数部分。这是每列中至少存在的数量。

现在你要做的是ItemCount % 3（模数），它是1或2（因为否则它可以被3整除，对吧），然后你进行分配。

- Johannes Rudolph

Answer 5

我需要一个C#版本，这是我想出来的（算法来自Richie的答案）：

// Start with 11 values
var data = "ABCDEFGHIJK";

// Split in 3 columns
var columnCount = 3;

// Find out how many values to display in each column
var columnCounts = new int[columnCount];
for (int i = 0; i < columnCount; i++)
    columnCounts[i] = (data.Count() + columnCount - (i + 1)) / columnCount;

// Allocate each value to the appropriate column
int iData = 0;
for (int i = 0; i < columnCount; i++)
for (int j = 0; j < columnCounts[i]; j++)
    Console.WriteLine("{0} -> Column {1}", data[iData++], i + 1);

// PRINTS:
//    A -> Column 1
//    B -> Column 1
//    C -> Column 1
//    D -> Column 1
//    E -> Column 2
//    F -> Column 2
//    G -> Column 2
//    H -> Column 2
//    I -> Column 3
//    J -> Column 3
//    K -> Column 3

- Xavier Poinas

Answer 6

这很简单

假设你有N个元素，索引从0到N-1，并且有列从0到2，第i个元素将放在第i mod 3列（其中mod是取模运算符，在C、C++和其他一些语言中表示为%）

- ThibThib

---

阅读了您的回复后，我想：“嗯，这很容易，为什么我没想到呢。”然后我意识到问题还有更多。请查看编辑。 - Brian Bolton

Answer 7

你只是想知道每列中的项目数量吗？如果你有n个项目，那么计数将如下：

round(n/3), round(n/3), n-2*round(n/3)

其中，“round”是将数字四舍五入到最近的整数（例如，round(x)=(int)(x+0.5)）

如果你想要实际放置这些项目，请尝试类似于以下Python风格的伪代码：

def columnize(items):
  i=0
  answer=[ [], [], [] ]
  for it in items:
    answer[i%3] += it
    i += 1
  return answer

- redtuna

---

你的第一行代码将10分配为（3，3，4），并将11分配为（4，4，3）。 - Steve Jessop

你说得对，确实如此。这些数字的求和是正确的。根据我所读到的要求，解决方案符合要求：每列中的项目数不超过其他列的项目数多出一个。如果你希望值反映出从第二个代码块中获得的计数，那么我认为你可以使用RichieHindle上面的代码。 - redtuna

好的 - 既然规格已经改变了。 - Steve Jessop

Answer 8

这是我为所有像我一样的PHP黑客们（是的，因为关联而感到内疚！）拼凑出来的PHP版本。

function column_item_count($items, $column, $maxcolumns) {
    return round($items / $maxcolumns) + (($items % $maxcolumns) >= $column ? 1 : 0);
}

而你可以这样调用它...

$cnt = sizeof($an_array_of_data);
$col1_cnt = column_item_count($cnt,1,3);
$col2_cnt = column_item_count($cnt,2,3);
$col3_cnt = column_item_count($cnt,3,3);

这个功劳应归功于上面用 Java (?) 提供它的 @Bombe。

NB：此函数期望您传递一个序数列号，即第一列= 1，第二列= 2，依此类推...

- pchap10k