生成schedu的回溯解决方案提示

Question

我试图解决以下问题：

有3个小时的数学，2个物理和3个信息学。我需要生成所有可能的时间表，以便一天至少有1小时的这些科目，最多3个小时（可以是数学、数学、数学或数学物理信息学）

日程安排为5天。 所以我想出了以下解决方案：

设generate（k，o）为第k天的‘generator’函数，其中o小时在1到3之间

每天k和hour选一个仍然在我们左边的主题。我用一个数组counter[i] = TakenCount来跟踪它，其中I是1，2，3对应于数学，物理和信息学，TakenCount是指我用了多少小时的那个科目。在

对于配置，我使用了一个矩阵v[k][o]，它给出了第k天的配置，小时为o

这是我迄今为止尝试过的代码

h = ['', 'm', 'f', 'i']
counter = [0, 0, 0, 0]
limit = [0, 3, 2, 3]
v = [['' for x in range(4)] for x in range(6)]

def generate(k, o):
  if k == 6:
    if counter[1] == limit[1] and counter[2] == limit[2] and counter[3] == limit[3]:
      showConfig()
  else:
    for i in range(1, 4, 1):
      if counter[i] != limit[i]:
        v[k][o] = h[i]
        counter[i] += 1

        generate(k + 1, 1)
        generate(k + 1, 2)
        generate(k + 1, 3)

        v[k][o] = ''
        counter[i] -= 1

def showConfig():
  print '-- Configuration --'
  print counter

  for i in range(1, 6, 1):
    print 'Day ', i,
    success = False

    for j in range(1, 4, 1):
      print v[i][j],

  print '-- End --'

generate(1, 1)
generate(1, 2)
generate(1, 3)

它是用Python编写的，但我认为这不是问题，因为它非常容易阅读

这里的问题是我从来没有在v[i][2]和v[i][3]内呆上几个小时，只有在v[i][1]和这种情况下

^{pr2}$

永远不会实现，我也不知道为什么。在

同样，在我为第二天生成k + 1之后，我需要将当前的v[k][o] to'和{}重置为counter[i] - 1

这不是家庭作业或类似的东西。我问的是这个解决方案是不是很好，如果是，那么我在代码中犯了什么错？因为我好像找不到

输出示例：

( (m), (m, f), (m, f, i), (i), (i) )
...
( (m, i), (f), (i), (m, f, i), (m) )
( (m, f), (i), (i), (m, f, i), (m) )

其中m是数学，f是物理，i是信息学，每个妄想都是一周中的一天，所以一周内有5天

Answer 1

以下是您想要的：

from itertools import permutations
def possible_permutations(*args):
    length_args = len(args)
    args_list, permutations_list = [], []
    for arg in args:
        args_list.append(arg)
        permutations_list.append(tuple(permutations(args_list)))
    # Clean ugly list of touples of touples into a list of touples.
    perms = []
    for perm in permutations_list:
        for p in perm:
            perms.append(p)
    return perms

def schedules(days, *classes):
    possible_perms = possible_permutations(*classes)
    for perm in permutations(possible_perms, days):
        print(perm)
schedules(5, 'math', 'science', 'english')

---

旧答案

我不太清楚你问什么，但我相信这能解决你的问题。在

^{pr2}$

输出：

(('physics', 2), ('math', 3), ('informatics', 3))
(('physics', 2), ('informatics', 3), ('math', 3))
(('math', 3), ('physics', 2), ('informatics', 3))
(('math', 3), ('informatics', 3), ('physics', 2))
(('informatics', 3), ('physics', 2), ('math', 3))
(('informatics', 3), ('math', 3), ('physics', 2))