akmhmgc · akmhmgc · Oct 4, 2025 · tokuhirat · Oct 5, 2025 · akmhmgc
diff --git a/46/step1.md b/46/step1.md
@@ -0,0 +1,32 @@
+# step1 何も見ずに解く
+[1,2,3]の場合、
+[[]]
+[[1], [2], [3]]
+[[1, 2], [1, 3], [2, 3],[2, 1], [3, 1], [3, 2]]
+といった形で増やしていけば良さそう。
+つまり、配列の各permutationにまだ追加していない値があれば追加したものを加えるというループを繰り返してpermutationの長さがnumsのサイズになれば終了すれば良い。
+
+```ruby
+# @param {Integer[]} nums
+# @return {Integer[][]}
+def permute(nums)
+    permutations = [[]]
+    while permutations.first.size < nums.size
+        next_permutations = []
+        permutations.each do |permutation|
+            next_permutations.concat((nums - permutation).map { |num| (permutation + [num]) })
+        end
+        permutations = next_permutations
+    end
+    permutations
+end
+```
+
+ある時点でのpermutationの長さをkとすると、
+```
+(nums - permutation).map { |num| (permutation + [num]) }
+```
+の部分で(n - k) * kの計算量がかかる。
+これを各階層のノードの数とかけて0 - nのkについて合計すると、計算量はO(n * n!)になる。
+空間計算量は最終的に作られるpermutationの数 * 各permutationの長さなのでO(n * n!)
+nの最大値が6なので1秒以内で間に合うが、少しでも大きくなったらどうしようもなさそう。
diff --git a/46/step2.md b/46/step2.md
@@ -0,0 +1,58 @@
+# step2 他の方の解答を見る
+
+## 使用中のnumsをSetにいれるかどうか
+https://github.com/Ryotaro25/leetcode_first60/pull/54#discussion_r1986035628
+
+numsの中でpermutationで使われていないものを取り出す時に線形に検索するとnが乗ってしまう。
+これは(Intersection of Two Arrays)[https://leetcode.com/problems/intersection-of-two-arrays/editorial/]と同じ話かと思った。
+
+https://github.com/tokuhirat/LeetCode/pull/50/files#r2278840164
+一方で、問題の制限はnが6以下であるし、オーバーヘッドを加味すると配列のまま計算する方が速いかもしれない。
+ハッシュテーブルにした方が速くなるくらいのサイズだとそもそも現実的な計算時間で終わらなくなっている気もするな…
+
+と思ってRubyのコードを読んだところ、特定の長さの配列まではハッシュテーブルを使わずに線形探索していた。
+そういえば積集合をとる`&`も同じことをしていたんだった。
+ref: https://github.com/ruby/ruby/blob/5257e1298c4dc4e854eaa0a9fe5e6dc5c1495c91/array.c#L5558-L5583
+
+## 再帰で解く
+https://github.com/ryosuketc/leetcode_arai60/pull/39
+
+```ruby
+# @param {Integer[]} nums
+# @return {Integer[][]}
+def permute(nums)
+    permute_helper = lambda do |nums|
+        permutes = []
+        append_permutes = lambda do |permute, nums|
+            if nums.empty?
+                permutes << permute 
+                return
+            end
+            nums.each_with_index do |num, i|
+                new_permute = permute + [num]
+                new_nums = nums[0...i] + nums[(i + 1)..-1]
+                append_permutes.call(new_permute, new_nums)
+            end
+        end
+        append_permutes.call([], nums)
+        permutes
+    end
+    permute_helper.call(nums)
+end
+```
+
+## step1の改善
+
+```ruby
+# @param {Integer[]} nums
+# @return {Integer[][]}
+def permute(nums)
+    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] })
+        end
+    end
+    permutes
+end
+```
diff --git a/46/step3.md b/46/step3.md
@@ -0,0 +1,15 @@
+# step3 3回続けて10分以内に書いてエラーを出さなければOKとする
+
+```ruby
+# @param {Integer[]} nums
+# @return {Integer[][]}
+def permute(nums)
+    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] })
+        end
+    end
+    permutes
+end
+```
diff --git a/46/step4.md b/46/step4.md
@@ -0,0 +1 @@
+## step4 レビューを受けて解答を修正
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1 @@
		## step4 レビューを受けて解答を修正