如何以随机顺序生成所有集合组合

Question

首先，我甚至不确定术语是否正确，因为我没有找到类似的内容（特别是因为我不知道要使用什么关键词）

问题： 有一群人，我想将他们分成组。我有一套规则来给每个分配打分。我想找到最好的（或者至少是非常好的）分配。

例如，对于一个由四个人 {A,B,C,D} 组成的人群，并将其分配到两个由两个人组成的组中，可能的分配方式如下：

{A,B},{C,D}

{A,C},{B,D}

{A,D},{B,C}

例如，{B,A},{C,D}和{C,D},{A,B}与第一个相同（我不关心组内顺序和组本身的顺序）。

人数、小组数量以及每个小组中适合的人数都是输入。

我的想法是列出每种可能的分配方案，计算它们的得分，并跟踪最佳方案。也就是说，用暴力方法解决问题。由于人口可能很多，所以我想按照随机顺序进行遍历，当时间耗尽时返回找到的最佳结果（可能是当用户感到无聊或认为结果已经足够好了）。人口可以从非常少（列出的四个）到非常多（可能超过200），因此仅仅尝试随机排列而不考虑重复会在小型问题上失败，而在大型问题上则需要采用暴力方法（另外，如果使用纯随机排列，我将不知道何时停止）。

人口数量足够大，无法将所有分配方案列出以便能够打乱它们。因此，我需要一种方法来以随机顺序找到所有可能的分配方案，或者一种方法来生成相应的分配方案，给定一个索引，并使用索引数组并对其进行打乱（后者更好，因为我可以将任务轻松分配到多个服务器上）。

- Daniferrito

---

洗牌方法只需要每次迭代进行一次洗牌。您的问题表述不清，但是考虑以下方法：对于每次迭代：将您的人口进行洗牌并线性分配。所以前两个是0组，接下来两个是1组，依此类推。这只需要每次迭代O（人口大小）的空间。获得相同洗牌（浪费一次迭代）的几率非常低。如果组大小不固定，则无需更改任何内容。只需将前x个放入group0，将下一个y个元素放入group1即可。然而，高效的算法总是会利用有关成本的信息。 - sascha

重新阅读您的问题后，我发现上述方法并不关心所描述的顺序属性（{B,A},{C,D}和{C,D},{A,B}都可以被抽样），但我怀疑这种方法的整体效率仍然很高（因为这些事件的概率很低）。该方法也非常简单。但是，每个有效的算法都取决于您的参数和成本函数，因此改进您的问题可能是明智的选择！ - sascha

我在问题中没有提到（现在我会添加），但人口从非常小的（甚至可能是四个人的例子）到相当大的（现在可能是200，其排列比long可以存储的多）变化很大，因此纯随机化对于那些很快就能完成暴力破解的小问题不起作用。 - Daniferrito

告诉我们一些关于代价函数的内容。盲目搜索是很愚蠢的（黑盒优化非常困难）。 - sascha

这个问题是关于如何生成集合，还是关于如何解决您的优化问题的更大问题？ - samgak

Answer 1

假设我们有N个元素，我们想要将它们组织成G组E个（其中G*E=N）。组的顺序和组内元素的顺序都不重要。最终目标是以随机顺序生成每个解决方案，知道我们无法一次存储所有解决方案。

首先，让我们考虑如何生成一个解决方案。由于顺序并不重要，我们可以通过对组内元素以及组本身按照其第一个元素进行排序来规范化任何解决方案。

例如，如果我们考虑人口{A，B，C，D}, 使用N = 4, G = 2, E = 2，那么解决方案{B,D}, {C,A}可以归一化为{A,C}, {B,D}。在每个组内排序元素（A在C之前），并对组进行排序（A在B之前）。

当解决方案被规范化时，第一组的第一个元素始终是人口的第一个元素。第二个元素是剩下的N-1个元素中的一个，第三个元素是剩下的N-2个元素中的一个，依此类推，但这些元素必须保持排序。因此，对于第一组，存在(N-1)!/((N-E)!*(E-1)!)种可能性。

类似地，下一组的第一个元素是固定的：它们是每个组创建后剩余元素的第一个元素。因此，第（n+1）组（n从0到G-1）的可能性个数为(N-nE-1)!/((N-(n+1)E)!*(E-1)!) = ((G-n)E-1)!/(((G-n-1)E)!*(E-1)!)。

