Combinatorial Algorithms for Subset and Permutation Ranking
Combinatorial algorithms play a crucial role in computing subset and permutation rankings. These algorithms involve defining ranking functions, successor functions, lexicographic ordering on subsets, and permutation representations. The functions SUBSETLEXRANK and SUBSETLEXUNRANK are used for computing subset rank over lexicographical ordering, while the function PERMLEXRANK is employed for finding the permutation rank. These algorithms facilitate the efficient storage and generation of combinatorial objects, providing equal probabilities for random object selection from a finite set.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Combinatorial algorithms computing subset rank and unrank, Gray codes, ?-element subset rank and unrank, computing permutation rank and unrank Ji Vysko il, Radek Ma k 2012
Combinatorial Generation definition: Suppose that S is a finite set. A ranking function will be a bijection rank: ? {0, ,|?| 1} and unrank function is an inverse function to rank function. definition: Given a ranking function rank , defined on S, the successor function satisfies the following rule: successor(s) = t rank(t) = rank(s) + 1 potential uses: storing combinatorial objects in the computer instead of storing a combinatorial structure which could be quite complicated generation of random objects from S ensuring equal probability 1/|S| Advanced algorithms 2 / 22
Subsets Suppose that ? is a positive integer and ? = {1, ,?}. Define ? to consist of the 2?subsets of ?. Given a subset ? ? , let us define the characteristic vector of ? to be the one-dimensional binary array ? ? = [?? 1,?? 2, ,?0] where ??= 1 if (? ?) ? if (? ?) ? 0 Advanced algorithms 3 / 22
Subsets Example of the lexicographic ordering on subsets of ? = {1,2,3}: ? ? ? = [?2,?1,?0] ????(?) [0,0,0] 0,0,1 [0,1,0] [0,1,1] [1,0,0] 0 1 2 3 4 {3} {2} {2,3} {1} {1,3} {1,2} {1,2,3} [1,0,1] [1,1,0] [1,1,1] 5 6 7 Advanced algorithms 4 / 22
Subsets computing the subset rank over lexicographical ordering Function SUBSETLEXRANK( size n; set T ) : rank r = 0 ; for i = 1 to n do { if i T then r = r + 2n-i; } return r ; 1) 2) 3) 4) 5) 6) Function SUBSETLEXUNRANK( size n; rank r ) : set T = ; for i = n downto 1 do { if r mod 2 = 1 then T = T {i} ; r = ? div 2 ; } return T ; 1) 2) 3) 4) 5) 6) 7) Advanced algorithms 5 / 22
Permutations A permutation is a bijection from a set to itself. one possible representation of a permutation ?: 1, ,? 1, ,? is by storing its values in a one-dimensional array as follows: index value 1 2 n ?[1] ?[2] ?[n] Advanced algorithms 6 / 22
Permutations computing the permutation rank over lexicographical ordering Function PERMLEXRANK( size n; permutation ) : rank r = 0 ; = ; for j = 1 to n do { r = r + ( [ j ] 1) (n j)! ; for i = j +1 to n do if [ i ] > [ j ] then [ i ] = [ i ] 1 ; } return r ; 1) 2) 3) 4) 5) 6) 7) 8) Advanced algorithms 7 / 22
Permutations computing the permutation unrank over lexicographical ordering Function PERMLEXUNRANK( size n; rank r ) : permutation [ n ] = 1 ; for j = 1 to n 1 do { d = ? ??? ?+1 ! ?! r = r d j! ; [ n j ] = d + 1 ; for i = n j + 1 to n do if [ i ] > d then [ i ] = [ i ] + 1 ; } return ; 1) 2) 3) ; 4) 5) 6) 7) 8) 9) Advanced algorithms 8 / 22
? - Element subsets Suppose that ? is a positive integer and ? = {1, ,?}. ? ? consists of all ? ??????? ??????? of ?. A ?-element subset ? ? can be represented in a natural way as a sorted one-dimensional array ? = ?1,?2, ,?? where ?1< ?2< < ??. Advanced algorithms 9 / 22
? - Element subsets Example of the lexicographic ordering on ?-element subsets: ? ????(?) ? {1,2,3} [1,2,3] 0 {1,2,4} 1,2,4 1 {1,2,5} [1,2,5] 2 {1,3,4} [1,3,4] 3 {1,3,5} [1,3,5] 4 {1,4,5} [1,4,5] 5 {2,3,4} [2,3,4] 6 {2,3,5} [2,3,5] 7 {2,4,5} [2,4,5] 8 {3,4,5} [3,4,5] 9 Advanced algorithms 10 / 22
? - Element subsets computing the ?-element subset successor with lexicographic ordering Function KSUBSETLEXSUCCESOR(k-element subset as array T; 1) number n, k ) : k-element subset as array ; 2) U = T ; i = k ; while ( i 1 ) and ( T[i] = n k + i ) do i = i 1 ; if ( i = 0 ) then return undefined ; else { for j = i to k do U[j] = T[i] + 1 + j i ; return U ; 11) } 3) 4) 5) 6) 7) 8) 9) 10) Advanced algorithms 11 / 22
? - Element subsets computing the ?-element subset rank with lexicographic ordering Function KSUBSETLEXRANK(k-element subset as array T; number n, k ) : rank ; r = 0 ; T[0] = 0 ; for i = 1 to k do { if ( T[i 1]+1 T[i] 1 ) then { for j = T[i 1]+1 to T[i] 1 do r = r + ? ? 1) 2) 3) 4) 5) 6) ; 7) ? ? } 8) } 9) 10) return r ; Advanced algorithms 12 / 22
? - Element subsets computing the ?-element subset unrank with lexicographic ordering Function KSUBSETLEXUNRANK(rank r; 1) number n, k ) : k-element subset as array ; 2) x = 1 ; for i = 1 to k do { while ( ? ? 3) 4) r ) do { 5) ? ? ? ? ? ? r = r ; 6) x = x + 1 ; 7) } T[i] = x ; x = x + 1 ; 8) 9) 10) 11) } 12) return T ; Advanced algorithms 13 / 22
Gray Code definition: The reflected binary code, also known as Gray code, is a binary numeral system where two successive values differ in only one bit. ??will denote the reflected binary code for 2?binary n-tuples, and it will be written as a list of 2?vectors, as follows: ? ??=[?0 ?, ?1 ?, , ?2? 1 ] The codes ??are defined recursively: ?1=[0,1] ? 1 ? 1 ??=[0?0 ? 1, 0?1 ? 1, , 0?2? 1 1 ? 1, 1?0 ? 1] , ,1?1 ,1?2? 1 1 File:Binary-reflected Gray code construction.svg example: ?3=[000, 001, 011, 010, 110, 111, 101, 100] Advanced algorithms 14 / 22
Gray Code Example: binary ??3 ? representation of ? 000 001 010 011 100 101 110 111 000 001 011 010 110 111 101 100 0 1 2 3 4 5 6 7 Advanced algorithms 15 / 22
Gray Code lemma 1 Example: Suppose 0 r 2? 1 B = bn 1, , b0is a binary code of r G = gn 1, , g0is a Gray code of r Then for every j {0,1, , n 1} 10010 11100 5 ?28 28 00 = 00+01 11 = 11+02 02 = 12+13 03 = 13+14 14 = 14+05 ??= ??+ ??+1 mod 2 proof By induction on n. Note We may suppose bn = gn = 0. Advanced algorithms 16 / 22
Gray Code lemma 2 Suppose 0 r 2? 1 B = bn 1, , b0is a binary code of r G = gn 1, , g0is a Gray code of r Then for every j {0,1, , n 1} Example: 10010 11100 5 ?28 28 00 = 00+01 01 = 11+12 12 = 02+13 ??= ??+ ??+1 mod 2 proof ??= ??+ ??+1 mod 2 ?? ??+ ??+1 (mod 2) ?? ??+1 mod 2 ??= ??+ ??+1 mod 2 ??+ 13 = 03+14 14 = 14+05 Advanced algorithms 17 / 22
Gray Code lemma 3 Example: Suppose 0 r 2? 1 B = bn 1, , b0is a binary code of r G = gn 1, , g0is a Gray code of r Then for every j {0,1, , n 1} 10010 11100 5 ?28 28 00 = 00+11+02+03+14 01 = 11+02+03+14 12 = 02+03+14 13 = 03+14 14 = 14 ? 1 ??= ?? mod 2 ?=? proof ? 1 ? 1 ? 1 ?? mod 2 = (??+??+1) mod 2 = ??+ ??+ 2 ?? mod 2 = (??+??) mod 2 = ?? ?=? ?=? ?=?+1 By lemma 1. By the sum reordering. By the property of modulo. By the maximum range of r and the range of bj. Advanced algorithms 18 / 22
Gray Code converting to and from minimal change ordering (Gray code) Function BINARYTOGRAY( binary code rank B ) : gray code rank returnB xor(B >> 1) ; 1) 2) Function GRAYTOBINARY(gray code rank G ) : binary code rank B = 0; n = (number of bits in G) 1; for i=0 tondo { B = B<< 1; B = Bor (1 and ( (B >> 1) xor (G>>n) ) ); G = G<< 1; } return B ; 1) 2) 3) 4) 5) 6) 7) 8) 9) Advanced algorithms 19 / 22
Subsets Gray Code computing the subset rank over minimal change ordering Function GRAYCODERANK( size n; set T ) : rank r = 0 ; b = 0 ; fori = n 1 downto 0 do{ if n i T then b = 1 b ; if b = 1 then r = r +2i ; } returnr ; 1) 2) 3) 4) 5) 6) 7) 8) Advanced algorithms 20 / 22
Subsets Gray Code computing the subset unrank over minimal change ordering Function GRAYCODEUNRANK( size n; rank r ) : set T = ; c = 0 ; for i = n 1 downto 0 do{ b = ? div 2? ; if b c then T = T {n i} ; c = b ; r = r b 2i ; } 10) returnT ; 1) 2) 3) 4) 5) 6) 7) 8) 9) Advanced algorithms 21 / 22
References D.L. Kreher and D.R. Stinson , Combinatorial Algorithms: Generation, Enumeration and Search , CRC press LTC , Boca Raton, Florida, 1998. Advanced algorithms 22 / 22
