バックトラックアルゴリズムは、私がリストを持っている文字列のフォームマトリックス

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