バックトラックは、私は問題を解決しようとしていたすべての可能性

Question

て行くことはありません。

私は質問の名前といくつかのポイントを持っている辞書を持っています。たとえばQs = {"question1": 13, "question2": 1}については

、それはquestion1が13ポイントを持っていること、もう一つは1を持っているなど

私はuとv質問とxとy点の間の問題のすべてのサブセットを作成しようとしていました。ここで

は私のコードです：

class GrowingList(list): 
    def __setitem__(self, index, value): 
     if index >= len(self): 
      self.extend([None]*(index + 1 - len(self))) 
     list.__setitem__(self, index, value) 


questions = {"Q1":5, "Q2":1, "Q3": 1, "Q4": 4} 
u = 1 # 
v = 3 # between u and v questions 


x = 1 # 
y = 7 #between x and y points 


solution = GrowingList() 

def main(): 

    Backtracking(0) 



def Backtracking(k): 
     for c in questions.keys(): 
       solution[k] = c 
       # print ("candidate: ", solution) 
       if not reject(k): 
       # print ("not rejected: ", solution) 
        if accept(k): 
           print (solution) 
           if (k == v-1): 
            return ; 
           else: 
            Backtracking(k+1) 
def reject(k): 
    if len(solution) != len(set(solution)): #check whether the question already exists 
     return True 

    points = 0 
    for q in solution: 
     if q in questions: 
      points = points + questions[q] 

    if points >y or k+1 > v: #check if the candidate solution has between the given number of questions and points 
      return True 
    return False 

def accept(k): 
    if len(solution) != len(set(solution)): #check whether the question already exists 
     return False 

    points = 0 
    for q in solution: 
     if q in questions: 
      points = points + questions[q] 
    if x <= points <= y and u <= k+1 <= v: #if the candidate solution has between the given number of points and questions, we found a solution 
      return True 
    return False 

main() 

u = 1のためにそう

、= 3 v、x = 1とy = 7私だけ

['Q1'] 
['Q1', 'Q2'] 
['Q1', 'Q2', 'Q3'] 
['Q2', 'Q4', 'Q3'] 
['Q2', 'Q1', 'Q3'] 
['Q2', 'Q1', 'Q3'] 
['Q2', 'Q4', 'Q3'] 

取得しています。しかし、私は多くのことを欠場します1つの要素の質問のサブセットの残りの部分など、解の

['Q2'] 
['Q3'] 
['Q4'] 

も解決策に含める必要があります。

Answer 1

これは、あなたが望むことをしますが、重要だった場合にはバックトラックを使用しません。必要に応じて、イテレータをリストにするのではなく、イテレータsubsets(qs_between, min_set_size, max_set_size)を使用するだけです。

from itertools import chain, combinations 

qs = {"Q1":5, "Q2":1, "Q3": 1, "Q4": 4} 

min_set_size = 2 
max_set_size = 3 

min_score = 1 
max_score = 4 

qs_between = [question for question, score in qs.items() if min_score <= score <= max_score] 

def subsets(iterable, min_set_size, max_set_size): 
    return chain.from_iterable(combinations(iterable, size) 
     for size in range(min_set_size, max_set_size + 1)) 

result = list(subsets(qs_between, min_set_size, max_set_size)) 

print(result) 

Answer 2

簡単なアプローチ

import itertools 
from pprint import pprint 

u, v = 1, 3 

x, y = 1, 7 

Q = ['Q' + str(g) for g in range(u, v + 1)] 
points = range(x, y + 1) 

n = v - u + 1 

result = [] 

for i in range(1, n + 1): 
    for c in itertools.combinations(Q, i): 
     result += [dict(zip(c, x)) for x in itertools.product(points, repeat=i)] 

# print result 
pprint(result) 

いくつかの出力Powersetの上でループ

{'Q1': 7, 'Q3': 7, 'Q2': 5} 
{'Q2': 1} 
{'Q1': 7, 'Q3': 1, 'Q2': 6} 
{'Q1': 3, 'Q3': 3} 
{'Q1': 7}  
{'Q1': 3, 'Q3': 4} 

も同様に動作します。 powersetの要素cの場合、repeatパラメータにはlen(c)が必要です。