Apply lexicographic permute to multiset 1223Does it generate

Apply lexicographic permute to multiset {1,2,2,3}Does it generate correctly all the permutations in lexicgraphic order.

Solution

If we apply permutation on multiset {1,2,2,3} it gives us n ! ( n r ) ! = 4! = 24 numbers

These numbers are

1223 1232 1223 1232 1322 1322 2123 2132 2213 2231 2321 2312 2213 2231 2123 2132 2312 2321 3221 3212 3221 3212 3122 3122

Now,

To do permutations lexicographic-ally on given multiset we need to follow below steps

1. Sort elements in non-decreasing order.

2. Keep generating next higher permutation until we reach a permutation where all characters are sorted in non-increasing order.

Steps to generate the next higher permutation:
1. Take permutation and find the last element. Let us call this character as ‘x’.

2. Find the ceiling of the ‘x’. Let us call the ceil character as ‘y’.

3. Swap \'x\' and \'y\'.

4. Sort the sub-string in non-decreasing order after the original index of ‘x’.

If we follow above procedure we got below lexicographic permute for multiset {1,2,2,3}

1223 1232 1322 2123 2132 2213 2231 2312 2321 3122 3212 3221

Now, if we compare both the permutation we can see that all element of \"All permutation\" is exist in \"Lexicographic permutation\"