permutationの解法の思いつきから実装までどのようにして辿り着くことができるか

Question

下記の問題について、どのようにして解放がおもいつき、実装完了まで辿り着くことができますでしょうか？

恐らく、ふわっと大枠3つの方針があるかと思います。

1. 順列の数式を思い浮かべながら解く。
2. まずは、木構造で問題を表現してみて、課題の見通しをよくする。
3. とりあえず、for文で書いてみてから再帰に書き換える。

上記をつかったそれぞれの解き方については、様々な動画や書籍を探って理解したつもりには、なっていますが、もしこれに似たような問題がでてきたときに、上記、3つの方法で具体的に実装までして解ききることができるかというと怪しいです。

問題

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Input: nums = [1,2,3,4]
Output: [[1, 2, 3, 4], [2, 1, 3, 4], [3, 2, 1, 4], [1, 3, 2, 4], [3, 1, 2, 4], [2, 3, 1, 4], [4, 2, 3, 1], [1, 4, 3, 2], [1, 2, 4, 3], [4, 1, 3, 2], [2, 4, 3, 1], [2, 1, 4, 3], [4, 2, 1, 3], [3, 4, 1, 2], [3, 2, 4, 1], [4, 3, 2, 1], [1, 4, 2, 3], [1, 3, 4, 2], [4, 1, 2, 3], [3, 4, 2, 1], [3, 1, 4, 2], [4, 3, 1, 2], [2, 4, 1, 3], [2, 3, 4, 1]]

出典元：46. Permutations

私がやってみたプロセス：

まず、[1,2,3,4]という少ないインプットで考え、下記の2つのコードを書きました。

コード1

def perm(nums):
    if len(nums) <= 1:
        return [nums]
    
    first = nums[0:1]
    rest = nums[1:]

    for i in range(len(nums)):
        print(rest[:i] + first + rest[i:])
    return rest

こちらのコードは、スライシングを使うことでindexをずらしながら順番を入れ替えています。このスライシングに利用しているindexをより動的にすることができれば、解答に近づけそう、とこの段階では思いました。再帰をつかうのかなとは思いつきました。

コード2

def perm(nums):
    nums_list = []
    for _ in range(len(nums)):
        for i in range(1, len(nums)):
            nums[i-1], nums[i] = nums[i], nums[i-1]
            nums_list.append(nums.copy())
    return nums_list

こちらのコードは、in-placeをすることで順番にバブルソートをしています。しかし、バブルソートをしているがゆえに隣同士の並び替えしかおこなわれず、
一周目のfor文は、[2, 1, 3, 4], [2, 3, 1, 4], [2, 3, 4, 1]のようなアウトプットしかださず、真ん中にある数字たちの場所が入れ替わった組み合わせをだすことができません。こちらは、もう一つループを追加して三重ループにすることで解答に近づけそうかなと思いました。

問題は、ここからです。
このさきのコードを何をどう実装していけばいのか、具体的に思い浮かばず、手が進みませんでした。
恐らく、再帰をつかった解答と三重ループを利用した解答があるかと思っています。

それぞれの解答とその解答にどうやって至ったか、どうして思いついたのかについてご教示頂けませんでしょうか？

Comments

[Zuishin]

人に解かせたのでは、また理解したつもりになるだけだと思いますが。
せっかくなら後に残るような時間と労力の使い方をした方がいいのでは？

Answer 1

とりあえず、コード1をベースとした考え方を説明します。

コード1は、結果をprintするだけなので、まずはnums_listに結果を集めて返すようにします。

def perm(nums):
    if len(nums) <= 1:
        return [nums]

    first = nums[0:1]
    rest = nums[1:]

    nums_list = []
    for i in range(len(nums)):
        nums_list.append(rest[:i] + first + rest[i:])
    return nums_list

これだとperm([1,2,3,4])が[[1,2,3,4],[2,1,3,4],[2,3,1,4],[2,3,4,1]]となり、
[2,3,4]部分の順番が変わらないので、この部分の順番をどうにかして変えることを考えます。

