Головоломка KenKen добавляет:REDUX A (исправленный) нерекурсивный алгоритм

StackOverflow https://stackoverflow.com/questions/1061590

Вопрос

Этот вопрос относится к тем частям головоломок KenKen Latin Square, в которых вас просят найти все возможные комбинации чисел ncells со значениями x такие, что 1 <= x <= maxval и x(1) + ...+ x(cells) = targetsum.Протестировав несколько наиболее многообещающих ответов, я собираюсь вручить приз за ответ Леннарту Регебро, потому что:

  1. его программа такая же быстрая, как и моя (+-5%), и

  2. он указал, что где-то в моей исходной программе была ошибка, что позволило мне понять, что она на самом деле пытается сделать.Спасибо, Леннарт.

Криспи представил алгоритм, который кажется эквивалентным алгоритму Леннарта, но через 5 часов, ооочень, первым он доходит до провода.

Замечание:Простейший рекурсивный алгоритм Алекса Мартелли представляет собой пример создания всех возможных комбинаций, бросания их всех в сито и наблюдения за тем, какие из них проходят через отверстия.Этот подход занимает в 20+ раз больше времени, чем у Леннарта или у меня.(Увеличьте входные данные до max_val = 100, n_cells = 5, target_sum = 250, и на моем компьютере это 18 секунд против 18 секунд.8+ мин.) Мораль:Не генерировать все возможные комбинации — это хорошо.

Еще одно замечание:Мы с Леннартом подпрограммы генерируем те же ответы в том же порядке.Действительно ли это один и тот же алгоритм, рассматриваемый под разными углами?Я не знаю.

Мне что-то приходит в голову.Если вы отсортируете ответы, начиная, скажем, с (8,8,2,1,1) и заканчивая (4,4,4,4,4) (то, что вы получите с max_val=8, n_cells=5, target_sum =20) серия образует своего рода «медленнейший спуск», причем первые «горячие», а последние «холодные» и максимально возможное число ступеней между ними.Связано ли это с «информационной энтропией»?Какова правильная метрика для рассмотрения?Существует ли алгоритм, который создает комбинации в порядке убывания (или возрастания) тепла?(Насколько я вижу, этого нет, хотя на коротких отрезках времени он близок к нормализованному стандартному значению.разработчик)

Вот процедура Python:

#!/usr/bin/env python
#filename: makeAddCombos.07.py -- stripped for StackOverflow

def initialize_combo( max_val, n_cells, target_sum):
    """returns combo
    Starting from left, fills combo to max_val or an intermediate value from 1 up.  
    E.g.:  Given max_val = 5, n_cells=4, target_sum = 11, creates [5,4,1,1].
    """
    combo = []
    #Put 1 in each cell.
    combo += [1] * n_cells
    need = target_sum - sum(combo)
    #Fill as many cells as possible to max_val.
    n_full_cells = need //(max_val - 1)
    top_up = max_val - 1
    for i in range( n_full_cells): combo[i] += top_up
    need = target_sum - sum(combo)
    # Then add the rest to next item.
    if need > 0:
        combo[n_full_cells] += need
    return combo
#def initialize_combo()

def scrunch_left( combo):
    """returns (new_combo,done)
    done   Boolean; if True, ignore new_combo, all done;
            if Falso, new_combo is valid.

    Starts a new combo list.  Scanning from right to left, looks for first
    element at least 2 greater than right-end element.  
    If one is found, decrements it, then scrunches all available counts on its
    right up against its right-hand side.  Returns the modified combo.
    If none found, (that is, either no step or single step of 1), process
    done.
    """
    new_combo = []
    right_end = combo[-1]
    length = len(combo)
    c_range = range(length-1, -1, -1)
    found_step_gt_1 = False
    for index in c_range:
        value = combo[index]
        if (value - right_end) > 1:
            found_step_gt_1 = True
            break
    if not found_step_gt_1:
        return ( new_combo,True)

    if index > 0:
        new_combo += combo[:index]
    ceil = combo[index] - 1
    new_combo += [ceil]
    new_combo += [1] * ((length - 1) - index)
    need = sum(combo[index:]) - sum(new_combo[index:])
    fill_height = ceil - 1
    ndivf = need // fill_height
    nmodf = need % fill_height
    if ndivf > 0:
        for j in range(index + 1, index + ndivf + 1):
            new_combo[j] += fill_height
    if nmodf > 0:
        new_combo[index + ndivf + 1] += nmodf
    return (new_combo, False)
