-->

Tuesday, May 7, 2013

Lehmer Code

In mathematics and in particular in combinatorics, the Lehmer code is a particular way to encode each possible permutation of a sequence of n numbers. It is an instance of a scheme for numbering permutations and is an example of an inversion table.

The code

The Lehmer code makes evident the fact that there are
n!=n\times(n-1)\times\cdots\times2\times1
permutations of a sequence of n numbers. If a permutation σ is specified by the sequence (σ1, …, σn) of its images of 1, …, n, then it is encoded by a sequence of n numbers, but not all such sequences are valid since every number must be used only once. By contrast the encodings considered here choose the first number from a set of n values, the next number from a fixed set of n − 1 values, and so forth decreasing the number of possibilities until the last number for which only a single fixed value is allowed; every sequence of numbers chosen from these sets encodes a single permutation. While several encodings can be defined, the Lehmer code has several additional useful properties; it is the sequence
L(\sigma)=(L(\sigma)_1,\ldots,L(\sigma)_n)\quad\text{where}\quad L(\sigma)_i=\#\{ j>i : \sigma_j<\sigma_i \},
in other words the term L(σ)i counts the number of terms in (σ1, …, σn) to the right of σi that are smaller than it, a number between 0 and n − i, allowing for n + 1 − i different values.
A pair of indices (i,j) with i < j and σi > σj is called an inversion of σ, and L(σ)i counts the number of inversions (i,j) with i fixed and varying j. It follows that L(σ)1 + L(σ)2 + … + L(σ)n is the total number of inversions of σ, which is also the number of adjacent transpositions that are needed to transform the permutation into the identity permutation. Other properties of the Lehmer code include that the lexicographical order of the encodings of two permutations is the same as that of their sequences (σ1, …, σn), that any value 0 in the code represents a right-to-left minimum in the permutation (i.e., a σi smaller than any σj to its right), and a value n − i at position i similarly signifies a right-to-left maximum, and that the Lehmer code of σ coincides with the factorial number system representation of its position in the list of permutations of n in lexicographical order (numbering the positions starting from 0).
Variations of this encoding can be obtained by counting inversions (i,j) for fixed j rather than fixed i, by counting inversions with a fixed smaller value σj rather than smaller index i, or by counting non-inversions rather than inversions; while this does not produce a fundamentally different type of encoding, some properties of the encoding will change correspondingly. In particular counting inversions with a fixed smaller value σj gives the inversion table of σ, which can be seen to be the Lehmer code of the inverse permutation.

Encoding and decoding

The usual way to prove that there are n! different permutations of n objects is to observe that the first object can be chosen in n different ways, the next object in n − 1 different ways (because choosing the same number as the first is forbidden), the next in n − 2 different ways (because there are now 2 forbidden values), and so forth. Translating this freedom of choice at each step into a number, one obtains an encoding algorithm, one that finds the Lehmer code of a given permutation. One need not suppose the objects permuted to be numbers, but one needs a total ordering of the set of objects. Since the code numbers are to start from 0, the appropriate number to encode each object σi by is the number of objects that were available at that point (so they do not occur before position i), but which are smaller than the object σi actually chosen. (Inevitably such objects must appear at some position j > i, and (i,j) will be an inversion, which shows that this number is indeed L(σ)i.)
This number to encode each object can be found by direct counting, in several ways (directly counting inversions, or correcting the total number of objects smaller than a given one, which is its sequence number starting from 0 in the set, by those that are unavailable at its position). Another method which is in-place, but not really more efficient, is to start with the permutation of {0, 1, … n − 1} obtained by representing each object by its mentioned sequence number, and then for each entry x, in order from left to right, correct the items to its right by subtracting 1 from all entries (still) greater than x (to reflect the fact that the object corresponding to x is no longer available). Concretely a Lehmer code for the permutation B,F,A,G,D,E,C of letters, ordered alphabetically, would first give the list of sequence numbers 1,5,0,6,3,4,2, which is successively transformed
\begin{matrix} \mathbf1&5&0&6&3&4&2\\ 1&\mathbf4&0&5&2&3&1\\ 1&4&\mathbf0&4&2&3&1\\ 1&4&0&\mathbf3&1&2&0\\ 1&4&0&3&\mathbf1&2&0\\ 1&4&0&3&1&\mathbf1&0\\ 1&4&0&3&1&1&\mathbf0\\ \end{matrix}
where the final line is the Lehmer code (at each line one subtracts 1 from the larger entries to the right of the boldface element to form the next line).
For decoding a Lehmer code into a permutation of a given set, the latter procedure may be reversed: for each entry x, in order from right to left, correct the items to its right by adding 1 to all those (currently) greater than or equal to x; finally interpret the resulting permutation of {0, 1, … n − 1} as sequence numbers (which amounts to adding 1 to each entry if a permutation of {1, 2, … n} is sought). Alternatively the entries of the Lehmer code can be processed from left to right, and interpreted as a number determining the next choice of an element as indicated above; this requires maintaining a list of available elements, from which each chosen element is removed. In the example this would mean choosing element 1 from {A,B,C,D,E,F,G} (which is B) then element 4 from {A,C,D,E,F,G} (which is F), then element 0 from {A,C,D,E,G} (giving A) and so on, reconstructing the sequence B,F,A,G,D,E,C.

