具有特定属性的唯一元组列表生成算法

Question

我需要用唯一的元组（A，B，C）来标记N个对象，其中A<；B<；C和最大数目的As是M。Bs和Cs都是相同的。在所有的解中，寻找C值最低的一个。（最后一句话的意思是：如果两个解中有一个的C值最高，为4，另一个为5，则第一个解的C值为正确答案。）

示例：

M = 1
N = 4
#          As Bs Cs
objects = [(1, 2, 3), 
           (2, 3, 4), 
           (3, 4, 5), 
           (4, 5, 6)]
M = 2
N = 4
objects = [(1, 2, 3),
           (1, 2, 4),
           (2, 3, 4),
           (2, 3, 5)]
# or e.g
objects = [(1, 2, 3), 
           (2, 3, 4), 
           (2, 4, 5), 
           (3, 4, 5)]

M = 3
N = 8
objects = [(1, 2, 3), 
           (2, 3, 4), 
           (2, 3, 5), 
           (2, 4, 5), 
           (3, 4, 5), 
           (3, 4, 6), 
           (3, 5, 6), 
           (4, 5, 6)]

我想出的程序是一个复杂的“如果不是”怪物：

^{pr2}$

但我觉得这实际上应该是一些简单的东西，比如将itertools模块中的两个或三个函数组合在一个集合或其他东西中。有人能找到一个简单的解决方案吗？在

Answer 1

我认为这段代码符合您的要求，并且总是用尽可能低的C生成解决方案。但是，并不完全使用itertools。在

def generateTuples(N, M):
  done = 0
  counters = {}
  for C in range(3, N + 3):
    for B in range(2, C):
      for A in range(1, B):
        if (counters.get('A%i' % A, 0) < M and
            counters.get('B%i' % B, 0) < M and
            counters.get('C%i' % C, 0) < M):
          yield (A, B, C)
          counters['A%i' % A] = counters.get('A%i' % A, 0) + 1
          counters['B%i' % B] = counters.get('B%i' % B, 0) + 1
          counters['C%i' % C] = counters.get('C%i' % C, 0) + 1
          done += 1
          if done >= N:
            return

for (A, B, C) in generateTuples(8, 3):
  print (A, B, C)