#def scrunch_left()

def make_combos_n_cells_ge_two( combos, max_val, n_cells, target_sum):
    """
    Build combos, list of tuples of 2 or more addends.
    """
    combo = initialize_combo( max_val, n_cells, target_sum)
    combos.append( tuple( combo))
    while True:
        (combo, done) = scrunch_left( combo)
        if done:
            break
        else:
            combos.append( tuple( combo))
    return combos
#def make_combos_n_cells_ge_two()

if __name__ == '__main__':

    combos = []
    max_val     = 8
    n_cells     = 5
    target_sum  = 20
    if n_cells == 1: combos.append( (target_sum,))
    else:
        combos = make_combos_n_cells_ge_two( combos, max_val, n_cells, target_sum)
    import pprint
    pprint.pprint( combos)
Это было полезно?

Решение

Прежде всего, я бы использовал имена переменных, которые что-то значат, чтобы код был понятен.Затем, после того, как я понял проблему, это явно рекурсивная проблема, поскольку, как только вы выбрали одно число, вопрос поиска возможных значений для остальных квадратов представляет собой точно такую ​​же проблему, но с другими значениями.

Поэтому я бы сделал это так:

from __future__ import division
from math import ceil

def make_combos(max_val,target_sum,n_cells):
    combos = []
    # The highest possible value of the next cell is whatever is 
    # largest of the max_val, or the target_sum minus the number 
    # of remaining cells (as you can't enter 0).
    highest = min(max_val, target_sum - n_cells + 1)
    # The lowest is the lowest number you can have that will add upp to 
    # target_sum if you multiply it with n_cells.
    lowest = int(ceil(target_sum/n_cells))
    for x in range(highest, lowest-1, -1):
        if n_cells == 1: # This is the last cell, no more recursion.
            combos.append((x,))
            break
        # Recurse to get the next cell:
        # Set the max to x (or we'll get duplicates like
        # (6,3,2,1) and (6,2,3,1), which is pointless.
        # Reduce the target_sum with x to keep the sum correct.
        # Reduce the number of cells with 1.
        for combo in make_combos(x, target_sum-x, n_cells-1):
            combos.append((x,)+combo)
    return combos

if __name__ == '__main__':
    import pprint
    # And by using pprint the output gets easier to read
    pprint.pprint(make_combos( 6,12,4))

Я также заметил, что ваше решение все еще кажется ошибочным.Для ценностей max_val=8, target_sum=20 and n_cells=5 ваш код не находит решения (8,6,4,1,1,), В качестве примера.Я не уверен, означает ли это, что я пропустил какое-то правило или нет, но, насколько я понимаю, правила должны быть допустимым вариантом.

Вот версия с использованием генераторов. Она экономит пару строк и память, если значения действительно большие, но в случае рекурсии генераторы может быть сложно «получить». 

from __future__ import division
from math import ceil

def make_combos(max_val,target_sum,n_cells):
    highest = min(max_val, target_sum - n_cells + 1)
    lowest = int(ceil(target_sum/n_cells))
    for x in xrange(highest, lowest-1, -1):
        if n_cells == 1:
            yield (x,)
            break
        for combo in make_combos(x, target_sum-x, n_cells-1):
            yield (x,)+combo

if __name__ == '__main__':
    import pprint
    pprint.pprint(list(make_combos( 6,12,4)))

Другие советы

Ваш алгоритм на первый взгляд кажется довольно хорошим, и я не думаю, что ОО или другой язык улучшит код.Не могу сказать, помогла бы рекурсия, но я восхищаюсь нерекурсивным подходом.Могу поспорить, что с ним было труднее работать и его труднее читать, но, вероятно, он более эффективен и определенно довольно умный.Честно говоря, я не анализировал алгоритм подробно, но он определенно выглядит так, что для его правильной работы потребовалось много времени.Могу поспорить, что было много ошибок с отклонением на 1 и странных крайних случаев, которые вам пришлось продумать, а?

