::next_permutation std Uygulama Açıklama

SORU

14 Temmuz 2012, CUMARTESİ

::next_permutation std Uygulama Açıklama

std:next_permutation gnu libstdc 4.7 sürümü çıkarılan ve tanımlayıcıları arındırılmış ve aşağıdaki demo üretmek için biçimlendirme yani nasıl uygulandığını merak ettim..

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

template<typename It>
bool next_permutation(It begin, It end)
{
        if (begin == end)
                return false;

        It i = begin;
          i;
        if (i == end)
                return false;

        i = end;
        --i;

        while (true)
        {
                It j = i;
                --i;

                if (*i < *j)
                {
                        It k = end;

                        while (!(*i < *--k))
                                /* pass */;

                        iter_swap(i, k);
                        reverse(j, end);
                        return true;
                }

                if (i == begin)
                {
                        reverse(begin, end);
                        return false;
                }
        }
}

int main()
{
        vector<int> v = { 1, 2, 3, 4 };

        do
        {
                for (int i = 0; i < 4; i  )
                {
                        cout << v[i] << " ";
                }
                cout << endl;
        }
        while (::next_permutation(v.begin(), v.end()));
}

Beklendiği gibi çıktı: http://ideone.com/4nZdx

Benim soru: Nasıl çalışır? i, j k anlamı nedir? Ne değeri yürütme farklı yerlerinde tutmak mı? Onun doğruluğunun kanıtı bir kroki nedir?

Açıkça ana döngüye girmeden önce sadece önemsiz 0 veya 1 öğe listesi durumlarda denetler. Ana döngüye girdi en son öğeye işaret (bir önceki son değil) ve en az 2 elemanları uzun.

Ana döngü VÜCUTTA NELER oluyor?

CEVAP

14 Temmuz 2012, CUMARTESİ

Hadi biraz permütasyon bak:

Nasıl gelecek için bir permütasyon gideceğiz? Öncelikle, her şeyi farklı bir gözle bakalım.Basamak ve sayı olarak permütasyon gibi unsurları görebiliriz. Bu şekilde sorun görüntülüyorsunuz""sipariş . artan sayıları/permütasyon sipariş etmek istiyoruz .

Biz istediğimiz sayılar sırası ne zaman "en küçük miktar zam". Örneğin ne zaman saymayı bilmiyoruz sayısı 1, 2, 3, 10, ... çünkü hala 4, 5, ... ... arasında ve ancak 10 büyük 3, eksik sayılar olabilir hangi kazanılmış artarak 3 gibi küçük bir miktar. Yukarıdaki örnekte gördüğümüz 1 konaklama olarak ilk sayı için çok uzun bir süre gibi pek çok reorderings son 3 "basamak" olan "artış" permütasyon tarafından daha küçük bir miktar.

Sonunda "" 13**? kullanıyor muyuz yani Sadece son 3 basamak daha permütasyonu var hiçbir zaman.
Ve ne zaman son 3 basamak daha fazla permütasyon var mı? Son 3 basamak azalan zaman.

Aha! Bu algoritmayı anlamak için anahtardır.Biz sadece bir "her zaman" azalan sırada . basamak konumunu değiştirmek eğer azalan sırada değil ise. çünkü o zaman daha permütasyonu var(yani "" daha az miktarda) permütasyon. artırabiliriz

Hadi şimdi kodu geri dön:

while (true)
{
    It j = i;
    --i;

    if (*i < *j)
    { // ...
    }

    if (i == begin)
    { // ...
    }
}

Döngü içinde ilk 2 satır j bir unsurdur ve i daha önce unsurdur.
Eğer öğeleri artan sırada ise (if (*i < *j)) bir şey yapın.
Eğer her şey azalan ise (if (i == begin)) Bu son AHA yoksa.
Aksi halde devam ediyoruz ve j görüyoruz ve aslında indirildiği ben.

Şimdi anlamamız gereken if (*i < *j) bölüm if (i == begin) kısmını anlıyorum.

Ayrıca not: "O zaman unsuru olarak artan sırada ..." hangi destekler, daha önceki gözlem, biz sadece bir şey yapmak için bir basamak "zaman her şeyin doğru azalan sırada". if deyim, aslında en soldaki yeri bulmak artan sırada "hakkı için her şeyi azalan".

Hadi yine bazı örneklere bakın:

...
1 4 3 2
2 1 3 4
...
2 4 3 1
3 1 2 4
...

Bir basamak sağında her şey yolunda, biz azalan zamansonraki en büyük rakam bulmak ve önüne koyve sonraartan kalan sayılar koyun.

Hadi kodu arayın:

It k = end;

while (!(*i < *--k))
    /* pass */;

iter_swap(i, k);
reverse(j, end);
return true;

Sağa şeylerden beri azalan, "biz sadece kodun ilk 3 hatlarında gördüğümüz ucundan yineleme yapmak için." bir sonraki en büyük rakamı bulmak için

Bir sonraki değiştireceğiz "bir sonraki en büyük rakam" ön iter_swap() deyim ve o zamandan bu yana biliyoruz ki bu rakam değildi sonraki en büyük, bildiğimiz basamak hakkını hala azalan yani benzini koymak için artan sırada biz sadece reverse().

Bunu Paylaş: