python - Coding theory - Algorithm

Question

Here's the question and my attempt at solving it, but after debugging I realized that my while loop is not functioning as needed. Any help would be greatly appreciated.

Question: Given an alphabet q, create a list of combinations (with replacement) of size n from the alphabet. If there are at least M elements in the list of combinations, where each elements differs from the rest by d list items, return True.

import itertools as it
import numpy as np

def nmdcode(q, n, M, d):
    combinations = list(it.product(q, repeat=n))
    final_list = []
    
    i = 0
    n = 0
    
    final_list.append(combinations[0])
    checker = []
    result = False
    
    while i < (len(combinations) - 1):
        checker = combinations[i + 1]
        for element in final_list:
            diff = sum(map(lambda x,y: bool(x-y),checker, element))
            if (diff == d):
                final_list.append(checker)
                print(final_list)
        
        i += 1
    
    if (len(checker) >= M):
        result = True
        
    return result
    
print(nmdcode([1,2,5], 10, 200, 3))

标签： pythonalgorithmtheory

Answer 1

这是修改后的代码

import itertools as it
import numpy as np

def nmdcode(q, n, M, d):
    combinations = list(it.product(q, repeat=n))
    final_list = []
    
    i = 0
    n = 0
    
    # final_list.append(combinations[0])
    checker = []
    result = False
    
    
    #while i < (len(combinations) - 1):
    for checker in combinations:
        #checker = combinations[i + 1]
        for element in final_list:
            diff = sum(map(lambda x,y: bool(x-y),checker, element))
            #if (diff == d):
            if diff != d:
                break
        else:
            final_list.append(checker)
            print(final_list)
        
        #i += 1
    
    if (len(checker) >= M):
        result = True
        
    return result
    
print(nmdcode([1,2,5], 10, 200, 3))

从一个空的final_list.

循环检查组合是否final_list失败。

如果失败break，则循环跳过该else块。

如果条件不失败，else则执行块，将元素附加到final_list.

开头final_list是空的，所以循环直接进入块并附加toelse的第一个元素。combinationsfinal_list