Finden der (lexikographische) index, der eine permutation von einer gegebenen array.

Betrachten wir die permutation dacb. Wo kommt das in der lexikographischen Ordnung unter der 4! = 24 Permutationen von abcd?

• Betrachten Sie die ersten Buchstaben d. Unter den restlichen Buchstaben (acb) es sind drei Buchstaben, die kleiner als d und 3! = 6 Permutationen beginnen mit jedem von Ihnen, für eine Gesamtmenge von 18 Permutationen.
• Betrachten Sie die ersten beiden Buchstaben da. Unter den restlichen Buchstaben (cb) es gibt keine Buchstaben, die kleiner als a (wenn es welche gab, es wären 2! = 2 Permutationen beginnend mit d sowie jeweils eins), für eine Gesamtmenge von 0 Permutationen.
• Betrachten Sie die ersten drei Buchstaben dac. Unter den restlichen Buchstaben (b) es ist ein Buchstabe kleiner als c, und 1! = 1 Permutationen beginnend mit dab, für eine Gesamtmenge von 1 permutation.

Also insgesamt gibt es 19 Permutationen kleiner als dacb. Lassen Sie uns überprüfen.

>>> 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')]

Sieht gut aus. So gibt es 4! − 19 − 1 = 4 die Permutationen, die größer sind als dacb.

Sollte es nun verständlich sein, wie die Verallgemeinerung der Methode, um ein Algorithmus. Hier ist eine Implementierung 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

Hier ist die Backtracking-Lösung:

Programm permutates alle Lösungen für die gegebene Zeichenkette und gibt es eine Liste von Lösungen, sowie wie viele hier sind.

Ex:
für acb es gibt:

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;
}