这给了我们一种可能的解决方案索引方法。索引不是单个整数，而是由G个整数组成的数组，该整数n（仍然范围在0到G-1之间）的范围为1到(N-nE-1)!/((N-nE-E)!*(E-1)!)，表示解决方案的第n组（或“第（n+1）组”）。这很容易随机产生并检查重复项。

我们需要找到的最后一件事是如何从相应的整数n生成一组。我们需要从剩余的N-nE-1个元素中选择E-1个元素。此时，您可以想象列出每个组合并选择第（n+1）个。当然，这可以在不生成每个组合的情况下完成：请参见此问题。

对于好奇心，总解数为(GE)!/(G!*(E!)^G)。
在您的示例中，它是(2*2)!/(2!*(2!)^2) = 3。
对于N = 200和E = 2，有6.7e186个解决方案。
对于N = 200和E = 5，有6.6e243个解决方案（我找到的200个元素的最大值）。

此外，对于N = 200和E>13，第一组可能性的数量大于2 ^ 64（因此无法存储在64位整数中），这对于表示索引是有问题的。但只要您不需要具有超过13个元素的组，就可以使用64位整数数组作为索引。

- Nelfeal

Answer 2

你所说的“assignations”是具有固定数量的等大部分的分区。嗯，大多数情况下是这样。如果（组数）*（每组大小）小于或大于您的人口数量，则没有指定应该发生什么。

生成每个可能的分区并不太困难，但仅适用于小型人群或过滤和查找与某些独立标准匹配的任何分区。如果您需要优化或最小化某些内容，则最终会查看整个分区集，这可能是不可行的。

根据实际问题的描述，您想要了解局部搜索和优化算法，其中前面提到的模拟退火是其中一种技术。

---

这里是一个简单的递归Python函数，它生成等大小部分的固定长度分区，顺序不确定。它是我对类似分区问题的答案的专业化，而那个答案本身又是这个答案的专业化。将其转换成JavaScript（使用ES6生成器）应该相当简单。

def special_partitions(population, num_groups, group_size):
    """Yields all partitions with a fixed number of equally sized parts.

    Each yielded partition is a list of length `num_groups`, 
    and each part a tuple of length `group_size.
    """
    assert len(population) == num_groups * group_size
    groups = []  # a list of lists, currently empty 

    def assign(i):
        if i >= len(population): 
            yield list(map(tuple, groups))
        else:
            # try to assign to an existing group, if possible
            for group in groups:
                if len(group) < group_size:
                    group.append(population[i])
                    yield from assign(i + 1)
                    group.pop()

            # assign to an entirely new group, if possible
            if len(groups) < num_groups:
                groups.append([population[i]])
                yield from assign(i + 1)
                groups.pop()

    yield from assign(0)

for partition in special_partitions('ABCD', 2, 2):
    print(partition)

print()

for partition in special_partitions('ABCDEF', 2, 3):
    print(partition)

执行时，这将打印出：

[('A', 'B'), ('C', 'D')]
[('A', 'C'), ('B', 'D')]
[('A', 'D'), ('B', 'C')]

[('A', 'B', 'C'), ('D', 'E', 'F')]
[('A', 'B', 'D'), ('C', 'E', 'F')]
[('A', 'B', 'E'), ('C', 'D', 'F')]
[('A', 'B', 'F'), ('C', 'D', 'E')]
[('A', 'C', 'D'), ('B', 'E', 'F')]
[('A', 'C', 'E'), ('B', 'D', 'F')]
[('A', 'C', 'F'), ('B', 'D', 'E')]
[('A', 'D', 'E'), ('B', 'C', 'F')]
[('A', 'D', 'F'), ('B', 'C', 'E')]
[('A', 'E', 'F'), ('B', 'C', 'D')]

- user6732794

Answer 3

一个简单的递归算法生成这些配对的方法是将第一个元素与其余元素中的每个元素配对，对于这些组合中的每一对，递归地生成其余元素的所有配对。对于组，生成由第一个元素和其余元素的所有组合组成的所有组，然后对剩余部分进行递归。

您可以通过以下方式计算可能的组集数量：

public static int numGroupingCombinations(int n, int groupSize)
{
    if(n % groupSize != 0)
        return 0;   // n must be a multiple of groupSize

    int count = 1;
    while(n > groupSize)
    {
        count *= nCr(n - 1, groupSize - 1);
        n -= groupSize;
    }
    return count;
}

public static int nCr(int n, int r)
{
    int ret = 1;
    for (int k = 0; k < r; k++) {
        ret = ret * (n-k) / (k+1);
    }
    return ret; 
}

