Skip to main content

​
Lexicographic (or dictionary) Ordering

The permutation a1 a2 … ana_1 ~ a_2 ~ \dots ~ a_n precedes(mendahului) the permutation of b1 b2 … bnb_1 ~ b_2 ~ \dots ~ b_n, if for some kk, with 1≤k≤n,a1=b1,a2=b2,…,ak−1=bk−11 \leq k \leq n, a_1 = b_1, a2 = b2, \dots , a_{k-1} = b_{k-1}, and ak<bka_k < b_k In other words, a permutation of the set of the n smallest positive integers precedes (in lexicographic order) a second permutation if the number in this permutation in the first position where the two permutations disagree is smaller than the number in that position in the second permutation.
Dengan kata lain, permutasi dari himpunan bilangan bulat terkecil terkecil mendahului (dalam urutan leksikografis) permutasi kedua jika nomor dalam permutasi ini di posisi pertama di mana dua permutasi tidak sesuai lebih kecil dari angka di posisi itu di kedua permutasi.

​
Example

The permutation 23415 of the set {1,2,3,4,5}\{1, 2, 3, 4, 5\} precedes the permutation 23514, because these permutations agree in the first two positions, but the number in the third position in the first permutation, 4, is smaller than the number in the third position in the second permutation, 5. Similarly, the permutation 41532 precedes 52143.
Permutasi 23415 dari himpunan mendahului permutasi 23514, karena permutasi ini sama dalam dua posisi pertama, tetapi angka di posisi ketiga dalam permutasi pertama, 4, lebih kecil daripada nomor di posisi ketiga dalam permutasi kedua, 5. Demikian pula, permutasi 41532 mendahului 52143.

​
Algorithm based on Lexicographic

Find the integers aja_j and aj+1a_{j+1} with aj<aj+1a_j < a_{j+1} and aj+1>aj+2>⋯>ana_{j+1} > a_{j+2} > \dots > a_n,
The next larger permutation in lexicographic order is obtained by putting in the jth position the least integer among aj+1,aj+2,…,ana_{j+1}, a_{j+2}, \dots , a_n that is greater than aja_j and listing in increasing order the rest of the integers aj,aj+1,…,ana_j, a_{j+1}, \dots, a_n in positions j+1j + 1 to nn.

​
Example

What is the next permutation in lexicographic order after 362541?Solution:
The last pair of integers aja_j and aj+1a_{j+1} where aj<aj+1a_j < a_{j+1} is a3=2a_3 = 2 and a4=5a_4 = 5.
The least integer to the right of 2 that is greater than 2 in the permutation is a5=4a_5 = 4.
Hence, 4 is placed in the third position.
Then the integers 2, 5, and 1 are placed in order in the last three positions, giving 125 as the last three positions of the permutation. Hence, the next permutation is 364125.

​
Algortithm Generating the Next Permutation in Lexicographic Order

procedure next permutation(a1,a2,…,ana_1, a_2, \dots, a_n : permutation of
        {1,2,…,n}~~~~~~~~ \{1, 2, \dots, n\} not equal to n n−1 … 2 1n ~ n-1 ~ \dots ~ 2 ~ 1)
j:=n−1j := n - 1
while aj>aj+1a_j > a_{j+1}
    j:=j−1~~~~ j := j - 1
{j\{j is the largest subscript with aj<aj+1}a_j < a_{j+1}\}
k:=nk := n
while aj>aka_j > a_k
    k:=k−1~~~~ k := k - 1
{ak\{a_k is the smallest integer greater than aja_j to the right of aj}a_j\}
Interchange aja_j and aka_k
r:=nr := n
s:=j+1s := j + 1
while r>sr > s
    ~~~~ interchange ara_r and asa_s
    r:=r−1~~~~ r := r - 1
    s:=s+1~~~~ s := s + 1 {\{ this puts the tail end of the permutation after the jjth position in increasing order }\} {a1 a2 … an\{ a_1 ~ a_2 ~ \dots ~ a_n is now the next permutation }\}

