N eleman var. Örnek aşkına, hadi 7 diyelim, 1234567 elemanları. 7 olduğunu biliyorum! = 5040 bu 7 element Olası permütasyon.

İki işlevi teslimat kapsamı: hızlı bir algoritma istiyorum

f(sayı) haritalar ve benzersiz bir permütasyon için 5039 0 arasında bir sayı, ve

f'(permütasyon) haritalar permütasyon geri verdi, bu sayı için oluşturulan.

Sayı ve permütasyon arasındaki ilişkiyi hakkında, her permütasyon kendine özgü bir numarası vardır sağlayan umurumda değil.

Bu yüzden, örneğin, fonksiyonları nerede olabilirim

f(0) = '1234567'
f'('1234567') = 0

En hızlı algoritma aklınıza gelen olduğu için numaralandırma tüm permütasyon oluşturmak ve bir arama tablosu içinde her iki yönde, yani, bir kez tabloları oluşturulur, f(0) O(1) ve f('1234567') bir ara bir dize. Ancak, bu özellikle n büyük olduğunda bellek aç.

Herkes hızlı ve bellek dezavantajı olmadan çalışacak bir algoritma önerebilir?

Açıklamak için bir permütasyon n elemanları, gördüğünüz pozisyonu ilk öğe bulur, var n olanaklarını, siz de yapabilirsiniz bu tarif ile arasında bir sayı 0 ile n-1. Bir sonraki öğeye biter pozisyonu için, n-1 olasılık kaldı, 0 ve n-2 arasında bir sayı ile anlatabilirsiniz.
N sayı kadar vesaire.

= 5, permütasyon düşünün için n bir örnek olarak caebd 10 *getiriyor.

• a, ilk öğe, dizin atamak yani ikinci konumda buluyor1.
• b Endeksi 3, ama üçüncü kalan tek şey olan dördüncü konumunda biter, biz atamak2.
• c kadar olan ilk kalan pozisyon, her zaman biter0.
• d son kalan pozisyonunda biter1.
• e geriye kalan tek pozisyonu, endeksli biter0.

Dizin sırası var{1, 2, 0, 1, 0}.

