algorithm - 按字典顺序生成排列与排序？

Question

我有点困惑。以字典顺序生成排列的问题与排序问题有何不同？有人可以用一个例子向我解释吗？谢谢

Answer 1

这是两个不同的东西。有N!排列，但只有一个排序顺序（排序排列在字典上是最小的）。

下面是一个排序排列的例子：

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。

它们可能相关的一种方式是，如果您生成的排列不是按字典顺序排列的，那么您可以排序以按字典顺序排列。然而，这需要有阶乘空间。生成通常一次吐出一个元素，因此不必将所有元素都保存在内存中。

Answer 3

有一种相当简单的方法可以按字典顺序生成第 n 个排列。您在选择置换元素时所做的一组选择是：从 N 中选择 1，然后从 N-1 中选择 1，然后从 N-2 中选择 1，......然后从 2 中选择 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！排列，d[N-1]==1 用于下一个 (N-1)!，依此类推。您可以看到这些索引值将在 lex 中。命令。然后从排序集中选择符号（如果 syms[0], syms[1], ... 符合您想要的顺序，则任何随机访问集合都可以。）

这是我为解决 Project Euler 问题而编写的一些代码。它只生成索引值，并允许从 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--;
       }            
 }


}