Rang einer Permutation

Dieses Problem kann leicht gelöst werden, indem man es zuerst vereinfacht und rekursiv denkt.

Nehmen wir also zunächst an, dass alle Elemente in der Eingabesequenz eindeutig sind, dann ist die Menge der "eindeutigen" Permutationen einfach die Menge der Permutationen.

Um nun den Rang der Sequenz a_1, a_2, a_3, ..., a_nin ihren Permutationssätzen zu finden, können wir:

1. Sortieren Sie die Reihenfolge, um zu erhalten b_1, b_2, ..., b_n. Diese Permutation hat per Definition Rang 0.

2. Jetzt vergleichen wir a_1und b_1. Wenn sie gleich sind, können wir sie einfach aus dem Problem entfernen: Der Rang von a_1, a_2, ..., a_nwird der gleiche sein wie der Rang von gerecht a_2, ..., a_n.

3. Andernfalls b_1 < a_1werden dann alle Permutationen, die mit beginnen b_1, kleiner als sein a_1, a_2, ..., a_n. Die Anzahl solcher Permutationen ist einfach zu berechnen, es ist einfach (n-1)! = (n-1)*(n-2)*(n-3)*...*1.

   Aber dann können wir unsere Sequenz weiter betrachten b_1, ..., b_n. Wenn ja b_2 < a_1, sind wieder alle Permutationen, die mit beginnen b_2, kleiner. Also sollten wir (n-1)!unseren Rang noch einmal erhöhen.

   Wir tun dies, bis wir einen Index finden, jwo b_j == a_j, und dann landen wir bei Punkt 2.

Dies kann ganz einfach implementiert werden:

import math

def permutation_rank(seq):
    ref = sorted(seq)
    if ref == seq:
        return 0
    else:
        rank = 0
        f = math.factorial(len(seq)-1)
        for x in ref:
            if x < seq[0]:
                rank += f
            else:
                rank += permutation_rank(seq[1:]) if seq[1:] else 0
                return rank

Die Lösung ist ziemlich schnell:

In [24]: import string
    ...: import random
    ...: seq = list(string.ascii_lowercase)
    ...: random.shuffle(seq)
    ...: print(*seq)
    ...: print(permutation_rank(seq))
    ...: 
r q n c d w s k a z b e m g u f i o l t j x p h y v
273956214557578232851005079

Zum Thema gleiche Elemente: Der Punkt, an dem sie ins Spiel kommen, (n-1)!ist die Anzahl der Permutationen, wobei jedes Element als von den anderen verschieden betrachtet wird. Wenn Sie eine Längenfolge naus Symbol s_1, ..., s_kund Symbol haben, s_jdie c_jmal angezeigt wird, beträgt die Anzahl der eindeutigen Permutationen `(n-1)! / (c_1! * c_2! * ... * c_k!).

Dies bedeutet, dass (n-1)!wir es nicht nur addieren , sondern durch diese Zahl dividieren müssen, und dass wir auch die Anzahl c_tder aktuellen Symbole, die wir in Betracht ziehen , um eins verringern möchten .

Dies kann folgendermaßen geschehen:

import math
from collections import Counter
from functools import reduce
from operator import mul

def permutation_rank(seq):
    ref = sorted(seq)
    counts = Counter(ref)

    if ref == seq:
        return 0
    else:
        rank = 0
        f = math.factorial(len(seq)-1)
        for x in sorted(set(ref)):
            if x < seq[0]:
                counts_copy = counts.copy()
                counts_copy[x] -= 1
                rank += f//(reduce(mul, (math.factorial(c) for c in counts_copy.values()), 1))
            else:
                rank += permutation_rank(seq[1:]) if seq[1:] else 0
                return rank

Ich bin mir ziemlich sicher, dass es eine Möglichkeit gibt, das Kopieren des Zählwörterbuchs zu vermeiden, aber im Moment bin ich müde, also lasse ich das als Übung für den Leser.

Als Referenz das Endergebnis:

In [44]: for i,x in enumerate(sorted(set(it.permutations('aabc')))):
    ...:     print(i, x, permutation_rank(x))
    ...:     
0 ('a', 'a', 'b', 'c') 0
1 ('a', 'a', 'c', 'b') 1
2 ('a', 'b', 'a', 'c') 2
3 ('a', 'b', 'c', 'a') 3
4 ('a', 'c', 'a', 'b') 4
5 ('a', 'c', 'b', 'a') 5
6 ('b', 'a', 'a', 'c') 6
7 ('b', 'a', 'c', 'a') 7
8 ('b', 'c', 'a', 'a') 8
9 ('c', 'a', 'a', 'b') 9
10 ('c', 'a', 'b', 'a') 10
11 ('c', 'b', 'a', 'a') 11

Und um zu zeigen, dass es effizient ist:

In [45]: permutation_rank('zuibibzboofpaoibpaybfyab')
Out[45]: 246218968687554178