pythonでアルゴリズムの勉強をしていたのですが、途中で躓いてしまいました。再帰の適切な使い方を教えていただけないでしょうか

Question

pythonを用いてアルゴリズムの初心者向けの問題集を解いていたのですが、ある問題の途中で躓いてしまいました。再帰の使い方が間違っているのはわかっているのですが、どのように書けば適切に動くのかがわかりません。正しい書き方を教えていただけると嬉しいです。また、再帰以外の部分で改善点があったり、もっと良い解法があれば、後学のため教えていただけないでしょうか。

問題は以下のような内容です。

”いちごが円周上に並んだホールケーキの切り分け方について考えてみましょう。ホールケーキをN個に切り分けるとき、全てのケーキに乗っているいちごの数が１〜N個とすべて異なっているようにしたいです。なおかつ、隣り合った２つのケーキに乗っているいちごの数の合計が、いずれも平方数となるようにします。このような条件を満たすことができる最小のN(>1)を求めてください。

N個に切り分けるとき、いちごの数は合計でN(N+1)/2個となります。

例えばN=4のとき、いちごの数が１個となるもの、３個となるもの、２個となるもの、４個となるもの、という順番で切ったとします。この切り方は「ケーキに乗っているいちごの数がすべて数が異なる」という条件は満たしているものの、１個と３個のペア以外、３＋２のペア、２＋４のペア、４＋１のペアいずれも「隣り合っているケーキのイチゴの合計が平方数」という条件を満たしていないので、この切り方は条件を満たさないことになります。

問題の答えはN＝３２,条件を満たす並べ方は
[1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15]
のようです。

自分が書いたスクリプトは下記の通りです。

def adding_next_number(boolean, n, circle_list, num_list, square):
    if num_list == []:
        num_sum = circle_list[-1] + 1
        if num_sum in square:
            print(n)
            boolean == False
    else:
        for num in num_list:
            last_num = circle_list[-1]
            num_sum = last_num + num
            if num_sum in square:
                circle_list.append(num)
                num_list.remove(num)
                boolean, n, circle_list, num_list, square = adding_next_number(boolean, n, circle_list, num_list, square)
    
    return boolean, n, circle_list, num_list, square


def main():
    n = 2
    boolean = True
    while boolean == True:
        num_list = [i for i in range(2, n+1)]
        square = [i**2 for i in num_list if i**2 < n*2]

        circle_list = [1,]
        boolean, n, circle_list, num_list, square = adding_next_number(boolean, n, circle_list, num_list, square)

        n += 1


if __name__ == "__main__":
    main()

検証する数ｎについて、２からｎまでの数が収められたリスト（num_list）と隣り合ったケーキのイチゴの数が取りうる平方数が収められたリスト（square）を用意します。次に切り方の順番通りに数字を格納していくリスト、circle_listを用意します。Nの値にかかわらずイチゴが１個のケーキは存在するので、circle_listには予め１を格納しておいて、ここを皮切りに数字を格納していけるか検証していきます。

格納する数字を選ぶ関数がadding_next_number()です。もしcircle_listの末尾の数字とnum_listに残っている数字の合計が平方数になったらcircle_listに数字を格納します。そしてここで再帰を利用して次に格納される番号を調べにいく、といった内容で書いています。

書いている途中からわかってはいたのですが、この書き方だといつまでたっても答えを見つけることができません。仮に検証する数がN=３１だとすると、circle_listの末尾との合計が平方数となる数字がnum_listに残っていない状態、つまりcircle_listが

[1, 3, 6, 10, 15, 21, 4, 5, 11, 14, 2, 7, 9, 16, 20, 29]

となった途端に、N＝３１の場合についての検証は終わってしまいます。

同様に本来であれば正解であるはずのN=32の場合でも、circle_listが同じ

[1, 3, 6, 10, 15, 21, 4, 5, 11, 14, 2, 7, 9, 16, 20, 29]

となった段階で検証が終了し、正解として出力されません。

circle_listへの格納がうまくいかなくなったタイミングで、一つ前の状態にもどって別の選択肢がないか考えるようなコードを書きたいのですが、どのように書いたら良いのかわかりません。そもそも、もっとスマートな書き方があるような気もするのですが、それも気がするという以上のものではない状態です。

アイデアをお持ちの方がいらっしゃいましたら、ご助言をいただけたるととても助かります。
ご協力いただけると幸いです。よろしくお願いいたします。

##回答を修正することができました。ご協力いただき有難うございました。

人のスクリプトを読んで理解するという経験がまだまだ少ないので教えていただいたリンク先のスクリプトを読み解くのに時間がかかってしまい、返事とお礼が遅れてしまいました。解き方自体が勉強になっただけではなく、人のスクリプトを読んで理解する体験が自分にとってはとても貴重なものでした。
リンク先の解き方をそのまま真似することはできなかったですが、じっくりスクリプトを読んでいく中でなんとかオリジナルの解き方というか修正の仕方を思いつくことができました。まだまだ初心者なのでとても体力がいる作業でしたが貴重な経験になりました。有難うございました。