Учитывая все это, по сути, все, что я пытался сделать, — это как можно лучше улучшить ваш код, заменив многочисленные C-измы более идиоматичными Python-измами.Часто то, что требует цикла в C, можно выполнить в одной строке в Python.Также я попытался переименовать вещи, чтобы лучше соответствовать соглашениям об именах Python, и немного подчистил комментарии.Надеюсь, я не обижу вас своими изменениями.Вы можете взять то, что хотите, а остальное оставить.:-)

Вот записи, которые я делал во время работы:

  • Изменен код, который инициализирует tmp к куче единиц к более идиоматичному tmp = [1] * n_cells.
  • Измененный for цикл, который суммирует tmp_sum идиоматический sum(tmp).
  • Затем заменили все петли на tmp = <list> + <list> один лайнер.
  • Взолнованный raise doneException к init_tmp_new_ceiling и избавился от succeeded флаг.
  • Регистрация init_tmp_new_ceiling на самом деле кажется ненужным.Удалив его, единственное raiseлевые были внутри make_combos_n_cells, поэтому я просто изменил их на обычные и удалил doneException полностью.
  • Нормализованное сочетание 4 пробелов и 8 пробелов для отступов.
  • Удалены ненужные круглые скобки вокруг вашего if условия.
  • tmp[p2] - tmp[p1] == 0 это то же самое, что tmp[p2] == tmp[p1].
  • Измененный while True: if new_ceiling_flag: break к while not new_ceiling_flag.
  • Вам не нужно инициализировать переменные значением 0 в верхней части ваших функций.
  • Удаленный combos list и изменил функцию на yield его кортежи по мере их создания.
  • Переименован tmp к combo.
  • Переименован new_ceiling_flag к ceiling_changed.

И вот код для вашего прочтения:

def initial_combo(ceiling=5, target_sum=13, num_cells=4):
    """
    Returns a list of possible addends, probably to be modified further.
    Starts a new combo list, then, starting from left, fills items to ceiling
    or intermediate between 1 and ceiling or just 1.  E.g.:
    Given ceiling = 5, target_sum = 13, num_cells = 4: creates [5,5,2,1].
    """
    num_full_cells = (target_sum - num_cells) // (ceiling - 1)

    combo = [ceiling] * num_full_cells \
          + [1]       * (num_cells - num_full_cells)

    if num_cells > num_full_cells:
        combo[num_full_cells] += target_sum - sum(combo)

    return combo

def all_combos(ceiling, target_sum, num_cells):
    # p0   points at the rightmost item and moves left under some conditions
    # p1   starts out at rightmost items and steps left
    # p2   starts out immediately to the left of p1 and steps left as p1 does
    #      So, combo[p2] and combo[p1] always point at a pair of adjacent items.
    # d    combo[p2] - combo[p1]; immediate difference
    # cd   combo[p2] - combo[p0]; cumulative difference

    # The ceiling decreases by 1 each iteration.
    while True:
        combo = initial_combo(ceiling, target_sum, num_cells)
        yield tuple(combo)

        ceiling_changed = False

        # Generate all of the remaining combos with this ceiling.
        while not ceiling_changed:
            p2, p1, p0 = -2, -1, -1

            while combo[p2] == combo[p1] and abs(p2) <= num_cells:
                # 3,3,3,3
                if abs(p2) == num_cells:
                    return

                p2 -= 1
                p1 -= 1
                p0 -= 1

            cd = 0

            # slide_ptrs_left loop
            while abs(p2) <= num_cells:
                d   = combo[p2] - combo[p1]
                cd += d

                # 5,5,3,3 or 5,5,4,3
                if cd > 1:
                    if abs(p2) < num_cells:
                        # 5,5,3,3 --> 5,4,4,3
                        if d > 1:
                            combo[p2] -= 1
                            combo[p1] += 1
                        # d == 1; 5,5,4,3 --> 5,4,4,4
                        else:
                            combo[p2] -= 1
                            combo[p0] += 1

                        yield tuple(combo)

                    # abs(p2) == num_cells; 5,4,4,3
                    else:
                        ceiling -= 1
                        ceiling_changed = True

                    # Resume at make_combo_same_ceiling while
                    # and follow branch.
                    break

                # 4,3,3,3 or 4,4,3,3
                elif cd == 1:
                    if abs(p2) == num_cells:
                        return

                    p1 -= 1
                    p2 -= 1

