Given an array say "bca", I need to find the number of permutations which are lexicographicaly greater than the given permutation.
Thus, in this example, cab, cba are permutations which are greater. Thus the answer would be 2.
I tried approaching the problem by finding the lexicographic ranking of the array, but am not able to devise an efficient algorithm for the say.
Any help/pointers in the right direction is appreciated!
Let's look at the permutation dacb. Where does this come in lexicographic order among the 4! = 24 permutations of abcd?
d. Among the remaining letters (acb) there are three letters smaller than d, and 3! = 6 permutations starting with each one of them, for a total of 18 permutations.da. Among the remaining letters (cb) there are no letters smaller than a (if there were any there would be 2! = 2 permutations starting with d plus each one), for a total of 0 permutations.dac. Among the remaining letters (b) there is one letter smaller than c, and 1! = 1 permutations starting with dab, for a total of 1 permutation.So in total there are 19 permutations smaller than dacb. Let's check that.
>>> from itertools import permutations
>>> list(enumerate(''.join(p) for p in permutations('abcd')))
[(0, 'abcd'), (1, 'abdc'), (2, 'acbd'), (3, 'acdb'),
(4, 'adbc'), (5, 'adcb'), (6, 'bacd'), (7, 'badc'),
(8, 'bcad'), (9, 'bcda'), (10, 'bdac'), (11, 'bdca'),
(12, 'cabd'), (13, 'cadb'), (14, 'cbad'), (15, 'cbda'),
(16, 'cdab'), (17, 'cdba'), (18, 'dabc'), (19, 'dacb'),
(20, 'dbac'), (21, 'dbca'), (22, 'dcab'), (23, 'dcba')]
Looks good. So there are 4! − 19 − 1 = 4 permutations that are greater than dacb.
It should be clear now how to generalize the method to make an algorithm. Here's an implementation in Python:
from math import factorial
def lexicographic_index(p):
"""
Return the lexicographic index of the permutation `p` among all
permutations of its elements. `p` must be a sequence and all elements
of `p` must be distinct.
>>> lexicographic_index('dacb')
19
>>> from itertools import permutations
>>> all(lexicographic_index(p) == i
... for i, p in enumerate(permutations('abcde')))
True
"""
result = 0
for j in range(len(p)):
k = sum(1 for i in p[j + 1:] if i < p[j])
result += k * factorial(len(p) - j - 1)
return result
def lexicographic_followers(p):
"""
Return the number of permutations of `p` that are greater than `p`
in lexicographic order. `p` must be a sequence and all elements
of `p` must be distinct.
"""
return factorial(len(p)) - lexicographic_index(p) - 1
There is a very clean way to do this based on the factorial number system and Lehmer codes. The idea is to assign a numeric code to each possible permutation that encodes the order in which the values occur (the Lehmer code). You can then convert the Lehmer code into a number that determines the index of the permutation in the list of all permutations (this uses the factorial number system). Given the index of the permutation, you can then compute (n! - 1) and subtract out the index to determine how many more permutations there are.
If you're curious how to do this, I have an implementation of this algorithm that lets you map from permutations to indices or vice-versa. I also gave a talk on how to do this; the details are in the latter half of the slides.
Hope this helps!
Here is the Backtracking solution:
The program permutates all the solutions for the given string and it returns a list of solutions as well as how many here are.
Ex:
for acb it returns:
c a b
c b a
b a c
b c a
4
Code:
#include <iostream>
#include <stdio>
using namespace std;
int v[100], n, cnt;
char *str;
void init(int k)
{
v[k] = -1;
}
bool solutionReached( int k )
{
if (k == n + 1)
return true;
return false;
}
void printSolution( int k )
{
for (int i = 1; i < k; i++)
{
printf("%c ", str[v[i]]);
}
printf("\n");
cnt++;
}
bool hasSuccesor( int k )
{
if(v[k] < n - 1)
{
v[k]++;
return true;
}
return false;
}
bool isValid( int k )
{
for (int i = 1; i < k; i++)
{
if (v[i] == v[k])
{
return false;
}
}
if (k == n)
{
char *cuv = (char *) malloc(n * sizeof(char));
for (i = 0; i < n; i++)
cuv[i] = str[v[i + 1]];
if (strcmp(cuv, str) > 0)
{
return true;
}
else
return false;
}
return true;
}
void bkt(int k)
{
if(solutionReached(k))
printSolution(k);
else
{
init(k);
while(hasSuccesor(k))
if(isValid(k))
bkt(k + 1);
}
}
int main(int argc, char* argv[])
{
str = "bca";
n = strlen(str);
bkt(1);
printf("%i \n", --cnt);
return 0;
}
Straight-forward python solution relies on the fact that Pythons permutation generator will generate in lexicographic order from an initial sorted string.
In [68]: from itertools import permutations
In [69]: from math import factorial
In [70]: def lexigreaterperms(perm):
...: return factorial(len(perm)) - 1 - list(permutations(sorted(perm))).index(tuple(perm))
In [71]: lexigreaterperms('bca')
Out[71]: 2
In [72]: lexigreaterperms('dacb')
Out[72]: 4
