生成从整数118中选择的3组6个数字的所有可能集合

Question

因为6的组代表骰子，所以这些组中整数的顺序无关紧要。每个集合中的组的顺序确实很重要，但要检查每个集合，很容易找到每个集合的排列，我可以这样做

现在，我想出了一个方法来实现这一切，问题是效率。我想检查每一套，但到目前为止，我只想到了一种方法，使用：

for i in itertools.combinations(num, 6):
    W.append([i])
print(W)
print("Done building list of ",len(W)," possible dice.")

这给了我所有可能的6个数字的骰子，从18个整数中选择，其中数字的顺序无关紧要。这是18564组，共6组。然后，我使用以下方法找到这些骰子的组合：

for j in itertools.combinations(W, 3):
    check = list(itertools.chain(*list(itertools.chain(*j))))
    check = sorted(check)
#print(check)
if check == num:
   

问题产生于这样一个事实，即第二个组合将迭代10^15种可能性，其中只有一小部分是我想要生成的

我还有一个问题：

我很确定，将18件事情分配给3个不同的组（每组6件），其中组内的顺序无关紧要的方法是：18/（6！）^3~1700万种方法，可以相对快速地迭代。是这样吗？有没有一种方法可以迭代地生成这些方法，而无需过滤更大的可能性集

最后一点注意：

我正在做的是尝试生成所有非传递的六面骰子集，其中每个骰子的每个面都有一个不同的数字。我已经有了代码，可以检查一个集合，决定它是否符合这个条件，并存储最佳结果，即一个骰子击败队伍中下一个骰子的最高概率

 for k in itertools.permutations(j):
        B = k[0]
        G = k[1]
        R = k[2]

        b = 0
        g = 0
        r = 0

        for m in B:
            for n in G:
                if m > n:
                    b = b + 1
                else:
                    continue
        for m in G:
            for n in R:
                if m > n:
                    g = g + 1
                else:
                    continue
        for m in R:
            for n in B:
                if m > n:
                    r = r + 1
                else:
                    continue

        w = w + 1
        print(w)
        if b <= 18 or g <= 18 or r <= 18:
            continue
        else:
            if b >= blue and g >= green  and r >= red:
                Blue = B
                blue = b

                Green = G
                green = g

                Red = R
                red = r

                print(B)
                print(b/36)
                print(G)
                print(g/36)
                print(R)
                print(r/36)
                continue
            else:
                continue
else:
    continue

Answer 1

如评论中所述，OP似乎正在寻找Partitions of Groups of Equal Size

下面的代码是从C++中实现的算法转换而来的，在这里可以找到：https://github.com/jwood000/RcppAlgos/blob/master/src/ComboGroupsUtils.cpp^*。我将注释放在下面自己的一个块中，然后是pythonized代码（注意，这是一个直接翻译，可能还有改进的余地）

******* Overview of the Crucial Part of the Algorithm *******

---

last1 is one plus the upper bound in the previous section, so to obtain the current current upper bound, we must first add the size of a section (i.e. grpSize) and subtract one. We can now compute the length we need to reset v by subtracting idx1. E.g.

Given a portion of v with grpSize = 4, idx1 = 9, 6 groups (24 subjects) and base 0:

         prev sections   bound (index = 8)
             /  \        |
       ............. 8 | 9 12 23 24 | 10 20 21 22 | 11 ... 
                            |
                          idx1 (equal to last1, in this case)

Sort v past idx1:

                 ... 8 | 9 12 10 11 | 13 14 15 16 | 17... 

Determine the index, idx3, such that v[idx3] > v[idx1]

                 ... 8 | 9 12 10 11 | 13 14 15 16 | 17 ... 
                            |          |
                          idx1       idx3

Swap idx1 and idx3:

                 ... 8 | 9 13 10 11 | 12 14 15 16 | 17... 

Move enough indices after idx1 to fill that specific group:

                 ... 8 | 9 13 __ __ | 10 11 12 14 | 15 16 ... 

Identify and move indices that are successively incrementing values of v past idx1:

                 ... 8 | 9 13 14 15 | 10 11 12 16 | 17 ... 

The last two steps are accomplished with std::rotate. This completes the algorithm.

以下是一些帮助功能：

def rotate(l, n):
    return l[n:] + l[:n]

def numGroupCombs(n, nGrps, grpSize):
    result = 1

    for i in range(n, nGrps, -1):
        result *= i

    result = int(result)
    myDiv = 1

    for i in range(2, grpSize + 1):
        myDiv *= i

    result /= myDiv**nGrps
    return int(result)

这是主生成器（旋转函数是从这个答案Python list rotation得到的）：

