1. 序章


このチュートリアルでは、繰り返しのある順列を生成するための再帰的で反復的なアルゴリズムを紹介します。 繰り返しのあるすべての順列を見つけることは、セットのすべての組み合わせを生成するのような組み合わせ問題です。


2. 繰り返しのある順列








セットの繰り返しを伴う順列は、要素が由来し、繰り返される可能性のある順序付きタプルです。タプルの長さがである場合、それらを-tuplesと呼びます。 たとえば、とを使用すると、以下は4タプルになります。


      


私たちのタスクは、セットのすべてのタプルを生成することです。 の場合、そのようなタプルがあります。


ここでは、の形式を取ります。 要素の各セットをにマップできるため、そうすることで一般性を失うことはありません。 したがって、各タプルを元のセットの要素にマップすることができます。


表記を簡単にするために、の代わりに記述します。


3. 繰り返しを伴う順列を生成するための再帰的アルゴリズム


上の誘導による繰り返しで順列を定義することができます：


    

  1. の場合、唯一の順列は、として示す空の順列です。
    2. 

  2. の場合、からの数字を-tupleの前に付けることで、任意の-tupleを取得できます。
    3. 



これらのルールは、再帰的に従うロジックを提供します。 は基本ケースであり、それぞれについて、取得した各タプルの前にすべてを追加します。


3.1. 擬似コード


再帰的ソリューションの擬似コードは次のとおりです。






3.2. 例


関数がどのように機能するか見てみましょう。  それと、3つのタプルすべてを見つけたいとしましょう。 呼び出しは2タプルを返します。


      


-tuplesを取得するには、最初にすべての2-tuplesに1を付加して、次のようにします。


      


次に、2を追加します。


      


次に、3、4、および5で同じことを行った後、すべての3タプルを取得します。


4. 繰り返しを伴う順列を生成するための反復アルゴリズム


再帰的アルゴリズムは、すべてのタプルを生成すると、タプルを使用可能にします。 つまり、最初にすべてを生成する前に、タプルにアクセスすることはできません。 それらがあるので、再帰的アルゴリズムの空間の複雑さはです。  私たちのアプリケーションがメモリに制約がある場合、これは進むべき道ではありません。


さらに、通常、順列をフィルタリングして、それらの一部のみを保持する必要があります。 したがって、実行時にはいつでも単一のタプルを処理することになります。そのため、すべての順列を格納する必要はありません。 次のようなことができれば最高です。


    

  • 順列を求める
    • 

  • それを処理し、前のステップに進んで別のタプルを要求します
    • 



その場合、必要なのはスペースだけです。これは、メモリの複雑さが。で指数関数的に増加する再帰的アルゴリズムと比較して大幅に削減されます。 入力として順列を受け取り、辞書式順序で次の順列を返すアルゴリズムを使用して、これを実現できます。そのアルゴリズムに名前を付けましょう。 次に、最初の順列から始めて、を呼び出すことにより、他のすべての順列を繰り返し生成して処理します。




したがって、次の順列がある場合はそれを返し、最後のタプルの後継を要求する場合は返す必要があります。 しかし、どのように実装しますか？


4.1. 次の順列の生成


これが主なアイデアです。 順列とその後継には、共通の接頭辞があります。 たとえば、、は、の後継であり、それらの共通プレフィックスはです。 異なる接尾辞はより右下から始まります。 この例では、それは4インチでした。 それを1つインクリメントして、を取得します。


ただし、これはすべてのケースを網羅しているわけではありません。 変更しようとしているサフィックスにが含まれている場合はどうなりますか？ 考えてみましょう。 3より下の右端の要素。 ただし、1ずつインクリメントすると、が得られますが、実際の後続はです。 それで、正しい論理は何ですか？


解決策は、毎回実行する必要のある操作が循環増分であることを理解することです。 1に変更するを除いて、すべての数値を1つ増やします。 ただし、すべての数値がに等しい場合、後継者はありません。 これが最後の順列なので、呼び出し元のループを停止するために戻る必要があります。


4.2. 擬似コード


これがの擬似コードです：




ご覧のとおり、補助変数を除けば、は入力の後続変数を見つけるためにメモリ以上のものを必要としません。


4.3. 例


例を考えてみましょう。 それを言ってみましょう。


まず、変更するサフィックスがどこから始まるかを決定します。 7より下の右端の要素は2であるため、変更するサフィックスは。です。 次に、2を1ずつ増やして3を取得し、7つすべてを1に置き換えます。 取得する順列は、です。これは正しい結果です。


をの代わりに使用した場合、1を法として増分することになります。


5. 結論


この記事では、集合の繰り返しですべての順列を生成する2つの方法を紹介しました。 再帰的アルゴリズムはすべての順列を一度に返しますが、反復法はそれらを1つずつ処理し、スペースの複雑さを軽減します。