特定のプロパティを持つユニークなタプルのリストを生成するためのアルゴリズム

Question

N個のオブジェクトに一意のタプル（A、B、C）を付けてラベル付けする必要があります。A < B < Cと同じMの最大数はMです。それぞれCs。すべての解の中で、Cの最も低い値を持つものが検索されます。 （この最後の文は意味：2つの解決策の一つは、5の4及びその他の最高のCを持っている場合、最初の1が正しい答えになります。）

例：私が来た

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)] 

プログラムをまでは複雑であれば、他のモンスターです：

import sys 
# useage: labelme.py <N> <M> 
class ObjectListTree(object): 
    """Create many possible paths. 
    Store the parent in each node. 
    The last nodes are appended to the class wide endnodes. 
    """ 
    endnodes = [] 
    def __init__(self, parent, label, counter, n, M, N): 
     self.parent = parent 
     self.M = M 
     self.N = N 
     self.label = label 
     self.counter = counter 
     self.n = n 
     if n < N:  
      self.inc_a() 
      self.inc_b() 
      self.inc_c() 
     else: 
      ObjectListTree.endnodes.append(self) 

    def inc_a(self): 
     if self.label[0]+1 < self.label[1]: 
      if self.counter[1] < self.M: 
       if self.counter[2] < self.M: 
        self.plus_1() 
       else: 
        self.plus_1_3() 
      else: 
       if self.counter[2] < self.M: 
        self.plus_1_2() 
       else: 
        self.plus_all() 
     elif self.label[1]+1 < self.label[2]: 
      if self.counter[2] < self.M: 
       self.plus_1_2() 
      else: 
       self.plus_all() 
     else: 
      self.plus_all() 

    def inc_b(self): 
     if self.counter[0] == self.M: 
      return 
     if self.label[1]+1 < self.label[2] and self.counter[2] < self.M: 
      self.plus_2() 
     else: 
      self.plus_2_3() 

    def inc_c(self): 
     if self.counter[0] == self.M or self.counter[1] == self.M: 
      return 
     else: 
      self.plus_3() 

    def plus_all(self): 
     ObjectListTree(self, (self.label[0]+1, self.label[1]+1, self.label[2]+1), 
         counter = [1, 1, 1,], 
         n = self.n+1, N=self.N, M=self.M) 
    def plus_1_2(self): 
     ObjectListTree(self, (self.label[0]+1, self.label[1]+1, self.label[2]), 
         counter = [1, 1, self.counter[2]+1,], 
         n = self.n+1, N=self.N, M=self.M) 
    def plus_1_3(self): 
     ObjectListTree(self, (self.label[0]+1, self.label[1], self.label[2]+1), 
         counter = [1, self.counter[1]+1, 1,], 
         n = self.n+1, N=self.N, M=self.M) 
    def plus_1(self): 
     ObjectListTree(self, (self.label[0]+1, self.label[1], self.label[2]), 
         counter = [1, self.counter[1]+1, self.counter[2]+1,], 
         n = self.n+1, N=self.N, M=self.M) 
    def plus_2(self): 
     ObjectListTree(self, (self.label[0], self.label[1]+1, self.label[2]), 
         counter = [self.counter[0]+1, 1, self.counter[2]+1,], 
         n = self.n+1, N=self.N, M=self.M) 
    def plus_2_3(self): 
     ObjectListTree(self, (self.label[0], self.label[1]+1, self.label[2]+1), 
         counter = [self.counter[0]+1, 1, 1,], 
         n = self.n+1, N=self.N, M=self.M) 
    def plus_3(self): 
     ObjectListTree(self, (self.label[0], self.label[1], self.label[2]+1), 
         counter = [self.counter[0]+1, self.counter[1]+1, 1,], 
         n = self.n+1, N=self.N, M=self.M) 

tree = ObjectListTree(parent=None, label=(1, 2, 3), counter = [1,1,1,], n=1, N=int(sys.argv[1]), M=int(sys.argv[2])) 

best_path = tree.endnodes[0] 
for n in tree.endnodes: 
    if n.label[2] < best_path.label[2]: 
     best_path = n 
objects = [] 
while best_path: 
    objects.append(best_path.label) 
    best_path = best_path.parent 
objects.reverse() 
print objects 

しかし、私は、これは実際にはセットか何かに包まれitertoolsモジュールからの2つのまたは3の関数の組み合わせのような単純なものでなければならないことな感覚を持っています。誰にでも簡単な解決策が見えますか？

Answer 1

私はこのコードはあなたの要件を満たしていると思っていますし、常に可能な限り最低限の解決策を生成します。

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)