わからない時はGoogleやStackoverflowなどインターネットを活用して検索、質問すればどこかに答えが転がっている、そんな感じ

最近、leetcode.comのアルゴリズムのeasyの問題を適当に解いてます。書籍「独学プログラマー」で紹介されていました。有料のプレミアム会員にならなくても、問題を解くだけなら会員になるだけ。Pythonの練習に、という感じ。英語のサイトなので、英語の内容を読み解く必要があります。

Next Permutation - LeetCode

この問題を解こうとしたのですが、

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

 まず "permutation" がわからず、また "lexicographically next greater permutation of numbers" もわからず・・・。意味的に順列だとかなんとか程度しかわからず。leetcodeのDiscussionは基本、解答しかない（どんだけシンプルかつ早い処理を書いたー！みたいな）ので、検索してみることに。permutationについてWikipediaの内容がいいよーとStackoverflowで紹介されていたのでその通りにすると解けました。

Wikipedia has a nice article on lexicographical order generation. It also describes an algorithm to generate the next permutation.

Quoting:

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

1. Find the highest index i such that s[i] < s[i+1]. If no such index exists, the permutation is the last permutation.
2. Find the highest index j > i such that s[j] > s[i]. Such a j must exist, since i+1 is such an index.
3. Swap s[i] with s[j].
4. Reverse the order of all of the elements after index i till the last element.

Permutation - Wikipedia

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l greater than k such that a[k] < a[l].
3. Swap the value of a[k] with that of a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[n].

日本語の説明には上記の条件についてどこに書いてあるのかわかりませんでした。日本語または日本人にとっては常識、当たり前な知識というか条件なんでしょうね。

アルゴリズムというかプログラミングについては沢山書いて書き慣れるというか、考え方を練習して早く慣れるようにしていきたいですね。一つの問題を解くのに1時間〜2時間は当たり前みたいなのはちょっと・・・と。でも、楽しいです。

paiza.hatenablog.com

ちょうどPaizaの方がこのようなアルゴリズムについて学べる本の詳細をしてくださってました。

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

世界でもっとも強力な9のアルゴリズム

上記の条件を考えながら書いた処理は、

class Solution:
　def nextPermutation(self, nums):
　　"""
　　:type nums: List[int]
　　:rtype: void Do not return anything, modify nums in-place instead.
　　"""
　　nums_len = len(nums)
　　largest_index = 0
　　for i in range(nums_len-1):
　　　if nums[i] < nums[i+1]:
　　　　largest_index = i
　　　next_largest = 0
　　for j in range(nums_len):
　　　if nums[j] > nums[largest_index]:
　　　　next_largest = j
　　if nums[largest_index] == nums[next_largest]:
　　　nums.sort()
　　else:
　　　nums[largest_index], nums[next_largest] = nums[next_largest], 　nums[largest_index]
　　　j = nums_len-1
　　　tmp_list = []
　　　while j > largest_index:
　　　　tmp_list.append(nums[j])
　　　　j -= 1
　　　n = 1
　　　for i in tmp_list:
　　　　nums[largest_index + n] = i
　　　　n += 1 

アップル 13．3インチ MacBook Air(1．8GHz Dual Core i5 / 8GB / 128GB) MQD32J/A