所以我需要一种方法以任意顺序找到所有可能的分配方式，或者给定一个索引生成相应的分配方式，并使用索引数组并对其进行洗牌（后者更好，因为我可以轻松地将任务分配到多个服务器）。

要从索引生成分组，请通过将索引与可能组合数取模来选择要与第一个元素分组的项目的组合，并使用此结果使用此算法生成组合。然后将索引除以该数字，并递归生成集合的其余部分。

public static void generateGrouping(String[] elements, int groupSize, int start, int index)
{
    if(elements.length % groupSize != 0)
        return;

    int remainingSize = elements.length - start;
    if(remainingSize == 0)
    {
        // output the elements:
        for(int i = 0; i < elements.length; i += groupSize)
        {
            System.out.print("[");
            for(int j = 0; j < groupSize; j++)
                System.out.print(((j==0)?"":",")+elements[i+j]);
            System.out.print("]");
        }
        System.out.println("");
        return; 
    }

    int combinations = nCr(remainingSize - 1, groupSize - 1);

    // decide which combination of remaining elements to pair the first element with:
    int[] combination = getKthCombination(remainingSize - 1, groupSize - 1, index % combinations);

    // swap elements into place
    for(int i = 0; i < groupSize - 1; i++)
    {
        String temp = elements[start + 1 + i];
        elements[start + 1 + i] = elements[start + 1 + combination[i]];
        elements[start + 1 + combination[i]] = temp;
    }

    generateGrouping(elements, groupSize, start + groupSize, index / combinations);

    // swap them back:
    for(int i = groupSize - 2; i >= 0; i--)
    {
        String temp = elements[start + 1 + i];
        elements[start + 1 + i] = elements[start + 1 + combination[i]];
        elements[start + 1 + combination[i]] = temp;
    }
}

public static void getKthCombination(int n, int r, int k, int[] c, int start, int offset)
{
    if(r == 0)
        return;
    if(r == n)
    {
        for(int i = 0; i < r; i++)
            c[start + i] = i + offset;
        return;
    }
    int count = nCr(n - 1, r - 1);
    if(k < count)
    {
        c[start] = offset;
        getKthCombination(n-1, r-1, k, c, start + 1, offset + 1);
        return;
    }
    getKthCombination(n-1, r, k-count, c, start, offset + 1);
}

public static int[] getKthCombination(int n, int r, int k)
{
    int[] c = new int[r];
    getKthCombination(n, r, k, c, 0, 0);

    return c;
}

演示

start参数表示列表的起始位置，因此在调用顶层函数时，请将其设置为零。该函数可以很容易地重写为迭代函数。如果交换对象的开销很大，也可以传递索引数组而不是要分组的对象数组。

- samgak

---

每个组中的人数可能会有所不同（它们不仅限于两人组）。我认为这个算法可以被扩展到更大的组。是吗？如果是这样，这似乎是完美的答案。 - Daniferrito

可以的。例如，对于3个元素的组，您将把第一个元素与其他2个元素的每个可能组合分组，将索引模除((remainingSize - 1) * (remainingSize - 2))/2，并在递归时将开始增加3。 - samgak

要编写一个处理任意组大小的通用算法，您需要在每个步骤中计算和生成剩余元素的第n个组合。您可以使用此算法：nth combination。 - samgak

Answer 4

也许采用模拟退火方法会奏效。您可以从一个非最优解开始，并使用启发式方法进行迭代以改进。

您的评分标准可能会帮助您选择初始解决方案，例如，首先制作最佳评分的第一组，然后使用剩余的内容制作最佳评分的第二组，以此类推。

“相邻状态”的良好选择可能会暗示您的评分标准，但至少，如果它们通过单个交换不同，则可以将两个状态视为相邻。

因此，算法的迭代部分将尝试大量随机抽样的交换，并根据退火时间表选择全局得分提高的交换。

我希望您能找到更好的相邻状态选择！也就是说，我希望您能找到更好的规则，根据您的评分标准进行迭代性改进。

- Codie CodeMonkey

---

与详尽的生成和评分相比，我肯定更喜欢您的方法。还可以构建某种混合方法：只需构建N个不同的起始位置，并使用1/N次SA（一种在许多组合算法中使用的重启策略：例如所有kmeans实现都这样做）。 - sascha

Answer 5

如果您有足够大的人口，无法将所有的赋值都存储在内存中，也不太可能测试所有可能的赋值，那么最简单的方法就是随机选择测试赋值。例如：