[2,3,4]の順番を変える方法を考えますが、これは[2,3,4]の順列を求めること、
つまり今作ろうとしているpermでやろうとしていることそのものであると気づきます。

[2,3,4]は上記ソースにおけるrestにあたるので、このrestについてpermを再帰呼び出しして
その結果で繰り返してあげれば、目的の順列が得られることが分かります。

def perm(nums):
    if len(nums) <= 1:
        return [nums]

    first = nums[0:1]
    rest = nums[1:]

    nums_list = []
    for r in perm(rest):
        for i in range(len(nums)):
            nums_list.append(r[:i] + first + r[i:])
    return nums_list

Comments

[sequelanonymous]

コメントありがとうございます。
このコード読みながらなかなか自分だけで解答にたどり着ける自信がいまだに持てないので下記についてご確認させてください。

下記の点までは気づくことができました。
> [2,3,4]の順番を変える方法を考えますが、これは[2,3,4]の順列を求めること、
つまり今作ろうとしているpermでやろうとしていることそのもので

下記の点についてはどうしてそう思いましたでしょうか？
> [2,3,4]は上記ソースにおけるrestにあたる

また、下記の考えを思いつくのにbase caseから頭の中で逆算してシュミレートして再帰でいける、って思いつく感じなのでしょうか？
> このrestについてpermを再帰呼び出ししてその結果で繰り返してあげれば

私の場合、top-downなアプローチなのは理解しているものの、再帰実装するときは、イメージがふわっとした感じなので、ご確認させていただきました。

[actorbug]

>下記の点についてはどうしてそう思いましたでしょうか？
>> [2,3,4]は上記ソースにおけるrestにあたる
実際のこの関数の引数に[1,2,3,4]を与えて、[2,3,4]になるのがどの変数か調べればわかるはずです。

>また、下記の考えを思いつくのにbase caseから頭の中で逆算してシュミレートして再帰でいける、って思いつく感じなのでしょうか？
>> このrestについてpermを再帰呼び出ししてその結果で繰り返してあげれば
思いつくも何も、permが順列を求める関数ということから直接導き出しているにすぎません。
permを呼び出すのが再帰呼び出しにあたると意識して呼び出しているわけではありません。
たまたま、必要としている処理が、作ろうとしていた処理と同じだったというだけです。

再帰関数を自作する際のコツは、「目的の関数がすでに完成している」とみなして使うことです。
ただし、再帰呼び出しに渡す引数が、元の引数より小さい(サイズだったり、数値の大きさだったり)必要があるので、そこだけ注意しましょう。

[sequelanonymous]

> 再帰関数を自作する際のコツは、「目的の関数がすでに完成している」とみなして使うことです。

この意識、私もしっくりきました。この意識をしながら何度か再帰の問題を訓練してみようと思います。ありがとうございます。

Answer 2

コード2のほうをベースに考えました。

具体的には、与えられたnumsに対して、隣接する一組の要素同士の交換操作：

nums[i-1], nums[i] = nums[i], nums[i-1]

を順次適用していくループによって順列の集合を作っていき、新しい順列が作られなくなったところでループを終了させます。最初に与えられるnumsおよびnumsの要素を交換して出来る順列をsetの要素にしたいので、リストではなくタプルで表すことにしました。

まず、

nums[i-1], nums[i] = nums[i], nums[i-1]

による、隣接した要素の交換を以下のような関数にしておきます。

def swap_neighbors(nums, i):
    if i < 1 or len(nums) <= i:
        raise ValueError('指定されたインデクスが範囲外')
    ls = list(nums)
    ls[i-1], ls[i] = ls[i], ls[i-1]
    return tuple(ls)

上記の swap_neighbors()関数を使って perm(nums) を以下のように書きました。

