算法將列表分成組

我有一個名稱列表。算法將列表分成組

我想將此列表分成指定大小的組。所有組應該等於或小於指定的大小，儘可能在組間大小相等，儘可能接近指定的大小。

什麼算法（如果可能，請使用Java-esque僞代碼！）確定最合適的組大小？

例如：

列表包含13名 - 最大團隊尺寸3. 輸出（組大小）：3，3,3，2,2

列表包含13名 - 最大團隊規模4 。輸出：4，3，3，3

列表中包含31名 - 最大團隊規模5 輸出：5,5，5,4，4,4，4

列表中包含31名 - 團隊規模最大爲6. 輸出：6,5，5,5，5,5

列表中包含31名 - 最大團隊規模10 輸出：8,8，8,7

來源

2012-01-12 Keith

這功課嗎？你有什麼嘗試？ – 2012-01-12 14:31:42

1,1,1,1,1,1,1,1,1,1,1,1,1在每個組中最多有3個項目，並且組大小比您的示例中的要大。 – Robert 2012-01-12 14:39:41

預期產出不明確。例如，輸出是什麼：列表包含31個名稱 - 最大團隊規模10 – 2012-01-12 14:50:19

這很簡單。您計算N div M的結果並添加1以獲得正確的數組數（N是列表長度，M是最大團隊大小），然後在所有數組上迭代以添加項目例如：43個名字，最大球隊號碼4 => 43 mod 4 + 1 = 11，仍然是3.如此11陣列（10與4以及1與3）

來源

2012-01-12 14:38:31 Grooveek

你可能是指'div'，而不是'mod'，因爲'43 mod 4'是'3'，而不是'10'（'mod'的意思是*餘數*，不是整數除法）。如果'M'將N除以餘數，'+ 1'也不起作用。你需要做'（N + M-1）div M'來獲得你正在尋找的結果。 – dasblinkenlight 2012-01-12 15:06:39

你是對的MOD，我洗牌:-D – Grooveek 2012-01-12 15:10:57

我認爲這個答案是如此明顯，它的簡單性，我忽視了它的解決方案。 :) – Keith 2012-01-13 04:37:21

我不會寫代碼這一點，但

如果列表大小是團隊規模最大團隊規模，劃分的倍數來獲得組的數量，所有最大規模的，停止。
整數 - 將列表大小除以最大團隊大小，然後添加一個。這是組的數量。
從下一個更高的倍數中減去列表大小;這是比最大規模小一個的團隊數量。

這顯然只適用於接近工作的輸入;如果最大團隊規模與列表大小相比較大，則會失敗。

來源

2012-01-12 14:36:03

如果列表中的項目數量爲N，在子表項的最大數量爲K，你的問題的解決方案來自求解Linear Diophantine Equation

K*x + (K-1)*y = N

與附加約束

x > 0 
y >= 0

凡x是確切的大小K的子列表的數目，並且是y長度K-1的子列表的數目。

編輯：由於係數方程總是關閉由一個從彼此，該解決方案是相當簡單：

int m = (N+K-1)/K; 
int x = N - (K-1)*m; // Number of "full" lists 
int y = K*M - N;  // Number of off-by-one lists

實施例1：

N = 31, K = 5 
m = (31+5-1)/5 = 7 
x = 31 - (5-1)*7 = 3 // 3 lists of 5 items 
y = 5*7 - 31 = 4  // 4 lists of 4 items

示例2：

N = 32, K = 4 
m = (32+4-1)/4 = 8 
x = 32 - (4-1)*8 = 8 // 8 lists of 4 items 
y = 4*8 - 32 = 0  // no lists of 3 items

在網上查找求解線性丟番圖方程的算法 - 如果您理解了 Euclidean algorithm那麼它並不複雜。沒有約束的方程的解的數量是無限的，但是一旦你添加了約束，你應該得到一個解決方案。

來源

2012-01-12 14:42:23 dasblinkenlight

我認爲算法的變化有一些基於31的列表，最大大小爲10的例子。 – Keith 2012-01-12 21:08:51

public class Q { 
public static void q(int size, int maxTeamSize) { 
    int numOfTeams = size/maxTeamSize; 
    int mod = size % maxTeamSize; 
    numOfTeams += (mod > 0) ? 1 : 0; 
    System.out.print("\n(" + size + ":" + maxTeamSize + ")"); 
    for (int i = 0; i < numOfTeams; i++) { 
     System.out.print(" " + (size/numOfTeams + ((i < mod) ? 1 : 0))); 
    } 
} 

public static void main(String[] args) { 
    q(13, 3); 
    q(12, 4); 
    q(31, 5); 
    q(31, 6); 
} 
}

來源

2012-01-12 15:29:14 andrey

這是一個整潔的算法，但會導致更多的小組數量。我的目標是儘可能地讓儘可能多的團隊儘可能接近最大團隊規模。 – Keith 2012-01-12 22:20:27

算法將列表分成組

回答

相關問題