if __name__ == '__main__':
    print list(all_combos(ceiling=6, target_sum=12, num_cells=4))

Вот самое простое рекурсивное решение, которое я могу придумать, чтобы «найти все возможные комбинации n чисел со значениями x такие, что 1 <= x <= max_val и x(1) +...+ x(n) = цель».Я разрабатываю его с нуля.Вот версия вообще без какой-либо оптимизации, просто для простоты:

def apcnx(n, max_val, target, xsofar=(), sumsofar=0):
  if n==0:
    if sumsofar==target:
      yield xsofar
    return

  if xsofar:
    minx = xsofar[-1] - 1
  else:
    minx = 0

  for x in xrange(minx, max_val):
    for xposs in apcnx(n-1, max_val, target, xsofar + (x+1,), sumsofar+x+1):
      yield xposs

for xs in apcnx(4, 6, 12):
  print xs

Базовый случай n==0 (где мы не можем получить больше чисел) либо выдать кортеж, если он удовлетворяет условию, либо ничего, а затем завершить (возвратить).

Если мы должны создавать более длинные кортежи, чем мы создали до сих пор, if/else гарантирует, что мы получаем только неубывающие кортежи, чтобы избежать повторения (вы сказали «комбинация», а не «перестановка»).

А for пробует все возможности для «этого» элемента и перебирает все, что еще может дать следующий нижний уровень рекурсии.

Результат, который я вижу:

(1, 1, 4, 6)
(1, 1, 5, 5)
(1, 2, 3, 6)
(1, 2, 4, 5)
(1, 3, 3, 5)
(1, 3, 4, 4)
(2, 2, 2, 6)
(2, 2, 3, 5)
(2, 2, 4, 4)
(2, 3, 3, 4)
(3, 3, 3, 3)

что кажется правильным.

Существует множество возможных оптимизаций, но помните:

Сначала заставь это работать, затем сделай это быстро

Я переписывался с Кентом Беком, чтобы правильно атрибутировать эту цитату в «В двух словах о Python», и он рассказал мне, что получил ее от своего отца, чья работа на самом деле не была связана с программированием ;-).

В данном случае, мне кажется, ключевым вопросом является понимание что происходит, и любая оптимизация может помешать, поэтому я стараюсь "просто и понятно";мы можем, если понадобится!, оптимизировать носки, как только ОП подтвердит, что они может понять, что происходит в этой чистой, неоптимизированной версии!

К сожалению, ваш код довольно длинный и не особо читабельный.Если вы попытаетесь как-то обобщить это, возможно, кто-нибудь поможет вам написать это более четко.

Что касается самой проблемы, моей первой мыслью было бы использовать рекурсию.(Насколько я знаю, ты уже это делаешь.Еще раз извините за мою неспособность прочитать ваш код.) Подумайте, как можно свести проблему к меньшей, более простой версии одной и той же проблемы, неоднократно, пока не получите тривиальный случай с очень простым ответом.

Если быть более конкретным, у вас есть три параметра: max_val, target_sum и n_cells.Можете ли вы присвоить одному из этих чисел какое-то конкретное значение, чтобы решить чрезвычайно простую задачу, не требующую вообще никаких размышлений?Получив это, сможете ли вы свести более сложную версию проблемы к уже решенной?

РЕДАКТИРОВАТЬ:Вот мой код.Мне не нравится, как он выполняет дедупликацию.Я уверен, что есть более питонический способ.Кроме того, он запрещает использовать одно и то же число дважды в одной комбинации.Чтобы отменить это поведение, просто удалите строку if n not in numlist:.Я не уверен, что это полностью правильно, но, похоже, это работает и (ИМХО) более читабельно.Вы можете легко добавить запоминание, и это, вероятно, немного ускорит работу.