Applications to combinatorics and probabilities

Independence of relative ranks

The Lehmer code defines a bijection from the symmetric group Sn to the Cartesian product [n]\times[n-1]\times\cdots\times[2]\times[1], where [k] designates the k-element set \{0,1,\ldots,k-1\}. As a consequence, under the uniform law on the Sn, the component L(σ)i defines a uniformly distributed random variable on [n + 1 − i], and these random variables are mutually independent, because they are projections on different factors of a Cartesian product.

Number of right-to-left minima and maxima

Definition : In a sequence u=(uk)1≤k≤n, there is right-to-left minimum (resp. maximum) at rank k if uk is strictly smaller (resp. strictly bigger) than each element ui with i>k, i.e., to its right.
Let B(k) (resp. H(k)) be the event "there is right-to-left minimum (resp. maximum) at rank k", i.e. B(k) is the set of the permutations \scriptstyle\ \mathfrak{S}_n\ which exhibit a right-to-left minimum (resp. maximum) at rank k. We clearly have
\{\omega\in B(k)\}\Leftrightarrow\{L(k,\omega)=1\}\quad\text{and}\quad\{\omega\in H(k)\}\Leftrightarrow\{L(k,\omega)=k\}.
Thus the number Nb(ω) (resp. Nh(ω)) of right-to-left minimum (resp. maximum) for the permutation ω can be written as a sum of independent Bernoulli random variables each with a respective parameter of 1/k :
N_b(\omega)=\sum_{1\le k\le n}\ 1\!\!1_{B(k)}\quad\text{and}\quad N_b(\omega)=\sum_{1\le k\le n}\ 1\!\!1_{H(k)}.
Indeed, as L(k) follows the uniform law on \scriptstyle\ [\![1,k]\!],\
\mathbb{P}(B(k))=\mathbb{P}(L(k)=1)=\mathbb{P}(H(k))=\mathbb{P}(L(k)=k)=\tfrac1k.
The generating function for the Bernoulli random variable 1\!\!1_{B(k)} is
G_k(s)=\frac{k-1+s}k,
therefore the generating function of Nb is
G(s)=\prod_{k=1}^nG_k(s)\ =\ \frac{(s)_{\uparrow n}}{n!},
which allow us to find again the product form for the generative series of the Stirling numbers of the first kind (unsigned).

The secretary problem

