Aby opisać permutację n elementów, widzisz, że dla pozycji, na której kończy się pierwszy element, masz n możliwości, więc możesz to opisać liczbą od 0 do n-1. Dla pozycji, na której kończy się następny element, masz jeszcze n-1 możliwości, więc możesz to opisać liczbą od 0 do n-2.
Et cetera, dopóki nie masz n liczb.
Jako przykład dla n = 5, rozważ permutację, która prowadzi abcdedo caebd.
a, pierwszy element, kończy się na drugiej pozycji, więc przypisujemy mu indeks 1 .bkończy na czwartej pozycji, która byłaby indeksem 3, ale jest to trzecia pozostała pozycja, więc przypisujemy jej 2 .ckończy się na pierwszej pozostałej pozycji, która zawsze wynosi 0 .dkończy na ostatniej pozostającej pozycji, która (z tylko dwóch pozostałych pozycji) wynosi 1 .ekończy się na jedynej pozostałej pozycji, indeksowanej na 0 .
Mamy więc sekwencję indeksów {1, 2, 0, 1, 0} .
Teraz wiesz, że na przykład w liczbie binarnej „xyz” oznacza z + 2y + 4x. Dla liczby dziesiętnej
jest to z + 10y + 100x. Każda cyfra jest mnożona przez jakąś wagę, a wyniki są sumowane. Oczywistym wzorem w wadze jest oczywiście to, że waga wynosi w = b ^ k, gdzie b jest podstawą liczby, a k jest indeksem cyfry. (Zawsze będę liczył cyfry od prawej strony i zaczynając od indeksu 0 dla najbardziej prawej cyfry. Podobnie, gdy mówię o „pierwszej” cyfrze, mam na myśli skrajną prawą cyfrę.)
Powód dlaczego ciężary dla cyfr śledzić tego wzoru jest to, że największa liczba, które mogą być reprezentowane przez cyfry od 0 do k musi być dokładnie 1 niższy od najniższego numeru, który może być reprezentowany przez tylko za pomocą cyfr k + 1. W systemie dwójkowym 0111 musi być o jeden mniejszy niż 1000. W systemie dziesiętnym 099999 musi być o jeden mniejszy niż 100000.
Kodowanie do zmiennej o podstawie
Odstępy między kolejnymi liczbami wynoszące dokładnie 1 to ważna zasada. Zdając sobie z tego sprawę, możemy przedstawić naszą sekwencję indeksów za pomocą liczby o zmiennej podstawie . Podstawą dla każdej cyfry jest ilość różnych możliwości dla tej cyfry. Dla ułamka dziesiętnego każda cyfra ma 10 możliwości, w naszym systemie cyfra po prawej stronie miałaby 1 możliwość, a cyfra po lewej stronie miałaby n możliwości. Ale ponieważ skrajna prawa cyfra (ostatnia liczba w naszej sekwencji) zawsze wynosi 0, pomijamy ją. Oznacza to, że mamy podstawy od 2 do n. Ogólnie k-ta cyfra będzie miała podstawę b [k] = k + 2. Najwyższą dopuszczalną wartością dla cyfry k jest h [k] = b [k] - 1 = k + 1.
Nasza reguła dotycząca wag w [k] cyfr wymaga, aby suma h [i] * w [i], gdzie i przechodzi od i = 0 do i = k, była równa 1 * w [k + 1]. Podane okresowo, w [k + 1] = w [k] + h [k] * w [k] = w [k] * (h [k] + 1). Pierwsza waga w [0] powinna zawsze wynosić 1. Zaczynając od tego punktu mamy następujące wartości:
k h[k] w[k]
0 1 1
1 2 2
2 3 6
3 4 24
... ... ...
n-1 n n!
(Ogólną zależność w [k-1] = k! Można łatwo udowodnić za pomocą indukcji).
Liczba, którą otrzymamy z konwersji naszego ciągu będzie wówczas sumą s [k] * w [k], gdzie k biegnie od 0 do n-1. Tutaj s [k] jest k-tym (najbardziej po prawej, zaczynając od 0) elementem sekwencji. Jako przykład weźmy nasz {1, 2, 0, 1, 0}, z usuniętym skrajnym prawym elementem, jak wspomniano wcześniej: {1, 2, 0, 1} . Nasza suma to 1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = 37 .
Zwróć uwagę, że jeśli weźmiemy maksymalną pozycję dla każdego indeksu, otrzymamy {4, 3, 2, 1, 0}, a to konwertuje do 119. Ponieważ wagi w naszym kodowaniu liczb zostały wybrane tak, aby nie pomijać wszystkie liczby, wszystkie liczby od 0 do 119 są prawidłowe. Jest ich dokładnie 120, czyli n! dla n = 5 w naszym przykładzie jest to dokładnie liczba różnych permutacji. Możesz więc zobaczyć nasze zakodowane liczby całkowicie określające wszystkie możliwe permutacje.
Dekodowanie na podstawie zmiennej
Dekodowanie jest podobne do konwersji do formatu binarnego lub dziesiętnego. Typowy algorytm jest następujący:
int number = 42;
int base = 2;
int[] bits = new int[n];
for (int k = 0; k < bits.Length; k++)
{
bits[k] = number % base;
number = number / base;
}
Dla naszego numeru o zmiennej podstawie:
int n = 5;
int number = 37;
int[] sequence = new int[n - 1];
int base = 2;
for (int k = 0; k < sequence.Length; k++)
{
sequence[k] = number % base;
number = number / base;
base++; // b[k+1] = b[k] + 1
}
To poprawnie dekoduje nasze 37 z powrotem do {1, 2, 0, 1} ( sequencebyłoby to {1, 0, 2, 1}w tym przykładzie kodu, ale cokolwiek ... o ile odpowiednio indeksujesz). Musimy tylko dodać 0 na prawym końcu (pamiętaj, że ostatni element ma zawsze tylko jedną możliwość dla swojej nowej pozycji), aby odzyskać naszą pierwotną sekwencję {1, 2, 0, 1, 0}.
Permutowanie listy przy użyciu sekwencji indeksów
Poniższy algorytm umożliwia permutowanie listy zgodnie z określoną sekwencją indeksów. Niestety jest to algorytm O (n²).
int n = 5;
int[] sequence = new int[] { 1, 2, 0, 1, 0 };
char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];
bool[] set = new bool[n];
for (int i = 0; i < n; i++)
{
int s = sequence[i];
int remainingPosition = 0;
int index;
// Find the s'th position in the permuted list that has not been set yet.
for (index = 0; index < n; index++)
{
if (!set[index])
{
if (remainingPosition == s)
break;
remainingPosition++;
}
}
permuted[index] = list[i];
set[index] = true;
}
Wspólna reprezentacja permutacji
Normalnie permutacja nie jest przedstawiana tak nieintuicyjnie, jak to zrobiliśmy, ale po prostu przez bezwzględne położenie każdego elementu po zastosowaniu permutacji. Nasz przykład {1, 2, 0, 1, 0} for abcdeto caebdjest zwykle reprezentowany przez {1, 3, 0, 4, 2}. Każdy indeks od 0 do 4 (lub ogólnie od 0 do n-1) występuje dokładnie raz w tej reprezentacji.
Zastosowanie permutacji w tej formie jest łatwe:
int[] permutation = new int[] { 1, 3, 0, 4, 2 };
char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];
for (int i = 0; i < n; i++)
{
permuted[permutation[i]] = list[i];
}
Odwrócenie jest bardzo podobne:
for (int i = 0; i < n; i++)
{
list[i] = permuted[permutation[i]];
}
Konwersja z naszej reprezentacji do wspólnej reprezentacji
Zauważ, że jeśli weźmiemy nasz algorytm do permutacji listy przy użyciu naszej sekwencji indeksów i zastosujemy ją do permutacji tożsamości {0, 1, 2, ..., n-1}, otrzymamy odwrotna permutacja, przedstawiona we wspólnej formie. ( W naszym przykładzie {2, 0, 4, 1, 3} ).
Aby uzyskać nieodwróconą premutację, stosujemy algorytm permutacji, który właśnie pokazałem:
int[] identity = new int[] { 0, 1, 2, 3, 4 };
int[] inverted = { 2, 0, 4, 1, 3 };
int[] normal = new int[n];
for (int i = 0; i < n; i++)
{
normal[identity[i]] = list[i];
}
Lub możesz po prostu zastosować permutację bezpośrednio, używając algorytmu odwrotnej permutacji:
char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];
int[] inverted = { 2, 0, 4, 1, 3 };
for (int i = 0; i < n; i++)
{
permuted[i] = list[inverted[i]];
}
Zauważ, że wszystkie algorytmy radzenia sobie z permutacjami we wspólnej formie to O (n), podczas gdy zastosowanie permutacji w naszej postaci to O (n²). Jeśli chcesz zastosować permutację kilka razy, najpierw przekonwertuj ją na wspólną reprezentację.