Make a LexicographicPermute algorithm to generate permutations and apply this algorithm to multiset {1, 2, 2, 3}. 

Does it generate correctly all the permutations in lexicographic order?

 

LexicographicPermute to multiset {1, 2, 2, 3}

Given a sequence of n elements a₀ , a₁ , ......... a_n-1 generate all permutations of the sequence in lexicographically correct order. 

Step 1:

Partition the sequence into two sequences a₀ , a₁ , ......... a_j and a_j , a_j+1 , ......... a_n-1 such that we have already generated all permutations beginning with a₀ , a₁ , ......... a_j . This can by done by decreasing j from n-2 until ?aj?<aj+1?? . If j = 0 we are done. 

For example, the input sequence 1, 2, 2, 3 is split into the sequence 1 and the sequence 2, 2, 3. Obviously, there are no more lexicographic permutations beginning with 1 when the second sequence is in decreasing order. 

Step 2a:

In the second sequence a_j , a_j+1 , ......... a_n-1 working backwards, find a_m, the first value larger than a_j.

We find a_m by setting m to N -1 and decreasing until ?aj?<am??

Step 2b:

Swap ?aj?andam??

For example, our two sequences are 1 and 2, 2, 3. As the second sequence is decreasing because of the first step, am is the smallest element greater than y that can legitimately follow a₀ , a₁ , ......... a_j in a permutation. 

Step 3:

Reverse a_j , a_j+1 , ......... a_n-1

Here are some examples on the sequence (1, 2, 2, 3):

(1, 2, 2, 3) >> (1, 2, 2), (3) >> (1, 2, 3), (2) >> (1, 2, 3), (2) >> (1, 2, 3, 2)

(1, 2, 3, 2) >> (1, 2), (3, 2) >> (1, 3), (2, 2) >> (1, 3), (2, 2) >> (1, 3, 2, 2)

(1, 3, 2, 2) >> (1), (3, 2, 2) >> (2), (3, 2, 1) >> (2), (1, 2, 3) >> (2, 1, 2, 3) 

Total sequences is

[1, 2, 2, 3]

[1, 2, 3, 2]

[1, 3, 2, 2]

[2, 1, 2, 3]

[2, 1, 3, 2]

[2, 2, 1, 3]

[2, 2, 3, 1]

[2, 3, 1, 2]

[2, 3, 2, 1]

[3, 1, 2, 2]

[3, 2, 1, 2]

[3, 2, 2, 1]