This is an optimal stop problem, a classic in decision theory, statistics and applied probabilities, where a random permutation is gradually revealed through the first elements of its Lehmer code, and where the goal is to stop exactly at the element k such as σ(k)=n, whereas the only available information (the k first values of the Lehmer code) is not sufficient to compute σ(k).
In less mathematical words : a series of n applicants are interviewed one after the other. The interviewer must hire the best applicant, but must make his decision (“Hire” or “Not hire”) on the spot, without interviewing the next applicant ( and a fortiori without interviewing all applicants).
The interviewer thus knows the rank of the kth applicant, therefore, at the moment of making his kth decision, the interviewer knows only the k first elements of the Lehmer code whereas he would need to know all of them to make a well informed decision. To determine the optimal strategies (i.e. the strategy maximizing the probability of a win), the statistical properties of the Lehmer code are crucial.
Allegedly, Johannes Kepler clearly exposed this secretary problem to a friend of his at a time when he was trying to make up his mind and choose one out eleven prospective brides as his second wife. His first marriage had been an unhappy one, having been arranged without himself being consulted, and he was thus very concerned that he could reach the right decision.

Posted by at No comments:
Labels:

What Is Encoding permutations as integers via the Lehmer code

Permutations
A permutation of an array is an array that contains the same elements, but possibly in a different order. For example, given the array
    [ 'a', 'b', 'c' ]
All of its permutations are:
    [ 'a', 'b', 'c' ]
    [ 'a', 'c', 'b' ]
    [ 'b', 'a', 'c' ]
    [ 'b', 'c', 'a' ]
    [ 'c', 'a', 'b' ]
    [ 'c', 'b', 'a' ]

Computing a permutation: a naive solution
In order to motivate the Lehmer code, let’s first implement a naive algorithm for computing a permutation of an array. Given the following array arr.
    var arr = [ 'a', 'b', 'c' ];
A simple way of computing a random permutation of arr is:
  • Compute a random number i, 0 ≤ i < 3. arr[i] is the first element of the permutation. Remove element i from arr.
  • Compute a random number i, 0 ≤ i < 2. arr[i] is the second element of the permutation. Remove element i from arr.
  • The remaining element of arr is the last element of the permutation.
In order to implement the above algorithm, we need a function to compute a random integer in a range starting at 0, up to and excluding an upper bound upper. The following function performs that duty.
    /**
     * @returns a number 0 <= n < upper
     */
    function getRandomInteger(upper) {
        return Math.floor(Math.random() * upper);
    }
Furthermore, we don’t want to change the input array arr, which means that we need a function that non-destructively removes an element:
    /**
     * @returns a fresh copy of arr, with the element at index removed
     */
    function removeElement(arr, index) {
        return arr.slice(0, index).concat(arr.slice(index+1));
    }
The algorithm itself looks as follows:
    function createPermutation(arr) {
        if (arr.length === 0) {
            return [];
        }
        var index = getRandomInteger(arr.length);
        return [arr[index]].concat(
            createPermutation(
                removeElement(arr, index)));
    }
Interaction:
    > createPermutation([ 'a', 'b', 'c' ])
    [ 'a', 'c', 'b' ]
Note: createPermutation() could be implemented more efficiently, but the current implementation expresses our intentions very clearly.

Encoding permutations as integers
An alternative to the above algorithm is to find a way to map single integers to permutations. We can then simply compute a random integer and map it to a permutation.

The naive algorithm in two steps
As a first step towards this new approach, lets first split up the previous algorithm into two steps:
  1. Compute the indices for the (continually shrinking) array arr.
  2. Turn the indices into a permutation.
The following function performs step 1. We don’t need to know anything about arr, except for its length len. The first index of the returned array is in the range [0,len), the second in the range [0,len−1), etc.
    function createLehmerCode(len) {
        var result = [];
        for(var i=len; i>0; i--) {
            result.push(getRandomInteger(i));
        }
        return result;
    }
Interaction:
    > createLehmerCode(3)
    [ 0, 1, 0 ]
The above way of encoding a permutation as a sequence of numbers is called a Lehmer code. Such a code can easily be converted into a permutation, via the following function (step 2):
    function codeToPermutation(elements, code) {
        return code.map(function (index) {
            var elem = elements[index];
            elements = removeElement(elements, index);
            return elem;
        });
    }
Interaction:
    > codeToPermutation(['a','b','c'], [0,0,0])
    [ 'a', 'b', 'c' ]
    > codeToPermutation(['a','b','c'], [2,1,0])
    [ 'c', 'b', 'a' ]

