用于检查字符串形式矩阵的回溯算法

Question

我有清单：

words = ["ALI", "SIN", "ASI", "LIR", "IRI", "INI", "KAR"]

我想检查它们是否形成如下矩阵：

并将我的解决方案作为列表返回：

solution = ["ALI", "SIN", "IRI"]

我想出了这段代码：

words=["ALI", "SIN", "ASI", "LIR", "IRI", "INI", "KAR"]
solution =[]
failedsolutions = []

def Get_next_word():

    while True:
        for word in words:
            if (word in solution) == False:
                solution.append(word)
                if (solution in failedsolutions) == False:
                    return False
                else:
                    solution.pop(len(solution) - 1 )
        return True

def Check_word_order():
    checker = True
    for i in range(len(solution)):
        for j in range(len(words[0])):
            for word in words:
                if solution[i][j] == word[j]:
                    checker = False
                else:
                    checker = True
            if checker == False:
                return checker

def main():
    while True:
        Get_next_word()


        check = Check_word_order()

        if check is False:
            #Backtrack
            failedsolutions.append(solution)
            solution.pop(len(solution) - 1 )

    #    else:
    #        solution.append()

    print(solution)

main()

我累了，不再能够调试我的代码了。帮助将不胜感激。谢谢ps：如果有更好的方法，我建议不要修复我的代码。

Answer 1

您可以使用这个简单的递归函数来分析所有可能的组：

import itertools
import copy
words = ["ALI", "SIN", "ASI", "LIR", "IRI", "INI", "KAR"]
def get_pairs(word_group, current_words, found):
   if not current_words:
     return found
   new_group = list(word_group)+[current_words[0]]
   if all(''.join(i) in words and ''.join(i) not in new_group for i in zip(*new_group)):
      return get_pairs(word_group, current_words[1:], new_group)
   return get_pairs(word_group, current_words[1:], found)


starting_pairs = [i for i in itertools.combinations(words, 2)]
final_listing = filter(lambda x:x, [get_pairs(i, copy.deepcopy(words), []) for i in starting_pairs])

输出：

[['ALI', 'SIN', 'IRI'], ['ASI', 'LIR', 'INI']]

这产生了有效矩阵的所有组合。

或者，不使用itertools：

def get_combos(word, new_words):
   if new_words[1:]:
     new_list = [(yield (word, i)) for i in new_words if i != word]
     for b in get_combos(new_words[0], new_words[1:]):
        yield b

starting_pairs = get_combos(words[0], words[1:])
final_listing = filter(lambda x:x, [get_pairs(i, copy.deepcopy(words), []) for i in starting_pairs])