​
Generating Combinations

An rr-combination can be represented by a sequence containing the elements in the subset in increasing order.
Kombinasi rr dapat direpresentasikan oleh urutan yang berisi elemen dalam subset dalam urutan meningkat.
The rr-combinations can be listed using lexicographic order on these sequences.
Kombinasi rr dapat dicantumkan menggunakan urutan leksikografis pada urutan ini.
In this lexicographic ordering, the first rr-combination is {1,2,…,r−1,r}\{1, 2, \dots, r - 1, r\} and the last rr-combination is {n−r+1,n−r+2,…,n−1,n}\{n - r + 1, n - r + 2, \dots, n - 1, n\}.
Dalam urutan leksikografis ini, kombinasi rr pertama adalah {1,2,…,r−1,r}\{1, 2, \dots, r - 1, r\} dan kombinasi rr terakhir adalah {n−r+1,n−r+2,…,n−1,n}\{n - r + 1, n - r + 2, \dots, n - 1, n\}.
The next rr-combination after a1 a2 … ara_1 ~ a_2 ~ \dots ~ a_r can be obtained in the following way: First, locate the last element aia_i in the sequence such that ai≠n−r+ia_i \neq n - r + i.
Kombinasi rr berikutnya setelah a1 a2 … ara_1 ~ a_2 ~ \dots ~ a_r dapat diperoleh dengan cara berikut: Pertama, temukan elemen terakhir aia_i dalam urutan sehingga ai≠n−r+ia_i \neq n - r + i.
Then, replace aia_i with ai+1a_i + 1 and aja_j with ai+j−i+1a_i + j - i + 1 for j=i+1,i+2,…,rj = i + 1, i + 2, \dots, r.
Kemudian, ganti aia_i dengan ai+1a_i + 1 dan aja_j dengan ai+j−i+1a_i + j - i + 1 untuk j=i+1,i+2,…,rj = i + 1, i + 2, \dots, r.
It is left for the reader to show that this produces the next larger rr-combination in lexicographic order.
Dibiarkan untuk pembaca menunjukkan bahwa ini menghasilkan kombinasi rr yang lebih besar berikutnya dalam urutan leksikografis.

​
Example

Find the next larger 4-combination of the set {1,2,3,4,5,6}\{1, 2, 3, 4, 5, 6\} after {1,2,5,6}\{1, 2, 5, 6\}.Solution:
The last term among the terms aia_i with a1=1,a2=2,a3=5a_1 = 1, a_2 = 2, a_3 = 5, and a4=6a_4 = 6 such that ai≠6−4+ia_i \neq 6 - 4 + i is a2=2a_2 = 2.
To obtain the next larger 4-combination, increment a2a_2 by 1 to obtain a2=3a_2 = 3.
Then set a3=3+1=4a_3 = 3 + 1 = 4 and a4=3+2=5a_4 = 3 + 2 = 5.
Hence the next larger 4-combination is {1,3,4,5}\{1, 3, 4, 5\}.

​
Algortithm Generating the Next r-Combination in Lexicographic Order

procedure next r-combination ({a1,a2,…,ar}\{a_1, a_2, \dots, a_r\} : proper subset of
        {1,2,…,n}~~~~~~~~ \{1, 2, \dots, n\} not equal to {n−r+1,…,n}\{n - r + 1, \dots, n\} with
        a1<a2<⋯<ar~~~~~~~~ a_1 < a_2 < \dots < a_r)
i:=ri := r
while ai=n−r+ia_i = n - r + i
    i:=i−1~~~~ i := i - 1
ai:=ai+1a_i := a_i + 1
for j:=i+1j := i + 1 to rr
      aj:=ai+j−i~~~~~~ a_j := a_i + j - i
{{a1,a2,…,ar}\{\{a_1, a_2, \dots, a_r\} is now the next combination}\}