def ComboGroups(v, nGrps, grpSize):

    if not isinstance(v, list):
        z = list(v)
    else:
        z = v.copy()

    for i in range(numGroupCombs(len(z), nGrps, grpSize)):
        yield z.copy()

        idx1 = (nGrps - 1) * grpSize - 1
        idx2 = len(z) - 1;
        last1 = (nGrps - 2) * grpSize + 1

        while (idx2 > idx1 and z[idx2] > z[idx1]):
            idx2 -= 1

        if (idx2 + 1) < len(z):
            if z[idx2 + 1] > z[idx1]:
                z[idx1], z[idx2 + 1] = z[idx2 + 1], z[idx1]
        else:
            while idx1 > 0:
                tipPnt = z[idx2]

                while (idx1 > last1 and tipPnt < z[idx1]):
                    idx1 -= 1

                if tipPnt > z[idx1]:
                    idx3 = idx1 + 1
                    z[idx3:] = sorted(z[idx3:])
                    xtr = last1 + grpSize - idx3

                    while z[idx3] < z[idx1]:
                        idx3 += 1

                    z[idx3], z[idx1] = z[idx1], z[idx3]
                    z[(idx1 + 1):(idx3 + xtr)] = rotate(z[(idx1 + 1):(idx3 + xtr)], idx3 - idx1)
                    break
                else:
                    idx1 -= 2
                    idx2 -= grpSize
                    last1 -= grpSize

下面是一个示例用法（https://ideone.com/kygF03）：

import time

def example(z, nGrps, verbose = True):
    grpSize = int(len(z) / nGrps)

    if verbose:
        for a in ComboGroups(z, nGrps, grpSize):
            print([a[i:i + grpSize] for i in range(0, len(a), grpSize)])
    else:
        start = time.time()

        for a in ComboGroups(z, nGrps, grpSize):
            b = a

        end = time.time()
        print(end - start)

example(list(range(1, 9)), 2)
[[1, 2, 3, 4], [5, 6, 7, 8]]
[[1, 2, 3, 5], [4, 6, 7, 8]]
[[1, 2, 3, 6], [4, 5, 7, 8]]
[[1, 2, 3, 7], [4, 5, 6, 8]]
[[1, 2, 3, 8], [4, 5, 6, 7]]
[[1, 2, 4, 5], [3, 6, 7, 8]]
[[1, 2, 4, 6], [3, 5, 7, 8]]
[[1, 2, 4, 7], [3, 5, 6, 8]]
[[1, 2, 4, 8], [3, 5, 6, 7]]
[[1, 2, 5, 6], [3, 4, 7, 8]]
[[1, 2, 5, 7], [3, 4, 6, 8]]
[[1, 2, 5, 8], [3, 4, 6, 7]]
[[1, 2, 6, 7], [3, 4, 5, 8]]
[[1, 2, 6, 8], [3, 4, 5, 7]]
[[1, 2, 7, 8], [3, 4, 5, 6]]
[[1, 3, 4, 5], [2, 6, 7, 8]]
[[1, 3, 4, 6], [2, 5, 7, 8]]
[[1, 3, 4, 7], [2, 5, 6, 8]]
[[1, 3, 4, 8], [2, 5, 6, 7]]
[[1, 3, 5, 6], [2, 4, 7, 8]]
[[1, 3, 5, 7], [2, 4, 6, 8]]
[[1, 3, 5, 8], [2, 4, 6, 7]]
[[1, 3, 6, 7], [2, 4, 5, 8]]
[[1, 3, 6, 8], [2, 4, 5, 7]]
[[1, 3, 7, 8], [2, 4, 5, 6]]
[[1, 4, 5, 6], [2, 3, 7, 8]]
[[1, 4, 5, 7], [2, 3, 6, 8]]
[[1, 4, 5, 8], [2, 3, 6, 7]]
[[1, 4, 6, 7], [2, 3, 5, 8]]
[[1, 4, 6, 8], [2, 3, 5, 7]]
[[1, 4, 7, 8], [2, 3, 5, 6]]
[[1, 5, 6, 7], [2, 3, 4, 8]]
[[1, 5, 6, 8], [2, 3, 4, 7]]
[[1, 5, 7, 8], [2, 3, 4, 6]]
[[1, 6, 7, 8], [2, 3, 4, 5]]

对于您的示例，上面未优化的实现可以在4秒钟内迭代所有2,858,856结果

example(list(range(1, 19)), 3, False)
4.4308202266693115

作为参考，相同的算法在C++中运行大约0.12秒

^*我是RcppAlgos的作者

Answer 2

首先，从18件事物中选择6件事物的所有组合。这是你的第一个骰子。有18564种可能性

然后，从剩下的12件（924件）中选择6件的所有组合，类似地。这将给你第二个骰子，给你第一个

最后，第三个骰子就是所有剩余的数字。这是18564x924x1=17153136

但事实上，等等。我们也不在乎三个骰子的顺序。所以我们可以假设“1”在第一个骰子上。然后不是第一个模具上的最小数字是第二个模具上的。这就是6188x462x1=2858856的可能性

下面是一些python代码。它不像你自己做的那样快，但它应该运行良好

如果您在真正的可传递骰子上运行此操作，请尝试删除“唯一”约束！我很好奇是否有有趣的重复骰子

import itertools
def iter_dice():
    nums = list(range(1,19))
    for first_die in itertools.combinations(nums[1:], 5):
        first_die = (1,) + first_die
        remaining = sorted(set(nums) - set(first_die))
        for second_die in itertools.combinations(remaining[1:], 5):
            second_die = (remaining[0],) + second_die
            third_die = sorted(set(remaining) - set(second_die))
            yield first_die, second_die, third_die
print(len(list(iter_dice())))
print(next(iter_dice()))