mysql - 需要不同的数字组排列

Question

我有从 1 到 36 的数字。我想做的是将所有这些数字分成三个组，并计算出组的所有各种排列。

每组必须包含 12 个数字，从 1 到 36

每个排列中，一个数字不能出现在多个组中

这是一个例子......

Permutation 1
Group 1: 1,2,3,4,5,6,7,8,9,10,11,12
Group 2: 13,14,15,16,17,18,19,20,21,22,23,24
Group 3: 25,26,27,28,29,30,31,32,33,34,35,36

Permutation 2
Group 1: 1,2,3,4,5,6,7,8,9,10,11,13
Group 2: 12,14,15,16,17,18,19,20,21,22,23,24
Group 3: 25,26,27,28,29,30,31,32,33,34,35,36

Permutation 3
Group 1: 1,2,3,4,5,6,7,8,9,10,11,14
Group 2: 12,11,15,16,17,18,19,20,21,22,23,24
Group 3: 25,26,27,28,29,30,31,32,33,34,35,36

这只是三个例子，我预计还会有数百万/数十亿

Answer 1

下面的分析假设组的顺序很重要 - 也就是说，如果数字是 1、2、3，则分组 [{1},{2},{3}] 与分组 [{3 },{2},{1}](事实上，从这组数字中得出六个不同的分组)。

对于您的情况，我们该如何进行？好吧，我们首先要选择第一组。有 36 种选择 12 种方法来执行此操作，即 (36!)/[(12!)(24!)] = 1,251,677,700 种方法。然后我们必须选择第二组。有 24 种选择 12 种方法来执行此操作，即 (24!)/[(12!)(12!)] = 2,704,156 种方法。由于第二个选择已经以第一个选择为条件，我们可以通过将数字相乘得到三组的总取法；从 36 个池子中选择三个相等的 12 组的方法总数为 3,384,731,762,521,200。如果使用 8 位字节表示数字，那么存储每个列表将至少需要约 3 个五字节(好吧，我猜乘以列表的大小，即 36 个字节，所以更像是约 108 个五字节)。这是大量数据，需要一些时间来生成，并且需要大量磁盘空间来存储，因此请注意这一点。

实际实现这一点并没有那么可怕。然而，我认为如果可能的话，在 SQL 中实现这一点将会遇到很大的困难。纯 SQL 没有返回超过 n^2 个条目的操作(对于简单的交叉联接)，因此获得如此大量的结果将需要大量的联接。此外，我并没有觉得如何概括该过程，因为纯 SQL 无法进行一般递归，因此无法进行可变数量的连接。

您可以使用过程语言生成分组，然后将分组写入数据库。不知道这是否是你想要的。

n = 36

group1[1...12] = []
group2[1...12] = []
group3[1...12] = []

function Choose(input[1...n], m, minIndex, group)

    if minIndex + m > n + 1 then
        return

    if m = 0 then

        if group = group1 then
            Choose(input[1...n], 12, 1, group2)

        else if group = group2 then
            group3[1...12] = input[1...12]
            print group1, group2, group3

    for i = i to n do

        group[12 - m + 1] = input[i]
        Choose(input[1 ... i - 1].input[i + 1 ... n], m - 1, i, group)

当你像 Choose([1...36], 12, 1, group1) 这样调用它时，它所做的就是用长度为 12 的所有可能的有序子序列填充 group1。 ，m = 0 且 group = group1，因此调用 Choose([?], 12, 1, group2) (对于 group1 的每个可能选择，因此 ?)。这将为 group2 选择所有剩余的长度为 12 的有序子序列，此时 m 再次 = 0，现在 group = group2。现在，我们可以安全地将 group3 分配给其余条目(在选择 group1 和 group2 后，只有一种方法可以选择 group3)。

我们仅通过传播开始查找递归调用的索引 (minIdx) 来获取有序子序列。我们采用有序子序列以避免获得同一组 12 个项目的排列(因为组内顺序并不重要)。

循环中对 Choose 的每次递归调用都会传递 input 并删除一个元素:正是刚刚添加到所考虑的组中的那个元素。

我们检查 minIndex + m > n + 1 并提前停止递归，因为在这种情况下，我们在输入中跳过了太多项目，无法填满当前组有 12 件商品(同时选择要订购的子序列)。

您会注意到我已将 12/36/3 组的假设硬编码到程序逻辑中。这样做是为了简洁和清晰，而不是因为您无法在输入大小 N 和要形成的组数 k 中对其进行参数化。为此，您需要创建一个组数组(k 个组，每个组的大小为 N/k)，然后使用 N/k 而不是 12 调用 Choose 并使用 select/switch case 语句而不是 if/then/else 来确定是再次选择还是打印。但这些细节可以留作练习。