def get_combos(max_val, target, n_cells):
    if target <= 0:
        return []
    if n_cells is 1:
        if target > max_val:
            return []
        else:
            return [[target]]
    else:
        combos = []
        for n in range(1, max_val+1, 1):
            for numlist in get_combos(max_val, target-n, n_cells-1):
                if n not in numlist:
                    combos.append(numlist + [n])
        return combos

def deduplicate(combos):
    for numlist in combos:
        numlist.sort()
    answer = [tuple(numlist) for numlist in combos]
    return set(answer)

def kenken(max_val, target, n_cells):
    return deduplicate(get_combos(max_val, target, n_cells))

Прежде всего, я сам изучаю Python, поэтому это решение не будет хорошим, но это всего лишь попытка решить эту проблему.Я пытался решить ее рекурсивно и думаю, что рекурсивное решение было бы идеальным для такого рода проблем, хотя ЭТО рекурсивное решение может быть не таким:

def GetFactors(maxVal, noOfCells, targetSum):
    l = []
    while(maxVal != 0):
        remCells = noOfCells - 1
        if(remCells > 2):
            retList = GetFactors(maxVal, remCells, targetSum - maxVal)
            #Append the returned List to the original List
            #But first, add the maxVal to the start of every elem of returned list.
            for i in retList:
                i.insert(0, maxVal)
            l.extend(retList)

        else:
            remTotal = targetSum - maxVal
            for i in range(1, remTotal/2 + 1):
                itemToInsert = remTotal - i;
                if (i > maxVal or itemToInsert > maxVal):
                    continue
                l.append([maxVal, i, remTotal - i])
        maxVal -= 1
    return l



if __name__ == "__main__":
    l = GetFactors(5, 5, 15)
    print l

Вот простое решение на C/С++:

const int max = 6;
int sol[N_CELLS];

void enum_solutions(int target, int n, int min) {
  if (target == 0 && n == 0)
    report_solution(); /* sol[0]..sol[N_CELLS-1] is a solution */
  if (target <= 0 || n == 0) return; /* nothing further to explore */
  sol[n - 1] = min; /* remember */
  for (int i = min; i <= max; i++)
    enum_solutions(target - i, n - 1, i);
}

enum_solutions(12, 4, 1);

Немного оффтоп, но все равно может помочь в программировании kenken.

Я получил хорошие результаты, используя алгоритм DLX для решения Killer Sudoku (очень похоже на KenKen, там есть клетки, но только суммы).Для большинства задач это заняло меньше секунды и было реализовано на языке MATLAB.

ссылка на этот форумhttp://www.setbb.com/phpbb/viewtopic.php?t=1274&highlight=&mforum=sudoku

Убийца Судоку "Посмотрите на Википедию, не могу опубликовать гиперсвязи" DAMT Spammers

Вот наивное, но лаконичное решение с использованием генераторов:

def descending(v):
  """Decide if a square contains values in descending order"""
  return list(reversed(v)) == sorted(v)

def latinSquares(max_val, target_sum, n_cells):
  """Return all descending n_cells-dimensional squares,
     no cell larger than max_val, sum equal to target_sum."""
  possibilities = itertools.product(range(1,max_val+1),repeat=n_cells)
  for square in possibilities:
    if descending(square) and sum(square) == target_sum:
      yield square

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

for m in latinSquares(6, 12, 4):
  print m

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

def latinSquares(max_val, target_sum, n_cells):
  if n_cells == 1:
    assert(max_val >= target_sum >= 1)
    return ((target_sum,),)
  else:
    lower_bound = max(-(-target_sum / n_cells), 1)
    upper_bound = min(max_val, target_sum - n_cells + 1)
    assert(lower_bound <= upper_bound)
    return ((v,) + w for v in xrange(upper_bound, lower_bound - 1, -1)
                     for w in latinSquares(v, target_sum - v, n_cells - 1))

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

Обратите внимание на использование -(-x/y) для округления после деления.Возможно, есть более питонический способ написать это.Обратите внимание, что я использую выражения генератора вместо урожайности.

for m in latinSquares(6,12,4):
  print m
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top