KenKenパズルaddends:REDUX A(訂正)非再帰的アルゴリズム

Question

この問題が関係するそれらの部品のKenKenラスパズルをお願いすべての組み合わせが可能ncells数値ようなxが1 <=x <=maxval x(1)+...+x(ncells)=targetsum.この試験により有望な応答、私の受賞に回答-受賞すLennart Regebroで:

1. 彼の間の違いによって発生すると鉱山(+-5%)、

2. ることも日常のあったバグのどこかにかかっています。おかげさLennart.

chrispyしたアルゴリズムにもそういう相当のLennartのが、5時間後でも、最初のワイヤーを返します。

A備考:Alexッリの素骨の再帰的アルゴリズムの一例ですので組み合わせて投げについてふるいに見る通穴があります。このアプローチの20%+倍Lennartの鉱山である.(ジャッキの入力max_val=100,n_cells=5,target_sum=250マイボックスで18秒前8+分） 徳:は生成で組み合わせが良いです。

他備考:Lennart、私のルーチンを生成 同じ答えを同じ順序で.ているものと同じアルゴリズムが様々な角度から?わかりません。

何か起こった。た場合の並べ替えの答えを起点と、(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

まず第一に、私は、コードが分かり得るように、何かを意味変数名を使用すると思います。私は問題を理解した後、次に、それはあなたが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や他の外国語習得にチャレンジを向上させたものです。どちらともいえない場合は再帰いたもののラウンドを突破したのは非再帰的アプローチ.私はベットでは難しかったかという読みものがより効率的なレコード店ディスクユニオンの非常に巧妙なものだったんだ。素直になれなかった分析のアルゴリズムを詳細にそのように見えるものには長いが働きます。私はベットがoff-by-1エラーとなっエッジケースで考え抜きか。

その中でも、基本的にはすべてにしようとしてきたアップコードをケージプレートもご提供してき替えにより多くのC-ismsと慣用的Python-アクセス等の脅威から機密性多くの場合には何が必要でループCできる一つの回線エラーになります。もう名前の変更も追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 い不要となります。取り除いていただいても、 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.

このコードの閲覧:

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

ここで私は考えることができる最も簡単な再帰的な解決策は、「値xように、1 <= xと<= MAX_VALとX（1）+ ... + X（N）=ターゲットと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)

正しい思われる。

bazillion可能な最適化がありますが、覚えてます：

  

まずそれを動作させる、そして

それは速く作ります

私はきちんと「一言ではPython」で、この引用符を帰するケントベックと一致し、そして彼はその仕事、実際のプログラミングには無関係だった、彼のお父さんからそれを得た私に語った; - 。）

この場合、何が起こっている重要な問題は、を理解のあるように思われ、いずれかの最適化を妨げる可能性があるので、私は「シンプルで理解しやすい」のすべてをアウトつもりです。必要であれば、OPは、彼らがを確認したら、私たちは、！、それオフに靴下を最適化することができは、この膨大で何が起こっているかを理解し、最適化されていないバージョン！

Answer 4

言って申し訳ありませんが、あなたのコードは、種類の長い、特に読めません。あなたは何とかそれを要約しようとすることができる場合は、多分誰かがあなたがより明確にそれを書くことができます。

問題自体については、私が最初に考えたのは、再帰を使用することです。 （私が知っているすべてについて、あなたはすでにそれをやっている。申し訳ありませんがもう一度あなたのコードを読んで、私のことができないため。）あなたが繰り返し、同じ問題の少ない容易なバージョンに問題を減らすことができる方法を考えて、あなたが持っているまで非常に単純な答えとの些細なケースます。

もう少し具体的に、あなたは、これらの3つのパラメータ、MAX_VAL、target_sum、およびn_cellsを持っています。あなたは、これらの数字の1はあなたにまったく考えを必要としない非常に簡単な問題を与えるために、いくつかの特定の値に設定することはできますか？あなたがいることをしたら、あなたは1を解決し、既にへの問題の少し難しいバージョンを減らすことができますか？

編集：ここに私のコードです。私はそれが重複除外ん道を好きではありません。私はより多くのPython的な方法があります確信しています。また、1つの組み合わせで二度同じ番号を使用して禁止します。この動作を元に戻すには、ちょうどライン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))

Answer 5

すべての

まず、私は自分自身ので、このソリューションは素晴らしいことではないだろうが、これは、これを解決するにちょうど試みであるの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 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

リトルビットofftopicが、それでもプログラミングKENKENで役立つ場合があります。

私は（それがケージを持ってKENKENとして非常にsimmilarが、唯一の合計）サムナンプレを解決するためのDLXのalgorhitmを使用して良い結果を得ました。これは、問題のほとんどのための秒未満を取って、それがMATLAB言語で実装されました。

このフォーラムを参照します http://www.setbb.com/phpbb/viewtopic。 PHP？トン= 1274＆ハイライト=＆mforum =数独の

キラー数独 「ウィキペディアを見て、カントポストハイパーリンク」damtスパマー

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

このコードは、あなたが満足することは不可能であるパラメータを指定した場合はAssertionErrorで失敗します。これは我々が不要な再帰を行うことはありません、私の「正しさの基準」の副作用です。あなたはその副作用をしたくない場合は、アサーションを削除します。

分割後切り上げする - （ - X / Y）

の使用に注意してください。それを書くためのより多くの神託の方法があるかもしれません。注また、私の代わりにをジェネレータ式を使用しています歩留まりのます。

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