Mapping integers to Lehmer codes
The next step is to replace create LehmerCode() by a function that maps an integer to a Lehmer code. Afterwards, we compute that integer randomly and not the code itself, any more. To that end, lets look at ways of encoding sequences of digits (e.g. indices) as single integers. If each of the digits has the same range, we can use a positional systemwhose radix is the (excluded) upper bound of the range.
The decimal system. For example, if each digit is in the range 0–9 then we can use the fixed radix 10 and the decimal system. That is, each digit has the same radix. “Radix” is just another way of saying “upper bound of a digit”. The following table reminds us of the decimal system.
Digit position
2
1
0
Digit range
0–9
0–9
0–9
Multiplier
100 = 102
10 = 101
1 = 100
Radix
10
10
10
The value of a position is the value of the digit multiplied by the multiplier. The value of a complete decimal number is the sum of the values of the positions.
Note that each multiplier is one plus the sum of all previous highest digits multiplied by their multipliers. For example:
100 = 1 + (9x10 + 9x1)
The factoradicsystem.Encoding the digits of a Lehmer code into an integer is more complex, because each digit has a different radix. We want the mapping to be bijective (a one-to-one mapping without “holes”). The factoradic system is what we need, as explained via the following table. The digit ranges reflect the rules of the Lehmer code.
Digit position
3
2
1
0
Digit range
0–3
0–2
0–1
0
Multiplier
6 = 3!
2 = 2!
1 = 1!
1 = 0!
Radix
4
3
2
1
The last digit is always zero and often omitted. Again, a multiplier is one plus the highest value that you can achive via previous positions. For example:
6 = 1 + (2x2 + 1x1 + 0x1)
The following function performs the mapping from integers to Lehmer codes.
    function integerToCode(int, permSize) {
        if (permSize <= 1) {
            return [0];
        }
        var multiplier = factorial(permSize-1);
        var digit = Math.floor(int / multiplier);
        return [digit].concat(
            integerToCode(
                int % multiplier,
                permSize-1));
    }
We start with the highest position. Its digit can be determined by dividing int by the position’s multiplier. Afterwards the remainder of that division becomes the new intand we continue with the next position.
integerToCode() uses the following function to compute the factorial of a number:
    function factorial(n) {
        if (n <= 0) {
            return 1;
        } else {
            return n * factorial(n-1);
        }
    }

Putting everything together
We now have all the pieces to compute a permutation as originally planned:
    function createPermutation(arr) {
        var int = getRandomInteger(factorial(arr.length));
        var code = integerToCode(int);
        return codeToPermutation(arr, code);
    }
The range of the random integer representing a permutation is [0,arr.length). That is an indication that the mapping between integers and permutations is really bijective, because arrhas arr.length! permutations,

Practically useful?
Is the Lehmer code practically useful? It is if you need to encode permutations as integers. There are two additional use cases for it: Computing a random permutation and enumerating all permutations. For both use cases, Lehmer codes give you convenient solutions, but not efficient ones. If you want efficiency, consider the following two algorithms:
Posted by at No comments:
Labels: ,

Friday, April 19, 2013

My Profil



Sebuah kata merupakan ungkapan hati, bermakna dan menjadi suatu hal yang penting dari tata bahasa. Sebuah kata disusun dari beberapa huruf dan dari banyak kata tersebut dapat dirangkai menjadi suatu kalimat yang indah.

Nama saya Sariman. Dahulu Saya adalah seorang bayi nan imut yang dianugerahkan kepada Mama dan Papa saya. Saya dilahirkan di Lubuk Pakam, tepatnya pada tanggal 15 Desember 1989. Saya anak pertama. Sejak kecil sampai dengan saat ini, saya tinggal bersama dengan kedua orang tua saya. Saya terkesan orang yang pendiam. Namun saya perduli terhadap lingkungan disekitar saya. Sekarang Saya sudah berumah tangga dan saya ingin sekali membahagiakan kedua orang tua saya serta isteri saya. 