def perm(nums):
    permutations = { nums }
    swap_operations = [i for i in range(1, len(nums))]
    
    target_nums_ls = [nums]
    next_target_nums_ls = []

    while len(target_nums_ls) > 0:
        for target_nums in target_nums_ls:
            for op in swap_operations:
                swapped_nums = swap_neighbors(target_nums, op)
                if not swapped_nums in permutations:
                    permutations.add(swapped_nums)
                    next_target_nums_ls.append(swapped_nums)
        target_nums_ls = next_target_nums_ls
        next_target_nums_ls = []

    return permutations

• 実行例） はじめに与えられるnums が (1, 2, 3, 4 ,5) の場合 ➡ サンプル (replit.com)

上記の perm(nums) は、新しい順列ができなくなるまで、とにかく交換操作のすべてを適用していき、それによって出来た順列のすべてについて、再び交換操作を行っていくという、あまり賢くないアルゴリズムの実装ですので、

こちらは、もう一つループを追加して三重ループにすることで解答に近づけそうかなと思いました。

というイメージの先にある（いわば、脳みそに汗をかいた）ものではないです。タプルを集合(set)の要素にできて、集合(set)はin 演算子によって、ある値がその集合に含まれるかを判定できるという、Python組み込みのデータ構造の力に頼った解です。

補足：

また、上記のperm(nums)がこの問題の解のひとつであることを主張するには、厳密には、以下の命題の証明が必要と思います。

【命題】
昇順に整列された順列　P0 = (1, 2, ・・・ , n) を並べ替えてできる任意の順列 P = (f(1), f(2), ・・・ f(n))（ただしfは、集合A={1, 2, ・・・ n}として、AからAへの一対一かつ上への写像）とする。また隣接する（i-1）番目の要素とi番目の要素を交換する操作を s(i) とする。このとき、P0 に対して、s(i)を有限回適用することで、任意の P にできる。

この【命題】、正しいのかな？ っていうのがあります。（先のサンプル では、一応(気休めとして）、(1, 2, 3, 4, 5) に対するperm関数の返す集合の要素数が 5! の120であることを確認していますが。）

正しいとすれば、その証明はどこかの大学の情報科学科の授業だったり課題の資料を探せば出てきそうですね。

補足2:
上記【命題】の証明は、数学的帰納法を使えばできそうです。（ちゃんと書いてみたわけではないけど）

Answer 3

質問の「解放」は「解法」の間違いですね。

nums の要素の i番目を先頭にして、残りを perm したものを後ろにくっつければいいと考えました。

def perm(nums):
	if len(nums) == 1: return [nums]
	return sum([[[nums[i]]+a for a in perm(nums[:i]+nums[i+1:])]
		for i in range(len(nums))], [])

nums = [1, 2, 3, 4]
print(perm(nums))

Answer 4

• 解答

def add_right(elem, lst):
    return [l+[elem] for l in lst]

def perm(nums):
    if len(nums) == 1:
        return [nums]
    return sum([add_right((nums2:=nums.copy()).pop(i), perm(nums2)) for i in range(len(nums))], [])

実行結果

>>> print(perm([1, 2, 3, 4]))
[[4, 3, 2, 1], [3, 4, 2, 1], [4, 2, 3, 1], [2, 4, 3, 1], [3, 2, 4, 1], [2, 3, 4, 1], [4, 3, 1, 2], [3, 4, 1, 2], [4, 1, 3, 2], [1, 4, 3, 2], [3, 1, 4, 2], [1, 3, 4, 2], [4, 2, 1, 3], [2, 4, 1, 3], [4, 1, 2, 3], [1, 4, 2, 3], [2, 1, 4, 3], [1, 2, 4, 3], [3, 2, 1, 4], [2, 3, 1, 4], [3, 1, 2, 4], [1, 3, 2, 4], [2, 1, 3, 4], [1, 2, 3, 4]]

• その解答にどうやって至ったか

ライブラリを使わずに順列を作る問題だと読んだときに、再帰とリストのsumを使うことはわかります。

forループで回せば書けることはわかっていますが、もっと簡単に書くためにはセイウチ演算子を使えばよさそうだということも少し考えればわかります。

書き始めてみると、評価順序の問題で関数を分けたほうがよさそうだと感じたので関数を分けました。