repeat 
    randomly shuffle population
    put 1st n/2 members of the shuffled pop into assig1 and 2nd n/2 into assig2
    score assignation and record it if best so far
until bored

如果你有一个庞大的人口，那么重复测试不太可能会导致效率损失，因为你不太可能再次遇到相同的分配。

根据你的评分规则，选择下一个要测试的分配可能更有效率，例如在迄今为止找到的最佳分配之间交换一对成员，但你没有提供足够的信息来确定是否是这种情况。

- Penguino

---

这个答案不涵盖我之前评论中未提及的内容，并且仅处理两个赋值组的特殊情况。 - sascha

我正在你评论时编写它。将前n/k个成员放入第一组等以得分k组分配的方法只是一个简单的变化。 - Penguino

Answer 6

这里提供一种针对您的优化问题的方法（忽略您基于排列的方法）。

我将问题表述为混合整数问题，并使用专门的求解器计算出好的解决方案。

由于您的问题可能没有很好地形式化，因此可能需要进行一些修改。但总体的信息是：这个方法将很难被击败！

代码

import numpy as np
from cvxpy import *

""" Parameters """
N_POPULATION = 50
GROUPSIZES = [3, 6, 12, 12, 17]
assert sum(GROUPSIZES) == N_POPULATION
N_GROUPS = len(GROUPSIZES)
OBJ_FACTORS = [0.4, 0.1, 0.15, 0.35]  # age is the most important

""" Create fake data """
age_vector = np.clip(np.random.normal(loc=35.0, scale=10.0, size=N_POPULATION).astype(int), 0, np.inf)
height_vector = np.clip(np.random.normal(loc=180.0, scale=15.0, size=N_POPULATION).astype(int), 0, np.inf)
weight_vector = np.clip(np.random.normal(loc=85, scale=20, size=N_POPULATION).astype(int), 0, np.inf)
skill_vector = np.random.randint(0, 100, N_POPULATION)

""" Calculate a-priori stats """
age_mean, height_mean, weight_mean, skill_mean = np.mean(age_vector), np.mean(height_vector), \
                                                 np.mean(weight_vector), np.mean(skill_vector)


""" Build optimization-model """
# Variables
X = Bool(N_POPULATION, N_GROUPS)  # 1 if part of group
D = Variable(4, N_GROUPS)  # aux-var for deviation-norm

# Constraints
constraints = []

# (1) each person is exactly in one group
for p in range(N_POPULATION):
    constraints.append(sum_entries(X[p, :]) == 1)

# (2) each group has exactly n (a-priori known) members
for g_ind, g_size in enumerate(GROUPSIZES):
    constraints.append(sum_entries(X[:, g_ind]) == g_size)

# Objective: minimize deviation from global-statistics within each group
#   (ugly code; could be improved a lot!)
group_deviations = [[], [], [], []]  # age, height, weight, skill
for g_ind, g_size in enumerate(GROUPSIZES):
    group_deviations[0].append((sum_entries(mul_elemwise(age_vector, X[:, g_ind])) / g_size) - age_mean)
    group_deviations[1].append((sum_entries(mul_elemwise(height_vector, X[:, g_ind])) / g_size) - height_mean)
    group_deviations[2].append((sum_entries(mul_elemwise(weight_vector, X[:, g_ind])) / g_size) - weight_mean)
    group_deviations[3].append((sum_entries(mul_elemwise(skill_vector, X[:, g_ind])) / g_size) - skill_mean)

for i in range(4):
    for g in range(N_GROUPS):
        constraints.append(D[i,g] >= abs(group_deviations[i][g]))

obj_parts = [sum_entries(OBJ_FACTORS[i] * D[i, :]) for i in range(4)]

objective = Minimize(sum(obj_parts))

""" Build optimization-problem & solve """
problem = Problem(objective, constraints)
problem.solve(solver=GUROBI, verbose=True, TimeLimit=120)  # might need to use non-commercial solver here
print('Min-objective: ', problem.value)

""" Evaluate solution """
filled_groups = [[] for g in range(N_GROUPS)]
for g_ind, g_size in enumerate(GROUPSIZES):
    for p in range(N_POPULATION):
        if np.isclose(X[p, g_ind].value, 1.0):
            filled_groups[g_ind].append(p)
for g_ind, g_size in enumerate(GROUPSIZES):
    print('Group: ', g_ind, ' of size: ', g_size)
    print(' ' + str(filled_groups[g_ind]))

