次に大きな順列

2020年11月26日)

3つの異なる色の順列

まず、順列の意味を理解しましょう。ウィキペディアからの定義によると、「 数学 順列 set は、大まかに言えば、そのメンバーを シーケンスに配置したものです。 em> または 線形順序 、またはセットがすでに順序付けられている場合、その要素の再配置。 「順列」という言葉は、順序集合の線形順序を変更する行為またはプロセスも指します。

したがって、定義が言うように、順列とは、特定のオブジェクトのセットを再配置することを意味します。すべての可能な注文。上の図からわかるように、{RGB、RBG、GRB、GBR、BRG、BGR}の6つの方法で3つの異なる色を配置できます。

可能な配置の数を計算する数式nの異なるオブジェクトについては、n!で与えられます。ここでn! = n *(n-1)*(n-2)*…* 1

特定のシーケンスのすべての順列を体系的に生成する方法はたくさんあります。古典的なアルゴリズムの1つは、次の順列が存在する場合、それを字句/辞書/アルファベット順に見つけることに基づいています。

したがって、ここでの問題の説明は、アルファベットのセットが与えられることです。それを文字列と呼びます。次の字句のアルファベットのセット、次の字句の大きい文字列、または現在の文字列と同じアルファベットのセットを持つ現在の文字列の後に辞書で次に来る文字列を見つける必要があります。

理解を深めるために、数字の例を見てみましょう。

数字= [4,5,2,6,7,3,1]
次に大きい数字は= [4,5,2、 7,1,3,6 ]

ブルートフォース

最初に頭に浮かぶのは、与えられた数のすべての順列を見つけ、現在の数よりも大きいそれらの順列の最小のものが私たちの答えになるということです。上で見たように、nがあります!可能性(n =数の桁数)、すべての桁を別個のものと見なすため、特定の数のすべての順列を見つけ続けると、計算にO(n!)時間がかかります。 nが大きい場合、これは非常に時間の複雑さです。

最適化

これをどのように改善できるかを考える必要があります。注意深く観察すると、おそらくより小さな数のセットの場合、パターンが表示される可能性があります。いくつかの例を試してみましょう。

[2,1,3] =次に大きい数は231
[1,1,5] =次に大きい数は151
[2,3 、5,4] =次に大きい数は2435です
[3,2,1] =考えられるすべての順列から現在の数よりも大きい数を形成することはできません

上記からのポイント観察:

ケース1:[3,2,1]

ここでは、右端から移動を開始し、最初の減少要素を見つけて、それを次の要素に置き換えることができるようにします。右側からそれ自体よりも大きい要素。

ケース1:次に大きい要素は増加しないシーケンスで可能

ケース2:[2,3,5,4]

index = 1、右端から最初に減少する要素のインデックス
3より大きい次に大きい要素をi = 1の右側で、nums [i]
これで、i = 1以降の残りの要素を昇順で並べ替えて最小の要素を作成します。i= 1以降の要素は既に非昇順で並べ替えられているため、単純に逆にすることができます

このグラフは、4と5を入れ替えても、8から始まるシーケンス、つまり86432がまだ増加しない順序で並べ替えられていることを示しています。最初の減少する要素を、それよりも少し大きい要素に置き換えているので、非常に明白です。したがって、増加しない順序を維持します。

ここからもう1つ観察できるのは、インデックスj = i + 1から右に向かって次に大きい要素を検索しているときに、インデックスjで検索を停止できることです。 nums [j]がnums [i]以下になると、そのインデックスの後の要素は決してbになりません。 eがnums [i]より大きい。

コードスニペット

次のコードでは、次に大きい場合に備えて順列は不可能です。可能な限り最小の順列に変換しています

複雑性分析

時間計算量= O(n){最悪の場合に最初の減少要素を見つけるために、例えば[1,5,4,3,2]} + O(n){右側の残りのサブ配列で次に大きい数を見つける} + O(1){最初の減少する要素を次に大きい要素と交換する} + O(n / 2){サブ配列をi +1からlenに反転して昇順で並べ替える} = O(n)

追加スペースは必要ないため、余分なスペースは必要ありません。 。
したがって、スペースの複雑さ:O(1)

この記事に時間を割いていただきありがとうございます。お役に立てば幸いです。明確な洞察が得られます。

まだご不明な点がございましたら、お気軽にお問い合わせください。役に立ったら、同僚と共有してください。あなたの拍手は私にもっとそのようなブログを書くように動機づけます! 🙂