初投稿記事です。お手柔らかにお願いいたします。
順列・組み合わせを返す再帰関数のテンプレート
まずは雛形を示します。
def create_lists(mylist=[]):
if is_answer(mylist): # a boolean which indicates mylist could be an answer.
return mylist
result = []
for c in get_appendable(mylist): # a list of elements which can be added.
x = create_lists(mylist+[c])
if len(x)!=0 and type(x[0]) is list:
result.extend(x)
elif len(x)!=0:
result.append(x)
return result
is_answer(mylist)はmylistが終了条件を満たしているかのBoolean値を返す関数です。
get_appendable(mylist)はmylistに追加可能な要素のリストを返す関数です。
利用例
問： 3以上7以下の自然数から3つ選び、いずれも互いに素である組み合わせをすべて挙げよ。
答えを先に言えば [3, 4, 5], [3, 4, 7], [3, 5, 7], [4, 5, 7], [5, 6, 7] の5組です。
当問題に適用できるis_answer関数とget_appendable関数は例えば下のように記述できます。
def is_answer(mylist):
return len(mylist) == 3
def get_appendable(mylist):
primes = [2, 3, 5]
numbers = [3, 4, 5, 6, 7]
appendable = []
for n in numbers:
if n > max(mylist,default=0):
if all([[m%p for m in mylist+[n]].count(0)<2 for p in primes]):
appendable.append(n)
return appendable
is_answer関数は非常にシンプルです。要素数が3つのリストならTrueを返します。
[2, 5, 6] のような、問の要請を満たさない組み合わせにもTrueを返してしまいますが、
仕様上、そもそもこのような配列がcreate_lists関数に与えられることはありません。
get_appendable関数の動作としましては、mylistの最大値より大きいもので、
mylistに追加してもいずれも互いに素という条件を満たしうる自然数の配列を返すものです。
例えば [3] を与えると [4, 5, 7] を返しますが、これら1つ1つが追加可能ということです。
print(create_lists())
# [[3, 4, 5], [3, 4, 7], [3, 5, 7], [4, 5, 7], [5, 6, 7]]
上述したis_answer関数とget_appendable関数を定義してからcreate_lists関数を呼ぶと、
上記の様な結果が返ってきます。先に示した答えと一致していることがわかります。
本題（福岡の猫島巡り）
福岡県には猫島と称される離島(上図赤字)が6つあり、全て本土から定期船が出ています。
上記の雛形を利用し、猫島全てを土・日の2日間で巡ることが可能な経路を導いてみました。
必要な情報は下記の2点です。いずれもWebサイトやGoogle mapで得て整形しました。
①各島への定期船の出港・帰港時刻
②本土側にある各港間の移動所要時間（移動手段は車を仮定）
出港・帰港時刻は個別に定義せず、必要な滞在時間を満足できる組み合わせで与えました。
例えば相島行11:10出港-14:10帰港のような形です。
ただし土日を入れ替えただけの順列を出力しないよう、相島行きは土曜日に限定しました。
本題に係るコードは私的かつ煩雑であるため割愛します。
得られた順列はわずか2パターンのみでした。下に示します。
【土曜日】
地島 行 07:45 発 09:05 帰港
大島 行 11:15 発 13:25 帰港
相島 行 14:30 発 16:00 帰港
玄界島 行 16:45 発 20:20 帰港
【日曜日】
小呂島 行 09:00 発 14:25 帰港
姫島 行 16:00 発 17:25 帰港
【土曜日】
姫島 行 07:50 発 10:05 帰港
大島 行 11:15 発 13:25 帰港
相島 行 14:30 発 16:00 帰港
玄界島 行 16:45 発 20:20 帰港
【日曜日】
小呂島 行 09:00 発 14:25 帰港
地島 行 15:10 発 17:55 帰港
地島も姫島も本土の港への公共交通機関を利用したアクセスは良くないため、
レンタカーを利用する場合には前入りが必須という結論となりました。
福岡近辺にお住いで、自家用車をお持ちの方ならば土日で巡れそうですね。
上記の旅程が実際に機能するかは波・道路の状態にも依存します。
またここで利用したダイヤは2022年9月現在のものであり、今後変わる恐れもあります。
実際に試されて損害を被られたとしても、私は責任を負えませんのでご留意ください。
以上となります。最後までお読みいただきありがとうございました。