사전 순 정렬에서 순열 생성과 정렬?

Question

나는 약간 혼란 스럽다. Lexicographic Order에서 순열을 생성하는 문제는 정렬 문제와 다른 점은 무엇입니까? 누군가 예를 들어 설명해 주시겠습니까? 감사합니다

Answer 1

두 가지가 있습니다. N! 순열이 있지만 단 하나의 정렬 된 순서 만 있습니다 (정렬 된 순열은 사전 식으로 가장 작습니다).

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

Here가 사전 식 순서 순열을 생성 ++ C에서 프로그램이다 : 여기

brown fox quick 

가 사전 식 순서 치환의리스트이다 : 여기

는 정렬 순열의 예이다 :

#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의 선택, N-2의 선택, 그리고 나서 1의 2 선택. 실행중인 "what 's left"목록에 대한 색인 값으로서 이러한 선택 사항은 변수 - 기본 숫자로 볼 수 있습니다.

오른쪽에서 왼쪽으로 자릿수를 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) = 다음 (N-1)! = 1, 등등. 이러한 인덱스 값은 lex로 표시됩니다. 주문. 그런 다음 정렬 된 집합에서 기호를 선택하십시오 (syms [0], syms [1], ...이 원하는 순서대로 있으면 임의의 임의 액세스 모음이됩니다).

다음은 몇 가지 코드입니다. Project Euler 문제에 대한 작업. 단지 인덱스 값을 생성하고, n 중에서 k 개의 심볼의 순열을 선택할 수 있습니다. 헤더 파일의 기본값은 k이고, 인수 검사 코드는 이것을 n으로 변환하고 전체 길이 순열을 생성합니다. 또한 표기법이 변경되었습니다. "인덱스"는 순열 ("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--; 
     }    
} 


}