algorithm - 辞書式順序と並べ替えで順列を生成しますか？

Question

私は少し混乱しています。辞書式順序で順列を生成する問題は、並べ替えの問題とどのように異なりますか？誰かが例を挙げて説明してもらえますか？ありがとう

Answer 1

これらは2つの異なるものです。順列はありますがN!、並べ替え順序は1つだけです（並べ替えられた順列は辞書式順序で最小です）。

ソートされた順列の例を次に示します。

brown fox quick

辞書式順序での順列のリストは次のとおりです。

brown fox quick
brown quick fox
fox brown quick
fox quick brown
quick brown fox
quick fox brown

辞書式順序で順列を生成するC++のプログラムは次のとおりです。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int main() {
    vector<string> s;
    s.push_back("quick");
    s.push_back("brown");
    s.push_back("fox");
    sort(s.begin(), s.end());
    do {
        for(int i = 0 ; i != s.size() ; i++) {
            cout << s[i] << " ";
        }
        cout << endl;
    } while (next_permutation(s.begin(), s.end()));
    return 0;
}

Answer 2

Permutationsの問題では対処されていませんsorting。

それらを関連付けることができる1つの方法は、辞書式順序ではない順列を生成する場合、辞書式順序で取得するように並べ替えることです。ただし、これには階乗スペースが必要です。生成は通常、一度に1つの要素を吐き出すため、すべての要素をメモリに保持する必要はありません。

Answer 3

辞書式順序でn番目の順列を生成するかなり簡単な方法があります。順列要素を選択する際に行う選択のセットは次のとおりです。Nの1つ、次にN-1の1つ、次にN-2の1つ、...次に2つのうちの1つを選択し、最後に1つだけ残ります。これらの選択肢は、実行中の「残り」リストへのインデックス値として、変数ベースの数値と見なすことができます。

数字は右から左にd[1]= n％2、d [2] =（n / 2）％3、d [3] =（n / 6）％4、...d[として展開できます。 k] =（n / k！）％（k + 1）。結果は、最初の（N-1）に対してd [N-1]==0になります。順列、次の（N-1）！の場合はd [N-1]==1など。これらのインデックス値がlexに含まれることがわかります。注文。次に、ソートされたセットからシンボルを選択します（syms [0]、syms [1]、...が希望の順序である場合は、任意のランダムアクセスコレクションで実行できます）。

これが、プロジェクトオイラーの問題に取り組むために私が作成したコードです。インデックス値を生成するだけで、nからk個のシンボルの順列を選択できます。ヘッダーファイルのデフォルトはkから-1であり、引数チェックコードはこれをnに変換し、完全な長さの順列を生成します。ここでも表記法が変更されています。「index」は順列の数（上記の「n」）であり、「n」は設定されたサイズ（上記の「N」）です。

vector<int> pe_permutation::getperm(long long index, int n, int k)
{

if (n<0) throw invalid_argument("permutation order (n)");
if (k<0 || k>n) 
{
    if (k==-1) 
        k=n;
    else throw invalid_argument("permutation size (k)");
}
vector<int> sset(n, 0); // generate initial selection set {0..n-1}
for (int i=1; i<n; ++i)
    sset[i] = i;

//  Initialize result to sset index values.  These are "without replacement"
//  index values into a vector that decreases in size as each result value
//  is chosen.  

vector<int> result(k,0);
long long r = index;
for (int m=n-k+1; m<=n; ++m)
{
    result[n-m] = (int)(r % m);
    r = (r / m);
}

// Choose values from selection set:

for (int i=0; i<k; ++i)
{
    int j = result[i];
    result[i] = sset[j];
    sset.erase(sset.begin()+j);
}
return result;

} // getperm(long long, int, int)

Answer 4

import java.util.*;
public class Un{

    public static void main(String args[]){
        int[]x={1,2,3,4};

        int b=0;int k=3;
        while(b!=(1*2*3*4)){

            int count=0;
            while(count!=6){
                for(int i=2;i>0;i--){
                    int temp=x[i];
                    x[i]=x[3];
                    x[3]=temp;
                    count++;
                    System.out.println(x[0]+""+x[1]+""+x[2]+""+x[3]);
                 }

            } 
            b+=count;
            int temp=x[0];
            x[0]=x[k];
            x[k]=temp;
            k--;
       }            
 }


}