def adding_numbers(N, S, C):
    new_list = []

    for l in C:
        N_copy = list(N)
        
        l_copy = list(l)
        l_copy.remove(1)

        for num in l_copy:
            N_copy.remove(num)
        
        for num in N_copy:
            n_sum = num + l_copy[-1]

            if n_sum in S:
                l_copy_2 = list(l)
                l_copy_2.append(num)

                new_list.append(l_copy_2)
    
    if new_list == []:
        return N, S, new_list

    elif len(new_list[0]) == len(N) + 1:
        the_final_list = []

        for l in new_list:
            n_sum = l[-1] + 1
            if n_sum in S:
                the_final_list.append(l)

        return N, S, the_final_list
    
    else:
        return adding_numbers(N, S, new_list)


def main():
    
    n = 2
    while True:
        # N -> numbers, S -> squares, C -> circle_list

        N = [i for i in range(2, n+1)]
        S = [i**2 for i in range(2, int((2*n - 1)**0.5 + 1))]

        C = []
        for i in N:
            n_sum = i + 1
            if n_sum in S:
                new_list = [1, i]
                C.append(new_list)
        
        if C != []:
            N, S, C = adding_numbers(N, S, C)
        
        if C != []:
            print(n)
            for l in C:
                print(*l)
            break

        n += 1


if __name__ == '__main__':
    main()

Comments

[tiitoi]

これですかね？
https://www.geeksforgeeks.org/permutation-numbers-sum-two-consecutive-numbers-perfect-square/

[tmp]

そのリンク先には両端の平方数の条件がないです。「ホール」が、両端が隣となる条件ですよね

[退会済みユーザー]

そうです。ケーキは円形なので両端は隣合う平方数です。上の32の正解には、右回りと左回りの鏡像パターンがでます。鏡像は同一とみてよいのでしょうね。

[NirohShimashita]

tiitoiさん、 tmpさん、 amdahlslawさん、ありがとうございます。
こういう問題をハミルトン路問題というということさえ知らなかったです。
tmpさんがおっしゃってくださったようにホール型（循環）には対応していないスクリプトのようですが、そこは最後に両端を確認すればOKなので、スクリプトそのままでもとても参考になりました。
隣あってもよい数字の組み合わせを一番最初に総当たりで確認してしまって表にしておくという解き方がされているようで、もしかしたらよくある解き方なのかも知れないですが、自分にはこんな解き方もあるんだなと驚きでした。自分にとってはちょっとワンランク上の解き方なので今すぐこの解き方を真似するのは難しいなと思ったのですが、そのかわりこのスクリプトをじっくり理解しようとする中で、オリジナルの解き方をなんとか思いつくことができました。

時間をさいてご協力いただき有難うございました。とても勉強になりました。

Answer 1

python初心者です。あらかじめscalaで確認したうえでpythonを記述しました。作成する平方数の数列の末尾の数を基準に、平方数の候補リストを作り、候補リストを順に読みながら、再帰的に次の平方数を探索します。

平方数を判定する

import math
def issquare(a, b):
  r = int(math.sqrt(a+b))
  return (0 == (r * r - a - b))

与えられた数から平方数の集合を発見する

与えられた数(last)と、残りの数字の集合(b)から、lastとの和が平方数になるものを発見し、平方数の集合と、平方数以外の数の集合に分ける。

def findSuccesors(last, b, acc=[], rem=[]):
  if not b:
    return (acc,rem)
  elif issquare(last,b[0]):
    acc.append(b[0])
    return findSuccesors(last,b[1:],acc,rem)
  else:
    rem.append(b[0])
    return findSuccesors(last,b[1:],acc,rem)

ある平方数と残りの数列を順次生成するジェネレータ