Şimdi ikili bir sayıyı, örneğin, biliyorsun, 'xyz' anlamına z 2y 4x. Ondalık sayı için
10y 100 katına z. Her basamak ağırlığı ile çarpılır ve sonuçlar toplanır. Ağırlığı belirgin desen dersin ağırlığı w = b^k, b Bir sayı ve k baz rakam dizini ile. (Her zaman doğru ve en sağdaki basamak için index 0'dan başlayarak basamak sayacağım. Aynı şekilde konuşurum 'ilk' basamak yani en sağdaki.)

nedenineden ağırlıklar için basamak izleyin bu model en yüksek sayıyı temsil edilebilir rakamı 0 k olmalı tam olarak 1 daha düşük daha düşük sayıda temsil edilebilir tek haneli kullanarak k 1. İkili, 0111 1000'den daha düşük olmalıdır. Ondalık, 099999 100000'den düşük olmalıdır.

Değişken temel kodlama
Sonraki sayılar tam olarak 1 olmak arasındaki boşluğu önemli kural. Bunu fark eden bizim Endeksi sırası tarafından temsil edebilirizdeğişken-baz numarası. Her basamak için temel bu rakam için farklı olanaklar miktarıdır. Ondalık için her basamak 10 olasılık, en sağdaki basamak 1 olasılık olurdu ve soldaki n olasılıklar olacaktır sistemimiz var. Ama en sağdaki basamak (bizim sıra son rakam her zaman 0, yana bırak. Bu üsleri n 2 kaldık demektir. Genel olarak, k'inci basamak Bankası b[k] = k 2 olacaktır. En yüksek değer basamağı k h[k] = b[k] - 1 = k 1 için izin verdi.

Bizim kural hakkında ağırlıkları w[k] basamak gerektiren toplamı h[i] * w[i], ben nereye gider i = 0 i = k, = 1 * w[k 1]. Belirtilen tekrar tekrar, w[k 1] = w[k] h[k] * w[k] = [k] g*(h[k] 1). İlk ağırlık w[0] her zaman 1 olmalıdır. Orada itibaren, aşağıdaki değerleri var:

k    h[k] w[k]    

0    1    1  
1    2    2    
2    3    6    
3    4    24   
...  ...  ...
n-1  n    n!  

(Genel ilişkisi w[k-1] = k! kolayca indüksiyon ile ispat edilir.)

Bizim dönüştürme sırası gelen numarayı sonra[k] s * w[k] toplamı, k n-1 0 ile çalışan olacak. Burada s[k] sırası (, 0'dan başlayarak en sağdaki) k'inci unsurdur. En sağdaki eleman daha önce de belirtildiği gibi çıkardı bir örnek olarak, bizim{1, 2, 0, 1, 0}al, :{1, 2, 0, 1}. Bizim sum 1 1 0 * 2 2 * 6 1 * 24 = * .37.

Eğer her dizin için maksimum pozisyon alırsak, zorunda kalırız unutmayın{4, 3, 2, 1, 0}, ve o 119 dönüştürür. Sayımız kodlama ağırlıkları herhangi bir sayı atlamak bilmiyoruz seçildi yana, tüm sayıların 0 119 için geçerlidir. Tam olarak n olan bu, 120 var! n = 5 örneğimizde, tam olarak farklı permütasyon sayısı. Kodlanmış sayımız tamamen farklı olasılık belirtmek görebilirsiniz.

Değişken tabanından kod çözme
Kod çözme ikili veya ondalık dönüştürmek için benzer. Ortak bir algoritma bu

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

Değişken-sayı: bizim için

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
}

Bu doğru çözer bizim 37 geri {1, 2, 0, 1} (sequence olur {1, 0, 2, 1} Bu kod örneği, ama neyse ... sürece senin dizin gerektiği gibi). Biz sadece ihtiyacımız Ekle 0 ucu (unutma son öğe her zaman bir olasılık için yeni bir pozisyon) için geri bizim orijinal sıra {1, 2, 0, 1, 0}.

Bir dizin listesi sırasını kullanarak Permuting
Algoritma aşağıdaki dizin belirli bir sıraya göre bir liste kapsamalıdır için kullanabilirsiniz. (N2) O bir algoritma, ne yazık ki.

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

Permütasyon ortak gösterimi
Normalde sadece permütasyon uygulandıktan sonra her bir öğenin mutlak konumu ile yaptığımız gibi unintuitively olarak, ama bir permütasyon temsil olmaz. caebd 23 *bizim için örnek {1, 2, 0, 1, 0} normalde{1, 3, 0, 4, 2}tarafından temsil edilir. 4 0 (ya da genel olarak, 0 n-1) her dizin bu temsilin tam olarak bir kez oluşur.

Bu formda bir permütasyon uygulamak kolay

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

Çok benzer eviren:

for (int i = 0; i < n; i  )
{
    list[i] = permuted[permutation[i]];
}

Ortak temsili için bizim temsil dönüştürme
Eğer biz bizim algoritma kapsamalıdır listesini kullanarak bizim Endeksi sırası ve uygular, kimlik permütasyon {0, 1, 2, ..., n-1}, alıyoruzterspermütasyon, genel hali ile temsil etti. ({2, 0, 4, 1, 3}bizim örnek).

Non-ters mutasyon olsun, ben sadece gösterdi algoritma permütasyon uyguluyoruz:

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

Ya da sadece permütasyon doğrudan, ters permütasyon algoritması kullanarak uygulayabilirsiniz:

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

Genel hali permütasyon ile ilgili tüm algoritmalar formumuzu bir permütasyon uygulama(n2) O sırada O(n) olduğunu unutmayın. Eğer bir permütasyon birkaç kez uygulamak gerekiyorsa, ilk ortak temsili dönüştürmek.