Функции ввода и рекурсии в python

Question

Это идиотский вопрос.Здесь идет:

У меня есть два списка ,андидатов_вход и ограничений_вход.Приведенная ниже функция находит победившего кандидата в кандидате-входе для заданного порядка ограничений в ограничении-входе путем исключения кандидатов, которые не могут быть победителями, пока не останется только один.Поэтому я удаляю элементы из обоих входных списков - теряю кандидатов и ограничения, которые уже сказали все, что они могут сказать, а затем перехожу к следующему ограничению.

Я не хочу на самом деле изменять исходный вводсписки, потому что они мне понадобятся снова.Но вставка чего-то вроде этого в начале функции:

remaining_candidates = candidates_input[:]
remaining_constraints = constraint_input[:]

И затем замена этих новых имен на старые в функции, кажется, нарушает рекурсию.Что я делаю не так?

def OT_eval(candidates_input, constraint_input): #chooses an optimal candidate given candidates and constraint ranking
    constraint = constraint_input[0]             #highest ranked constraint
    violations_list = [(len(re.findall(constraint, candidate)), candidate) for candidate in candidates_input]
    violations_list.sort()
    """
    Creating list of (num violations, candidate) duples for each candidate, then sorting on num violations
    """
    for pair in violations_list:                 #checking each candidate against  known optimal candidate 
        if pair[0] > violations_list[0][0]:      #num violations > minimal violations
            candidates_input.remove(pair[1])     #removing suboptimal candidate
    if len(candidates_input) > 1 and len(constraint_input) > 0: #if further constraints needed,
        constraint_input.remove(constraint)                     #remove current constraint and recurse
        OT_eval(candidates_input, constraint_input)
    elif len(candidates_input) == 1:
        optimal_candidate = candidates_input[0]
        print "Optimal Candidate:  ", optimal_candidate
        return optimal_candidate
    elif len(candidates_input) > 1 and len(constraint_input) == 0: #more than one candidate left, but no more constraints
        raise ValueError("Optimal candidate cannot be determined: check constraints")

Answer 1

Причина, по которой это «работает» без копирования, заключается в том, что когда вы делаете рекурсивный вызов, вы ничего не возвращаете из него. Каждый рекурсивный вызов повторно фильтрует исходные данные, и как только вы вернулись из всего, исходные данные были полностью повторно отфильтрованы. Если вы делаете копии, то создаются последовательно более отфильтрованные копии, но исходные данные не изменяются, и нет доступа к более отфильтрованным копиям из вызывающей области.

Это исправлено return результатом рекурсивного вызова. В момент, когда вы делаете начальный вызов, вы должны захватить возвращаемое значение (и, возможно, переназначить его исходной переменной). Конечно, чтобы все работало правильно, вам нужно возвращать одно и то же везде, куда вы возвращаете. Поэтому вы должны вернуть кортеж (candid_input, constraint_input), чтобы у вас были эти данные, и позволить сайту вызова интерпретировать результат . Ваш код запутан; ответственность не разделена должным образом. Здесь есть две задачи: фильтрация данных и определение значения отфильтрованных данных.

Когда вы пишете рекурсивный код, вы обычно хотите, чтобы он был в функциональном стиле. Это означает: не изменяйте вещи на месте, а создавайте измененные версии. Для последовательности и аккуратности вы должны делать это даже для подэтапов.

def OT_eval(candidates_input, constraint_input):
    # It's much cleaner to handle base cases for recursion **first**.
    if not (constraint_input and candidates_input):
        # We ran out of one or the other. BTW, your original code doesn't
        # consider the case of an overly constrained situation.
        return (candidates_input, constraint_input)

    constraint = constraint_input[0]
    # At first I was going to replace the call to `.sort()` by using 
    # the free function `sorted` to maintain the "functional" theme. 
    # However, you don't really need to sort the list, as far as I can
    # tell; you just need to find the minimum and use it as a basis for
    # comparison.
    violations = [
        (len(re.findall(constraint, candidate)), candidate)
        for candidate in candidates_input
    ]

    # Now we create "all candidates with more than the minimum violations"
    minimal_violations = min(violations)[0]
    violators = [
        candidate
        for violation_count, candidate in violations
        if violation_count > minimal_violations
    ]
    # And hence "all candidates without that many violations"
    good_candidates = [
        candidate
        for candidate in input_candidates
        if candidate not in violators
    ]     

    # And now we can recurse.
    return OT_eval(good_candidates, constraint_input[1:])

# Then, outside, we do the actual result processing and output:

final_candidates, final_constraints = OT_eval(candidates, constraints)

if final_constraints:
    print "No candidates survived the selection process."
elif len(final_candidates) != 1:
    print "Couldn't determine a winner."
else:
    print "The winner is:", final_candidates[0]

Конечно, теперь, когда тело функции очищено, вы сможете увидеть тривиально, как преобразовать в итерацию. Кроме того, здесь есть ненужное осложнение: поскольку мы определяем количество нарушений для каждого кандидата, нет смысла определять всех нарушителей и отфильтровывать их: мы могли бы просто определить всех хороших кандидатов напрямую через противоположное условие (слева). как упражнение).

Answer 2

Мне кажется, что вы должны зацикливаться на вашем constraint_input вместо рекурсии?