Kenken Puzzle Addend : Redux A (수정) 비 수수제 알고리즘

Question

이 질문은 1 <= x <= maxval 및 x (1) + ... + x (ncells) =이므로 값 X와 NCELLS 숫자의 가능한 모든 조합을 찾도록 요청하는 Kenken Latin Square 퍼즐의 일부와 관련이 있습니다. 대상. 더 유망한 답변 중 몇 가지를 테스트 한 후에는 Lennart Regebro에게 답변을받을 것입니다.

1. 그의 일상은 내 일 (+-5%)만큼 빠르며

2. 그는 내 원래 루틴이 어딘가에 버그를 가지고 있다고 지적하여 그것이 실제로 무엇을하려고했는지 알게되었습니다. 고마워, Lennart.

Chrispy는 Lennart와 동등한 것으로 보이는 알고리즘을 기여했지만 5 시간 후에 Sooo는 먼저 와이어를 얻습니다.

발언 : Alex Martelli의 Bare-Bones Recursive Algorithm은 가능한 모든 조합을 만들고 체로 던지고 구멍을 통과하는 것을 보는 예입니다. 이 접근법은 Lennart 또는 Mine보다 20 배 이상 걸립니다. (입력을 max_val = 100, n_cells = 5, target_sum = 250으로 잭업하고 내 상자에는 18 초 대 8+ 분입니다.) Moral : 가능한 모든 조합을 생성하지는 않는 것이 좋습니다.

또 다른 발언 : Lennart와 나의 루틴이 생성됩니다 같은 순서로 동일한 답변. 실제로 다른 각도에서 보이는 동일한 알고리즘입니까? 모르겠어요.

나에게 뭔가 일어난다. 답을 정렬하면 (8,8,2,1,1)로 시작하고 (4,4,4,4,4)로 끝나는 경우 (max_val = 8, n_cells = 5, target_sum으로 얻는 것 = 20), 시리즈는 "가장 느린 하강"의 종류를 형성하며, 첫 번째는 "뜨거운"이고 마지막은 "콜드"이며 그 사이의 가장 큰 단계는 가장 큰 단계입니다. 이것은 "정보 엔트로피"와 관련이 있습니까? 그것을 보는 적절한 메트릭은 무엇입니까? 열의 하강 (또는 오름차순) 순서로 조합을 생성하는 알고리즘이 있습니까? (이것은 내가 볼 수있는 한, 짧은 스트레칭에 가깝지만 정규화 된 std. dev.를보고 있지만).

파이썬 루틴은 다음과 같습니다.

#!/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

우선, 코드가 이해할 수 있도록 무언가를 의미하는 변수 이름을 사용합니다. 그런 다음 문제를 이해 한 후에는 하나의 숫자를 선택하면 나머지 사각형에 대한 가능한 값을 찾는 문제는 정확히 동일한 문제이지만 다른 값이 다른 것이 분명히 재귀적인 문제입니다.

그래서 나는 이것처럼 할 것입니다.

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 2

당신의 알고리즘은 첫 번째 홍당무에서 꽤 잘 보이며, OO 나 다른 언어가 코드를 개선 할 것이라고 생각하지 않습니다. 재귀가 도움이되었을 지 말할 수는 없지만 비 수수적인 접근 방식에 감탄합니다. 나는 그것이 일하기가 더 어려웠고 읽기가 더 어려웠지만 더 효율적 일 가능성이 높고 확실히 영리합니다. 솔직히 말해서 나는 알고리즘을 자세히 분석하지 않았지만 정확하게 작업하는 데 시간이 오래 걸리는 것처럼 보입니다. 나는 1-1의 오류가 많았고 당신이 생각해야 할 이상한 가장자리 케이스가 있었을 것입니다.

그 모든 것을 감안할 때, 기본적으로 내가 시도한 것은 수많은 C-Ims를 더 관용적인 Python-ism으로 대체함으로써 가능한 한 최선을 다해 코드를 올렸습니다. 종종 C로 루프가 필요한 것은 파이썬에서 한 줄로 수행 할 수 있습니다. 또한 Python Naming Conventions를 더 잘 따르는 이름을 바꾸고 의견을 약간 정리하려고했습니다. 내 변화에 대해 당신을 화나게하지 않기를 바랍니다. 당신은 당신이 원하는 것을 가져 가서 나머지를 떠날 수 있습니다. :-)

내가 일할 때 취한 메모는 다음과 같습니다.

• 초기화하는 코드를 변경했습니다 tmp 1에 더 관용적으로 tmp = [1] * n_cells.
• 변경 for 요약하는 루프 tmp_sum 관용적으로 sum(tmp).
• 그런 다음 모든 루프를 a로 교체했습니다 tmp = <list> + <list> 짧막 한 농담.
• 움직이는 raise doneException 에게 init_tmp_new_ceiling 그리고 그것을 제거했습니다 succeeded 깃발.
• 체크인 init_tmp_new_ceiling 실제로 불필요한 것 같습니다. 그것을 제거하면, 유일한 것 raiseS가 남아 있었다 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.