Saya sangat suka dengan Mie ayam, Mie Rebus, Cokelat dan Es krim. Saya juga senang berjalan-jalan, mendengarkan musik yang bergenre Melankolis serta mencari pengalaman baru bersama teman-teman baru. 
O Iya Saya juga suka bermain musik lo? Musik yang Saya Mainkan kebanyakkan Piano dan Gitar.
Bagi kalian yang ingin mengenal saya lebih mendalam, mari kita berteman :)
Posted by at No comments:
Labels:

Cara membuat Foto berjalan

Foto Yang berjalan di blog memang sangat menarik untuk dilihat . bagaimana cara membuatnya ? yupz.. Dalam postingan kali ini saya akan menerangkan bagaimana cara membuat foto berjalan di blog . Sama seperti teks yang berjalan gambar yang berjalan ini juga menggunakan efek dari marquee . langsung ajah yach kita praktek .hehehehe
Ikuti langkah-langkah berikut untuk membuat gambar berjalan di blog

Copy Paste kode berikut ke blog anda :

<table border="10" cellpadding="3" height="135" width="195"/>
<tr>
<td>
<marquee onmouseover="this.stop()" onmouseout="this.start()" scrollamount="2" direction="up" width="192" height="132" align="center">

<img src="http://farm5.static.flickr.com/4017/4274096032_8bf5bd349a_o.jpg" height="130" width="190" />
<br/>
<img src="http://farm5.static.flickr.com/4046/4273351371_7c1ceb936b_o.jpg" height="130" width="190" />

</marquee>
</td>
</tr>
</table>

Hasilnya Adalah sebagai berikut :








Keterangan ganti link yang berwarna biru dengan link tempat anda menaruh gambar, contohnya saja gambar yang anda taro di flickr.com .


Membuat Gambar berjaln Dari kiri ke kanan

Copy paste kode berikut ke blog anda :
<marquee align="center" direction="left" height="200" scrollamount="3" width="100%" >

<img src="http://farm5.static.flickr.com/4017/4274096032_8bf5bd349a_o.jpg" width="190" height="130" />

</marquee>

Hasilnya Adalah sebagai berikut :



Selamat mencoba.......
Posted by at No comments:
Labels:

Cara Buat Link Download

Apa Itu link download ? Link download adalah seuatu teks atau gambar yang bisa di klik untuk mengarahkan link ke sebuah hosting untuk mendownload sebuah file . Bagaimana Cara membuatnya ? caranya begini Copy kode berikut lalu paste di blog kalian :
<a href="http://www.klinik-it.blogspot.com">Download</a>

Keterangan : Teks yang berwarna biru adalah Link tujuan ketika teks Yang berwarna Merah Di Klik . Teks Yang Berwarna merah juga Bisa anda ganti Dengan kata lain misalnya saja "Klik Disini"Ataupun yang lainya !

Ada banyak Fariasi untuk membuat link download,diantarannya dengan cara membuat linknya berhuruf besar,Miring tebal atau dengan menggunakan gambar . Contohnya sebagaiberikut :

Copy paste kode berikut untuk membuat teks link download menjadi tebal :
<a href="klinik-it.blogspot.com"><b>Download</b></a>

Untuk membuat teks tersebut miring silakan ganti kode <b>dan</b> Dengan <i>dan</i> .

Dan untuk membuat link tersebut Berukuran kecil sampe besar ganti kode yang saya hijaukan dengan kode <h1> dan </h1> . ganti angka tersebut dengan angka 1 - 6 jika ingin menyesuaikan ukuran besar link .

Cara Selanjutnya adalah membuat link download dengan gambar/ikon
Caranya copy paste kode berikut ke blog anda :

<a href="http://www.klinik-it.blogspot.com" title="Download"><img src="http://farm5.static.flickr.com/4042/4278913170_e7973277d8_o.png" width="216" height="74" alt="download[4]" /></a>

Hasilnya adalah sebagi berikut :



Keterangan Ganti Link yang berwarna biru dengan Full link Hosting tujuan anda .

Selamat Mencoba ..........?
Posted by at No comments:
Labels:
Subscribe to: Posts (Atom)