특정 속성을 가진 고유 튜플의 목록을 생성하는 알고리즘

Question

N 개의 객체에 고유 한 튜플 (A, B, C)로 라벨을 지정해야합니다. 여기서 A < B < C와 동일한 A의 최대 개수는 M입니다. Bs 및 Cs 각각. 모든 솔루션 중에서 가장 낮은 C 값을 가진 솔루션이 검색됩니다. (이 마지막 문장의 의미 : 두 가지 솔루션 중 하나가 4의 가장 높은 C 5의 기타가있는 경우, 그 첫 번째가 정답이다.)

예 :

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 모듈에서 두 개 또는 세 개의 기능의 조합 같은 간단한 뭔가해야한다는 느낌이 듭니다. 누구든지 간단한 해결책을 볼 수 있습니까?

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)