그리고 여기에 당신의 ferusal 코드는 다음과 같습니다.

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 3

다음은 "1 <= x <= max_val 및 x (1) + ... + ... + x (n) = target"을 값으로 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)

정확해 보입니다.

가능한 최적화가 있지만 기억하십시오.

먼저 작동하게 한 다음 빠르게 만듭니다

나는 Kent Beck과 일치 하여이 인용문을 "Python in a Nutshell"로 올바르게 기인했으며, 그는 실제로 프로그래밍과 관련이없는 아빠로부터 그것을 얻었습니다 ;-).

이 경우 핵심 문제는 이해 무슨 일이 일어나고 있는지, 그리고 모든 최적화가 방해 할 수 있으므로, 나는 "단순하고 이해할 수있는"것을 위해 모두 나가고 있습니다. 필요하다면!, OP가 확인하면 양말을 최적화 할 수 있습니다. ~할 수 있다 이 순수하고 최적화되지 않은 버전에서 무슨 일이 일어나고 있는지 이해하십시오!

Answer 4

죄송합니다. 코드는 길고 특히 읽을 수 없습니다. 어떻게 든 요약하려고하면 누군가가 더 명확하게 쓰는 데 도움을 줄 수 있습니다.

문제 자체에 관해서는, 나의 첫 번째 생각은 재귀를 사용하는 것입니다. (내가 아는 모든 것에 대해, 당신은 이미 그렇게하고 있습니다. 코드를 읽을 수 없어서 다시 죄송합니다.) 문제를 동일한 문제의 더 작은 버전으로 줄일 수있는 방법을 생각하십시오. 매우 간단한 답변이있는 사소한 사례.

좀 더 구체적으로하려면 Max_val, Target_sum 및 N_Cells의 세 가지 매개 변수가 있습니다. 전혀 생각할 필요가없는 매우 간단한 문제를 해결하기 위해 그 숫자 중 하나를 특정 값으로 설정할 수 있습니까? 일단 당신이 그것을 가지고 있다면, 당신은 이미 해결 된 문제로 약간 더 어려운 문제를 줄일 수 있습니까?

편집 : 여기 내 코드가 있습니다. 나는 그것이 복제하는 방식이 마음에 들지 않습니다. 나는 더 피스닉 방식이 있다고 확신합니다. 또한 한 번의 조합으로 동일한 숫자를 두 번 사용하여 분리됩니다. 이 동작을 취소하려면 줄을 꺼내십시오. if n not in numlist:. 이것이 완전히 정확한지 확실하지 않지만 작동하는 것처럼 보이며 (IMHO) 더 읽기 쉬운 것 같습니다. 당신은 쉽게 회고록을 추가 할 수 있으며, 아마도 그것을 상당히 높이게 할 것입니다.

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

Answer 5

우선, 나는 파이썬 직접 배우고 있으므로이 솔루션은 좋지 않지만 이것은 단지 이것을 해결하려는 시도 일뿐입니다. 나는 그것을 재귀 적으로 해결하려고 노력했으며 재귀 솔루션은 이런 종류의 문제에 이상적이라고 생각합니다.

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 6

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 7

약간의 오프 토피이지만 여전히 Kenken을 프로그래밍하는 데 도움이 될 수 있습니다.

나는 살인자 스도쿠를 해결하기 위해 DLX Algorhitm을 사용하여 좋은 결과를 얻었습니다 (Kenken은 케이지가 있지만 합계 만). 대부분의 문제에 대해 2 위도 걸렸으며 Matlab 언어로 구현되었습니다.

이 포럼을 참조하십시오http://www.setbb.com/phpbb/viewtopic.php?t=1274&highlight=&mforum=sudoku

Killer Sudoku "Wikipedia 봐, 캔트 하이퍼 링크"Damt Spammers

Answer 8

다음은 발전기를 사용하는 순진하지만 간결한 솔루션입니다.

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 9

그리고 여기에는 또 다른 재귀 적 발전기 기반 솔루션이 있지만 이번에는 간단한 수학을 사용하여 각 단계에서 범위를 계산하여 불필요한 재귀를 피합니다.

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

이 코드는 만족할 수없는 매개 변수를 공급하는 경우 어시스트러러로 실패합니다. 이것은 우리가 불필요한 재귀를하지 않는 나의 "정확성 기준"의 부작용입니다. 그 부작용을 원하지 않으면 어설 션을 제거하십시오.

분할 후 -(-x/y)를 사용하는 것을 주목하십시오. 그것을 쓰는 더 피스닉 방법이있을 수 있습니다. 또한 사용 중입니다 발전기 표현식 수율 대신.

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