Conversation
| end | ||
| permute_helper.call(nums) | ||
| end | ||
| ``` |
There was a problem hiding this comment.
はじめに読んだ時、lambda がネストされていて難しく感じました。nums はブロックパラメータに書かなくても読めるはずなので書かれているのはなんでだろうと思いました。処理を読むと append_permutes の nums はまだ追加していない nums であり、ブロックパラメータに書く必要があるとわかりました。また、permute_helper は入出力が permute と同じなのでまとめられないかなと思いました。自分だったら以下のように書くと思います。
def permute(nums)
results = []
permute_helper = lambda do |permuted_prefix, remaining_nums|
if remaining_nums.empty?
results << permuted_prefix
return
end
remaining_nums.each_with_index do |num, i|
new_permuted_prefix = permuted_prefix + [num]
new_remaining_nums = remaining_nums[0...i] + remaining_nums[(i + 1)..-1]
permute_helper.call(new_permuted_prefix, new_remaining_nums)
end
end
permute_helper.call([], nums)
results
endThere was a problem hiding this comment.
コメントありがとうございます。
おっしゃる通りlambdaの引数として利用しているnumsが関数の引数の名前と同じでかなり読みにくいですね。
あと外側のlambdaには引数は不要ですね。
個人的にはresultsをlambdaの外のものを変更するのがあまり好きではないので以下のように書こうと思います。
# @param {Integer[]} nums
# @return {Integer[][]}
def permute(nums)
permute_helper = lambda do
permutes = []
append_permutes = lambda do |permute, remaining_nums|
if remaining_nums.empty?
permutes << permute
return
end
remaining_nums.each_with_index do |num, i|
new_permute = permute + [num]
new_nums = remaining_nums[0...i] + remaining_nums[(i + 1)..-1]
append_permutes.call(new_permute, new_nums)
end
end
append_permutes.call([], nums)
permutes
end
permute_helper.call
endThere was a problem hiding this comment.
少し考えたのですが、この程度であればlambdaはネストさせなくても良い気がしてきました。
permute内に処理が追加されるようなら検討しても良いかもしれません。（その時はlamdaをネストさせるより別のメソッドに切り出すかもしれないですが）
| def permute(nums) | ||
| permutes = [[]] | ||
| while permutes.first.size != nums.size | ||
| permutes = permutes.each_with_object([]) do |permute, next_permutes| |
There was a problem hiding this comment.
細かいですが、permuteは動詞の印象があるので、この辺の変数の名前はpermutationsやpermsにしたいかもしれません。
| permutes = [[]] | ||
| while permutes.first.size != nums.size | ||
| permutes = permutes.each_with_object([]) do |permute, next_permutes| | ||
| next_permutes.concat((nums - permute).map { |num| permute + [num] }) |
There was a problem hiding this comment.
こちらのやり方はこちらのやり方で読みやすいと思いますが、割と広く知られている手法としては、次のようなバックトラッキングを用いたやり方で順列を生成するアルゴリズムがあると思います。
(LLMに書かせたコードなので読みにくかったらすみません)
def permute_inplace(nums)
res = []
backtrack = ->(first) do
if first == nums.length
res << nums.dup
return
end
(first...nums.length).each do |i|
nums[first], nums[i] = nums[i], nums[first]
backtrack.call(first + 1)
nums[first], nums[i] = nums[i], nums[first] # 元に戻す
end
end
backtrack.call(0)
res
endどこまで作ったかのindexを渡すことで、途中まで作った順列を表す配列それ自体にnums - permuteを含めることができるというのと、各要素の各段階において新しい配列を作る必要がない、という部分で多少効率的かと思います。
There was a problem hiding this comment.
ありがとうございます！
発想にまだ慣れていないですがコード自体は読みやすいです。
解いた問題
46. Permutations
使用言語
Ruby
次に解く問題
78. Subsets