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

Question

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

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

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

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

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

Еще одно замечание: Леннарт и мои процедуры генерируют одинаковые ответы в том же порядке . Являются ли они фактически одним и тем же алгоритмом, видимым с разных сторон? Я не знаю.

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

Вот процедура 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)

Answer 1

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

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

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

• Изменен код, который инициализирует tmp, с кучей 1, на более идиоматический tmp = [1] * n_cells.
• Изменен for цикл, который суммирует tmp_sum на идиоматический sum(tmp).
• Затем заменил все петли на tmp = <list> + <list> однострочник.
• Перемещено raise doneException в init_tmp_new_ceiling и избавлено от флага succeeded.
• Регистрация в init_tmp_new_ceiling на самом деле кажется ненужной. Удаляя его, единственные raise s остались в 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 список и изменена функция на 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))

Answer 2

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

Так что я бы сделал это так:

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

Answer 3

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

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 пробует все возможности для элемента "this" и перебирает все, что еще может дать следующий-нижний уровень рекурсии.

Вывод, который я вижу:

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

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

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

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

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

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

Answer 4

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

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

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

убийца судоку "посмотрите на википедию, не можете опубликовать гиперссылку" damt spammers

Answer 5

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

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) для округления после деления. Там может быть более питонический способ написать это. Заметьте также, что я использую выражения генератора вместо yield.

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

Answer 6

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

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

Answer 7

Вот простое решение на C / 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);

Answer 8

Прежде всего, я сам изучаю 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

Answer 9

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

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

Чтобы быть более конкретным, у вас есть эти три параметра: 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))