求文件在目录间均等分配的有效算法（无初始文件残留）

需求说明 #

• 分配完成后，所有目录中无初始文件残留；
• 分配后所有目录的文件数量均等，该数量由特定算法确定；
• 若存在剩余文件不足以给每个目录再分配一个，剩余文件需归属于初始文件数多于分配数的目录；
• 不考虑总文件数小于目录数的情况。

目前找不到合适的成熟算法，自己实现的算法过于复杂且无法适配所有场景。

分配数计算方式 #

已知各目录文件数及总文件数，按以下步骤计算分配数：

1. 计算总文件数与各目录文件数的最小差值：

min_diff = min(total_number_of_files - files_number_in_directory[i])

2. 计算每目录平均文件数：

avg = total_number_of_files / directories_number

3. 取上述两个值中的较小值作为分配数：

dis_number = min(min_diff, avg)

示例场景 #

1. 最简场景：各目录初始文件数相等 #

输入：

directory_1: file_1_1, file_1_2
directory_2: file_2_1, file_2_2
directory_3: file_3_1, file_3_2

输出：

directory_1: file_2_1, file_3_2
directory_2: file_3_1, file_1_2
directory_3: file_1_1, file_2_2

2. 存在剩余文件的场景 #

输入：

dir_1: file_1_1, file_1_2, ..., file_1_10
dir_2: file_2_1, file_2_2
dir_3: file_3_1, file_3_2

输出：

dir_1: file_2_1,  file_2_2, file_3_1, file_3_2
dir_2: file_1_1, file_1_2, file_1_3, file_1_4
dir_3: file_1_5, file_1_6, file_1_7, file_1_8

extra: file_1_9, file_1_10

分配数为14 - 10 = 4，可将dir2和dir3的所有文件移入dir1，但file_1_9和file_1_10无法分配。

当前算法实现逻辑（存在缺陷） #

核心思路：每次迭代仅移动等于目录中最小文件数的文件，类似置换操作，每次使用新偏移量；每一步忽略已移动文件，处理剩余原文件；当出现文件数为0的目录时，从文件数最多的目录取文件填充，填充数量为当前目录中的最小文件数或当前平均值。

具体步骤：
将目录存储为带索引的vector，初始化temp_directories，同时创建存储各目录文件数的int数组。

1. 找到目录中的minimum_files_number；
2. 若minimum_files_number != 0：
   2.1 随机初始化shift，取值范围为[1, n - 1]，n为目录数；
   2.2 将directory-i的最后一个元素放入temp_directory的i + shift索引位置，并从directory-i中执行pop_back；
   2.3 重复步骤2.2共minimum_files_number次；
3. 若minimum_files_number == 0：
   3.1 标记文件数为0的目录（0-directories）；
   3.2 检查current_total_number_of_files > ((number_of_0-directories + 1) * minimum_files_number)：
   3.2.1 是：初始化current_fill_number = minimum_files_number；
   3.2.2 否：初始化current_fill_number = current_avg_number，其中current_avg_number = current_total_number_of_files / directories_number；
   3.3 从文件数最多的目录向0-directories转移文件：
   3.3.1 找到max_index——文件数最多的目录索引；
   3.3.2 将directory-max_index的最后一个元素push_back到0-directory-i，并从directory-max_index执行pop_back；
   3.3.3 重复步骤3.3.1和3.3.2共current_fill_number次；
   3.4 将未标记为0-directories的目录送入步骤2处理，此时minimum_file_number = current_fill_number；

算法执行示例 #

初始目录文件数：

dir_index: 0   1   2   3
files:     4   8  13  10

初始minimum_file_number为4，随机取shift=2，置换关系为：

(0   1   2   3)
(2   3   0   1)

将directory-1的最后4个文件放入temp_directory-3，以此类推，操作后目录文件数变为[0 4 9 6]。出现0文件目录后，从文件数为9和6的目录取文件填充，得到[4 4 5 6]，对[4 5 6]重复步骤2，操作后变为[0 0 1 2]，此时文件数小于目录数，归入extra组。

内容的提问来源于stack exchange，提问作者su-mrak