我试图实现贪婪算法，我需要找到具有最独特字母的字母生成器，处理这些字母，然后找到下一个最好的生成器，直到我处理完所有字母。然而，当我运行函数 get_next_best_generator 第一次它返回了正确的值，但在下一次调用中没有返回任何东西，并出现以下错误-。0
[]
KeyError: ''一呼百应generator_2
6
['p', 'q', 'k', 'j', 'l', 'm', 'n', 't']
为什么在第一次调用后，它没有返回任何东西？
以下是我的代码
# create lists to store covered alphabets and processed generators
alphabets_covered=[]
generator_covered=[]
# create a dict to store generators and the alphabets that they generate
generator_alphabets_dict={'generator_1':['p','q','r'], 'generator_2':['p', 'q','k','j','l','m','n','t'],
'generator_3':['x','m'], 'generator_4':['p','e','m','g']}
def get_next_best_generator():
'''get the generator that generates the most unique alphabets that have not been covered'''
most_alphabets_count=0
best_generator_alphabets=[]
best_generator=''
#Loop through the dict to find the generator with most unique alphabets
for generator ,alphabets in generator_alphabets_dict.items():
unique_alphabets_list = []
generator_alphabets = list(alphabets)
# Loop to store the unique alphabets for a generator
for selected_alphabet in generator_alphabets:
if selected_alphabet not in alphabets_covered:
unique_alphabets_list.append(selected_alphabet)
alphabets_covered.append(selected_alphabet)
# update all values if current generator's unique element list is greater than its predecessor's
if len(unique_alphabets_list) > most_alphabets_count:
most_alphabets_count = len(unique_alphabets_list)
best_generator_alphabets = alphabets
best_generator = generator
return most_alphabets_count, best_generator_alphabets , best_generator
# Loop until all alphabets have been covered
while len(alphabets_covered) < 13:
most_alphabets_count, best_generator_alphabets, best_generator = get_next_best_generator()
print(best_generator)
print(most_alphabets_count)
print(best_generator_alphabets)
generator_alphabets_dict.pop(best_generator)
generator_covered.append(best_generator)
在做了一些修改之后--我的函数仍然不能返回具有最独特元素的键。
更新后的代码
# create lists to store covered alphabets and processed generators
generator_covered=[]
# create a dict to store generators and the alphabets that they generate
generator_alphabets_dict={'generator_1':['p','q','r'], 'generator_2':['p', 'q','k','j','l','m','n','t'],
'generator_3':['x','w','b'], 'generator_4':['p','e','m','g']}
alphabets = set(['p','q','r','k','j','l','m','n','t','x','w','b','e','g'])
def get_next_best_generator():
'''get the generator that generates the most unique alphabets that have not been covered'''
most_alphabets_count=0
best_generator_alphabets=[]
best_generator=''
#Loop through the dict to find the generator with most unique alphabets
for generator ,alphabets in generator_alphabets_dict.items():
unique_alphabets_list = []
generator_alphabets = list(alphabets)
for selected_alphabet in generator_alphabets :
if selected_alphabet in alphabets:
unique_alphabets_list.append(selected_alphabet)
# update all values if current generator's unique element list is greater than its predecessor's
if len(unique_alphabets_list) > most_alphabets_count:
most_alphabets_count = len(unique_alphabets_list)
best_generator_alphabets = unique_alphabets_list
best_generator = generator
return most_alphabets_count, best_generator_alphabets , best_generator
# Loop until all alphabets have been covered
while alphabets:
most_alphabets_count, best_generator_unique_alphabets, best_generator = get_next_best_generator()
print(best_generator)
print(most_alphabets_count)
print(best_generator_unique_alphabets)
generator_alphabets_dict.pop(best_generator)
generator_covered.append(best_generator)
alphabets -= set(best_generator_unique_alphabets)
预期输出-generator_28['p', 'q', 'k', 'j', 'l', 'm', 'n', 't']generator_33['x', 'w', 'b']generator_42['e', 'g']generator_11['r']
首先，如果你的脚本崩溃了，请附上完整的堆栈跟踪。
你的问题是由于你的if-statement if len(unique_alphabets_list) > most_alphabets_count 永远不会在你的第二次函数传递中为True。
原因是，在这个for-loop里面。
for selected_alphabet in generator_alphabets:
if selected_alphabet not in alphabets_covered:
unique_alphabets_list.append(selected_alphabet)
alphabets_covered.append(selected_alphabet)
在这里你写到 alphabets_covered 在你运行了一次函数之后，它将包含所有的唯一字母，所以第二次绕过if-statement将永远不会为True。如果你通过在函数内部定义变量来改变它的范围，你仍然可以对唯一值进行计数。
最后，因为你不能再使用 alphabets_covered 作为你的 while-statement 限制器，将其改为只检查 generator_alphabets_dict 里面是否有任何值。
这是更新后的代码。
# create lists to store covered alphabets and processed generators
generator_covered = []
# create a dict to store generators and the alphabets that they generate
generator_alphabets_dict = {'generator_1': ['p', 'q', 'r'], 'generator_2': ['p', 'q', 'k', 'j', 'l', 'm', 'n', 't'],
'generator_3': ['x', 'm'], 'generator_4': ['p', 'e', 'm', 'g']}
def get_next_best_generator():
'''get the generator that generates the most unique alphabets that have not been covered'''
most_alphabets_count = 0
best_generator_alphabets = []
best_generator = ''
alphabets_covered = [] # Moved into the function.
#Loop through the dict to find the generator with most unique alphabets
for generator, alphabets in generator_alphabets_dict.items():
unique_alphabets_list = []
generator_alphabets = list(alphabets)
# Loop to store the unique alphabets for a generator
for selected_alphabet in generator_alphabets:
if selected_alphabet not in alphabets_covered:
unique_alphabets_list.append(selected_alphabet)
alphabets_covered.append(selected_alphabet)
# update all values if current generator's unique element list is greater than its predecessor's
if len(unique_alphabets_list) > most_alphabets_count:
most_alphabets_count = len(unique_alphabets_list)
best_generator_alphabets = alphabets
best_generator = generator
return most_alphabets_count, best_generator_alphabets, best_generator
# Loop until all alphabets have been covered
# the boolean value of an empty dictionary is False, so we can limit it on that.
while generator_alphabets_dict:
most_alphabets_count, best_generator_alphabets, best_generator = get_next_best_generator()
print(best_generator)
print(most_alphabets_count)
print(best_generator_alphabets)
generator_alphabets_dict.pop(best_generator)
generator_covered.append(best_generator)
我没有在你的函数中添加任何逻辑， 看一下它的输出，然后我们可以看到： generators 按以下顺序输出。
generator_2
generator_1
generator_4
generator_3
但是，这并不是我想要的顺序，因为... ... generator_4 字数多于 generator_1 因此在我看来应该更 "独特"。
考虑到这一点，我简化了您的代码，以返回我认为更 "独特 "的顺序。
def get_ordered_unique_generator(values: dict) -> list:
return sorted(values, key=lambda x: len(set(values[x])), reverse=True)
for k in get_ordered_unique_generator(generator_alphabets_dict):
print(f"Key: {k}, Value: {generator_alphabets_dict[k]}")
输出
Key: generator_2, Value: ['p', 'q', 'k', 'j', 'l', 'm', 'n', 't']
Key: generator_4, Value: ['p', 'e', 'm', 'g']
Key: generator_1, Value: ['p', 'q', 'r']
Key: generator_3, Value: ['x', 'm']
你的大部分错误似乎都是由于局部变量和全局变量范围的混淆造成的。例如，在你的函数中 get_next_best_generator() 你已经定义了变量 best_generator 作为一个值为''的字符串。然后你可以尝试使用操作来给这个字符串重新分配一个新的值 best_generator = generator. 这正在抛出一个错误，所以这需要全局性的，或者你需要重新考虑你返回数据的格式。例如，你可以将变量 most_alphabets_count, best_generator_alphabets 和 best_generator 在一个列表中。然后在返回的时候遍历它们，并在最后一次检查时将它们的值赋值。
# create lists to store covered alphabets and processed generators
alphabets_covered=[]
generator_covered=[]
# create a dict to store generators and the alphabets that they generate
generator_alphabets_dict={
'generator_1':['p','q','r'],
'generator_2':['p','q','k','j','l','m','n','t'],
'generator_3':['x','m'],
'generator_4':['p','e','m','g']
}
def get_next_best_generator():
'''get the generator that generates the most unique alphabets that have not been covered'''
most_alphabets_count=0
best_generator_alphabets=[]
value_list = []
print(generator_alphabets_dict)
#Loop through the dict to find the generator with most unique alphabets
for generator ,alphabets in generator_alphabets_dict.items():
unique_alphabets_list = []
for select_alphabet in alphabets:
if select_alphabet not in alphabets_covered:
unique_alphabets_list.append(select_alphabet)
alphabets_covered.append(select_alphabet)
# update all values if current generator's unique element list is greater than its predecessor's
if len(unique_alphabets_list) > most_alphabets_count:
value_list.append(len(unique_alphabets_list))
value_list.append(alphabets)
value_list.append(generator)
return value_list
# Loop until all alphabets have been covered
def mainloop():
counter = 0
while len(alphabets_covered) < 13 and len(generator_alphabets_dict.keys()) > 0 and counter < 10:
counter += 1
print(f'Loop counter: {counter}')
try:
my_values = get_next_best_generator()
most_alphabets_count = my_values[0]
best_generator_alphabets = my_values[1]
best_generator = my_values[2]
except Exception as e:
print(f'Error in assigning variables values to most_alphabets_count, best_generator_alphabets, best_generator: {e}')
print(f'best_generator: {best_generator}')
print(f'most_alphabets_count: {most_alphabets_count}')
print(f'best_generator_alphabets: {best_generator_alphabets}')
try:
if best_generator in generator_alphabets_dict.keys():
generator_alphabets_dict.pop((best_generator))
generator_covered.append(best_generator)
else:
print(f'key not found in dict')
except Exception as e:
print(f"ERROR: {e}\n")
else:
print('process complete with no errors\n')
finally:
print('process complete')
def print_dict(my_dict):
for k, v in my_dict.items:
print(f'Current values in dict:\n')
print(f'key:{k}')
print(f'value:{v}')
if __name__ == '__main__':
mainloop()
我不确定这是否能解决贪婪算法的问题， 但它确实有助于了解错误的来源和需要修正的地方。我在while循环上放了一个计数器，以阻止机器在无限循环中超时。
# create lists to store covered alphabets and processed generators
generator_covered=[]
# create a dict to store generators and the alphabets that they generate
generator_alphabets_dict={'generator_1':['p','q','r'], 'generator_2':['p', 'q','k','j','l','m','n','t'],
'generator_3':['x','w','b'], 'generator_4':['p','e','m','g']}
alphabets_set = set(['p','q','r','k','j','l','m','n','t','x','w','b','e','g'])
def get_next_best_generator():
'''get the generator that generates the most unique alphabets that have not been covered'''
most_alphabets_count=0
best_generator_alphabets=[]
best_generator=''
#Loop through the dict to find the generator with most unique alphabets
for generator ,alphabets in generator_alphabets_dict.items():
unique_alphabets_list = []
generator_alphabets = list(alphabets)
for selected_alphabet in generator_alphabets :
if selected_alphabet in alphabets_set:
unique_alphabets_list.append(selected_alphabet)
# update all values if current generator's unique element list is greater than its predecessor's
if len(unique_alphabets_list) > most_alphabets_count:
most_alphabets_count = len(unique_alphabets_list)
best_generator_alphabets = unique_alphabets_list
best_generator = generator
return most_alphabets_count, best_generator_alphabets , best_generator
# Loop until all alphabets have been covered
while alphabets_set:
most_alphabets_count, best_generator_unique_alphabets, best_generator = get_next_best_generator()
print(best_generator)
print(most_alphabets_count)
print(best_generator_unique_alphabets)
generator_alphabets_dict.pop(best_generator)
generator_covered.append(best_generator)
alphabets_set -= set(best_generator_unique_alphabets)
我使用了一个字母集，它被下一个最佳生成器中找到的唯一元素减去，并在字母集中有元素时循环。