group_stats = []
for g in range(N_GROUPS):
    age_mean_in_group = age_vector[filled_groups[g]].mean()
    height_mean_in_group = height_vector[filled_groups[g]].mean()
    weight_mean_in_group = weight_vector[filled_groups[g]].mean()
    skill_mean_in_group = skill_vector[filled_groups[g]].mean()
    group_stats.append((age_mean_in_group, height_mean_in_group, weight_mean_in_group, skill_mean_in_group))
print('group-assignment solution means: ')
for g in range(N_GROUPS):
    print(np.round(group_stats[g], 1))

""" Compare with input """
input_data = np.vstack((age_vector, height_vector, weight_vector, skill_vector))
print('input-means')
print(age_mean, height_mean, weight_mean, skill_mean)
print('input-data')
print(input_data)

输出（2分钟时间限制；商业求解器）

Time limit reached
Best objective 9.612058823514e-01, best bound 4.784117647059e-01, gap 50.2280%
('Min-objective: ', 0.961205882351435)
('Group: ', 0, ' of size: ', 3)
 [16, 20, 27]
('Group: ', 1, ' of size: ', 6)
 [26, 32, 34, 45, 47, 49]
('Group: ', 2, ' of size: ', 12)
 [0, 6, 10, 12, 15, 21, 24, 30, 38, 42, 43, 48]
('Group: ', 3, ' of size: ', 12)
 [2, 3, 13, 17, 19, 22, 23, 25, 31, 36, 37, 40]
('Group: ', 4, ' of size: ', 17)
 [1, 4, 5, 7, 8, 9, 11, 14, 18, 28, 29, 33, 35, 39, 41, 44, 46]
group-assignment solution means: 
[  33.3  179.3   83.7   49. ]
[  33.8  178.2   84.3   49.2]
[  33.9  178.7   83.8   49.1]
[  33.8  179.1   84.1   49.2]
[  34.   179.6   84.7   49. ]
input-means
(33.859999999999999, 179.06, 84.239999999999995, 49.100000000000001)
input-data
[[  22.   35.   28.   32.   41.   26.   25.   37.   32.   26.   36.   36.
    27.   34.   38.   38.   38.   47.   35.   35.   34.   30.   38.   34.
    31.   21.   25.   28.   22.   40.   30.   18.   32.   46.   38.   38.
    49.   20.   53.   32.   49.   44.   44.   42.   29.   39.   21.   36.
    29.   33.]
 [ 161.  158.  177.  195.  197.  206.  169.  182.  182.  198.  165.  185.
   171.  175.  176.  176.  172.  196.  186.  172.  184.  198.  172.  162.
   171.  175.  178.  182.  163.  176.  192.  182.  187.  161.  158.  191.
   182.  164.  178.  174.  197.  156.  176.  196.  170.  197.  192.  171.
   191.  178.]
 [  85.  103.   99.   93.   71.  109.   63.   87.   60.   94.   48.  122.
    56.   84.   69.  162.  104.   71.   92.   97.  101.   66.   58.   69.
    88.   69.   80.   46.   74.   61.   25.   74.   59.   69.  112.   82.
   104.   62.   98.   84.  129.   71.   98.  107.  111.  117.   81.   74.
   110.   64.]
 [  81.   67.   49.   74.   65.   93.   25.    7.   99.   34.   37.    1.
    25.    1.   96.   36.   39.   41.   33.   28.   17.   95.   11.   80.
    27.   78.   97.   91.   77.   88.   29.   54.   16.   67.   26.   13.
    31.   57.   84.    3.   87.    7.   99.   35.   12.   44.   71.   43.
    16.   69.]]

解决方案说明

• 这个解决方案看起来非常不错（关于平均偏差），而且只用了2分钟（我们事先决定了时间限制）
• 我们还得到了紧密的界限：0.961是我们的解决方案；我们知道它不能低于4.784

可重复性

• 代码使用了numpy和cvxpy
• 使用了商业求解器
  • 您可能需要使用非商业MIP求解器（支持提前终止的时间限制；获取当前最佳解决方案）
  • 在cvxpy中支持的有效开源MIP求解器有：cbc（目前无法设置时间限制）和glpk（请查阅文档以获取时间限制支持）

模型决策

• 该代码使用L1范数惩罚，这会导致一个MIP问题
• 根据您的问题，使用L2范数惩罚可能是明智的（一个大偏差比许多小偏差更严重），这将导致一个更难的问题（MIQP / MISOCP）

- sascha