Neden next_permutation bazı permütasyonları atlıyor?

Question

Bu basit işlev, girilen 5 harf dizesinin tüm izinlerini neden vermiyor? Ben 120 olması gerektiğini düşünüyorum ve next_permutation yanlış dönünceye kadar sadece bir döngü içinde bütün permütasyon döndürmek için 90.

#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <string> 
using namespace std; 

// Creates permutation lists for strings 
vector<string> createdcombos2(string letters) 
{ 
    vector<string> lettercombos;  

    cout << "Letters are: " << letters << endl; //input string 

    do 
     lettercombos.push_back(letters);   
    while(next_permutation(letters.begin(), letters.end()));  

    cout <<"Letter combos: " << endl; //print out permutations 
    for (auto i : lettercombos) 
     cout << i << endl; 
    cout << endl << lettercombos.size() << endl; //number of permutations 

    return lettercombos; 
} 


int main() 
{ 
    string letters = "gnary"; 
    vector<string> lettercombos; 

    lettercombos = createdcombos2(letters); 
} 

Answer 1

verir, vektör döngünün başlamasından önce sıralanması gerekir. next_permutation, artan sırayla permütasyonları döndürür. Yani, eğer sıralanmamış bir vektör ile başlıyorsanız, bu, permütasyon serilerinde kısmen yol almaya başlayacaktır.

std::sort(letters.begin(), letters.end()); 
do 
    lettercombos.push_back(letters);   
while(next_permutation(letters.begin(), letters.end())); 

Answer 2

Sen next_permutation sözlük sırasını sonraki permütasyon dönecektir, giriş sıralamak gerekir. Giriş permütasyonu: "gnary" sözlük bilgisi, "öfkeli" gibi bir permüpten "büyüktür", bu "daha küçük" permütasyonlara hiçbir zaman ulaşılmaz.

Sen std::sort()

Answer 3

next_permutation ait bool değeri bir taşma durumu veya bir taşıma bit gibidir getiri kullanarak dizeyi sıralayabilirsiniz. Son permütasyondan ilke, sözcükbilgisel düzende ilerlediğinde, false. Ama yine de koşulsuz olarak ilerliyor. Eğer bool dönüş değerini kullanmak istiyorsanız, daha önce yapılmış cevaplar bazı devlet olarak

for (int i = 0; i != 120; ++ i) { 
    lettercombos.push_back(letters);   
    next_permutation(letters.begin(), letters.end()); 
} 

Answer 4

: Tam olarak 120 permütasyon vardır biliyorsanız

, dönüş değeri ve körlemesine sadece döngü yok sayabilirsiniz Yinelemeleri durdurmak için std::next_permutation, "sıralanmış" bir permütasyondan başladığınızdan emin olmalısınız. Aksi halde, döngünüz zamanından önce sona erecektir.

Bu kesinlikle gerekli değil. std::next_permutation boyunca sıralanan

Permütasyon Eğer her basıldığında 120 permütasyon aynı dizisi boyunca tekrar tekrar tekrar süresiz std::next_permutation arayıp anlamına gelir başlangıcı ve sonu olmayan bir siklik sekansı oluşturmaktadır. Bu, döngüde kesinlikle herhangi bir permütasyondan başlayabileceğiniz anlamına gelir. Sadece başlangıç ​​permütasyonunu hatırlamanız ve bu permütasyonun tekrar ortaya çıktığı anı izlemek zorundasınız. Orijinal permütasyonunuza ulaştığınız an, yineleme sona erer. Durumunuzda, std::next_permutation'a 120 çağrı almanız bekleniyor. Örneğin

, "abcde" için tüm 5 harfli permütasyon bile set aşağıdaki kod yazdırır döngüsünün her tekrarda bu karşılaştıran permütasyon daha olsa not edebilirsiniz tamamen keyfi bir

std::string start = "cadeb", current = start; 
do 
    std::cout << current << std::endl; 
while (std::next_permutation(current.begin(), current.end()), current != start); 

One başlar olsa std::next_permutation (algoritmanın gizemlerinden "ücretsiz olarak" gelir) değerini kullanmaktan daha pahalıdır, bu yüzden, başlangıç ​​permütasyonunu önceden çözen çözümden memnunsanız, bunu yapmak gerçekten daha etkili bir yoldur . Alternatif olarak, döngüdeki tam permütasyon sayısını biliyorsanız (bu durumda 120), tam olarak std::next_permutation numarasını (Potatoswatter'ın yanıtında belirtildiği gibi) tam olarak arayabilirsiniz.