平方数の集合(acc)と、それ以外の集合(rem)から (accのひとつの数,(残りの数の集合(acc+rem-ひとつの数))を順に返す。

def candidatesStream(acc,rem):
    wacc = set(acc + rem)
    for e in set(acc):
        remainder = list(wacc - set([e]))
        yield (e, remainder)

平方数の後者を再帰的に探す

残りの数列(remdr)がnum_listに、平方数の数列(acc)がcircle_listに相当する。結果を格納するfoundを用意する。状態を保持するために再帰の引数にcopy.deepcopy()を使っている。

import copy
def seek(last, remdr, acc=[], found=[]):
  if not remdr: # 残りの数がなくなった
    if issquare(last,acc[0]): # 両端が平方数か？
        acc.append(last)
        found.append(acc)
  else:
    ss, rr = findSuccesors(last, remdr, [], [])
    if ss: # 平方数になる後者の集合がある場合
      acc.append(last)
      for (s,r) in candidatesStream(ss,rr): # 後者を順に、再帰的に探索する
        seek(s,copy.deepcopy(r),copy.deepcopy(acc),found)
  return found

動作確認

N=32を確認するため、seekの引数に、先頭の数 1 と残りの数列[2 .. 32]を与える。

#import sys
#sys.setrecursionlimit(10000)
for e in seek(1,[x for x in range(2,33)],[],[]):
    print(e)

結果は以下の２件。右回りと左回りの鏡像パターンがでる。
[1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15]
[1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8]

追記：解説とコードの改良 (2019-03-07)

解決済みになったあとですが、のちに検索されるかもしれないので、情報を追加しておきます。

解説

課題のなかに再帰的なデータ構造が見つかれば、再帰的な処理を行います。

データ構造

データ構造は以下のとおり。
(すでに出来上がった数列、末尾の数)、(残りの数列)
処理の開始時点では、(1) 、(2 ... )です。

(残りの数列)になれるのは、[(末尾の数に足して平方数になる数)(残りの数列)] です。
(残りの数列)はこの構造が入れ子になっているリストです（再帰的なデータ構造）。
[(末尾の数に足して平方数になる数)([(末尾の数に足して平方数になる数)( ... [(末尾の数に足して平方数になる数)()]])]

ある時点で、(末尾の数に足して平方数になる数)が、複数あるかもしれないし、まったくないかもしれない。

• なければ、数列の作成を中止。
• あれば、それぞれの候補を使って、(残りの数列)に再帰的な処理を行います。

(残りの数列)がゼロになったら、(すでに出来上がった数列)の両端の平方数判定を行い、正しいか調べます。

再帰処理

回答のコードは明示的な終了条件を持ちません。後続の候補の全てに再帰的に平方数の探索を行います。後続の平方数がなければそこでreturnするし、最後まで探索すれば両端判定をおこなってreturnします。すべての候補を調べ尽くした後に終了し、正解があれば戻り値のリストに入っています。もしも、正解が見つかった時点で終了したければ、再帰呼び出しの都度、戻り値を調べて、正解があれば即座にbreakすればよいです。

集合分割の汎用関数

再帰を使わない集合分割関数を見つけました。ラムダ式(cond)、と集合(b)を引数にとり、集合をcond条件によって二分割する。

def partition(cond,b):
  acc, rem = [], []
  for num in b:
    (acc if cond(num) else rem).append(num)
  return (acc,rem)

上の集合分割関数を利用する平方数の分割関数です。ラムダ式で平方数判定を行います。

def findSuccesors2(last,b):
  return partition(lambda x: issquare(last,x),b)

リストのコピー

リストのスライス機能をつかえばdeepcopyは不要。

        seek(s,r[:],acc[:],found) # seek(s,copy.deepcopy(r),copy.deepcopy(acc),found)

Streamという用語

このプログラムはScalaで作成したあとpythonに移植しました。Scala(Java)のコレクションでは、Streamはイテレータと同義で、遅延評価されるリストのことです。Streamは、(先頭の要素,(未評価のリスト))が入れ子構造になっています。後ろが未評価なのでHskellなどと同様に無限集合が扱えます。Couseraで公開しているScala講座のビデオをみると、Martin Odersky教授が、関数型プログラミングのデータ構造として、遅延評価するかしないかにかかわらず、この構造を繰り返し説明しています。このデータ構造と再帰処理がセットになるので、いつか学んでみるのもよいかもしれません。

pythonに移植したあとの名前をGenreratorかIteratorとしてください。

def candidatesIterator(acc,rem):
  wacc = set(acc + rem)
  for e in set(acc):
    remainder = list(wacc - set([e]))
    yield (e, remainder)

Comments

[NirohShimashita]

amdahlslawさん、有難うございます。

amdahlslawさんに書いていただいたスクリプトだと条件を満たすすべてのパターンが出力されるのが最高です。pythonについては初心者とのことですがfor文とyieldの組み合わせの使い方や関数の分け方は自分にはちょっと真似できないレベルでやっぱりプロフェッショナルは言語不問なんだなと感じました。

それからcopyモジュールについてやcopy.copy()とcopy.deepcopy()の違い、システムパラメーターで再帰の上限を設定する方法も今回始めて知りました。教えていただきたいこと以上のことを学べるスクリプトを書いていただいて有り難いです。有難うございました。

[NirohShimashita]

とんでもなく詳しい解説をつけてくださり有難うございます。データ構造や再帰と終了条件について、再帰を使わずに集合を分割する方法について（(acc if cond(num) else rem).append(num)＜ーこんな書き方あるんですね）、簡易なリストのコピーの仕方について、教えていただき有難うございます。それからCourseraというサービスを初めて知りました。まだ受講はしていませんがアカウントだけ作りました。今英語の勉強もしてみているところですぐすぐ受講できるほどの語学力はないのですぐすぐの受講はできませんが、いずれチャレンジしてみたいと感じました。視野を広げていただいて有難うございます。

[退会済みユーザー]

Courseraにpythonのコースがあると思います。無料で受講できますが、有料を選ぶと資格証明書を発行してくれます。もうひとつのオンラインコース。edxは完全無料です。参加大学が異なりますが、Courseraとほぼ同じ内容です。MITのコースをおすすめします。

[NirohShimashita]

有難うございます…！覗いてきてみます。