Düzenleme algoritmasının tamamını tek bir makalede okuyun
Yazar | Cooper Song
Sorumlu Editör | Wu Xingling
Sözde tam düzenleme, bir grup karakteri belirli bir sırayla, tüm olası kombinasyonları düzenlemektir.
Basit bir örnek için, "123" ün tam dizisi "123", "132", "213", "231", "312" ve "321" dir.
Kitaplık işlevlerini kullanarak tam düzenleme
C ++ < algoritma > Tam düzenleme üstbilgi dosyasında, yani sözlük sırasına göre uygulanan next_permutation işlevinde uygulanır. Next_permutation işlevini bir kez çalıştırmak "mutasyona" eşdeğerdir. Mutasyondan sonra, sözlüksel sıra orijinal dizeden daha büyük olacaktır, ancak ikinci sırada yer alır. Ayrıca, mutasyondan önce dizeden sonra sıralanır. Bu ne anlama geliyor? Örneğin, "123", bir mutasyondan sonra "213", "321" ve diğer sözlükbilimsel olarak daha büyük dizeler yerine next_permutasyon işlevi çağrıldıktan sonra "132" olacaktır.
Sonraki_permutasyonun bir dönüş değeri vardır, dönüş değeri doğru veya yanlıştır; bu, mutasyondan sonra hala yeni bir permütasyon üretilirse, doğruya döneceği ve yeni permütasyon oluşturulamazsa, yanlış döndüreceği anlamına gelir. Yukarıdaki örnekte olduğu gibi, mevcut dizge zaten "321" ise ve "321" den büyük bir sözlük sıralaması yoksa, bu durumda false döndürülür. Bu nedenle, tam olarak düzenlenecek karakter dizisi "132" ise, önce "123" olarak sıralanmalıdır, aksi takdirde tam düzenlemede "123" atlanacaktır.
Next_permutation'ın kullanımı aşağıdaki gibidir:
#Dahil etmek < video akışı >
#Dahil etmek < algoritma >
ad alanı std kullanarak;
string str;
int main
{
getline (cin, str);
// Sözlük düzenini en aza indirmek için önce sıralayın
sort (str.begin, str.end);
cout < < "Düzenlemenin tamamı:" < < endl;
yapmak
{
cout < < str < < endl;
} while (next_permutation (str.begin, str.end));
dönüş 0;
}
El her şeyi gözyaşı
Ama bu süreci programlayarak nasıl gerçekleştirebiliriz? Bu makale, tam dizi elde etmek için derin arama geriye doğru izleme algoritmasını kullanmayı öğretir. kod aşağıdaki gibi gösterilir:
#Dahil etmek < video akışı > #Dahil etmek < vektör > #Dahil etmek < algoritma > ad alanı std kullanarak; string str; dize sıcaklığı; vektör < bool > vis; void dfs (int cnt, int n) { eğer (cnt == n) { cout < < temp < < endl; dönüş; } for (int i = 0; i < n; i ++) { eğer (vis == yanlış) { temp.push_back (str ); vis = true; dfs (cnt + 1, n); vis = yanlış; temp.pop_back; } } } int main { getline (cin, str); sort (str.begin, str.end); int n = str.size; vis.resize (n); dfs (0, n); dönüş 0; }Üretilen provayı geçici olarak temp dizesinde saklıyoruz ve temp'deki karakter sayısı ilk dizedeki karakter sayısına eşit olduğunda temp çıktısını alıyoruz.
Vis dizisi, dizenin belirli bir alt simgesi tarafından indekslenen karakterin temp'e eklenip eklenmeyeceğini saklar.Sıcaklık eklenirse, vis true olarak ayarlanır ve eklenmezse vis false olur.
Dfs'de iletilen cnt parametresi, geçici olarak doldurulmuş karakterlerin sayısını ifade eder ve n, ilk dizedeki karakterlerin sayısıdır.
Yukarıdaki önceden haber verme ile, ana işlevde dfs (0, n) olarak adlandırıyoruz, bu da başlangıç durumunda temp'de hiçbir karakter olmadığı anlamına gelir.
Herkesin gözlemine kolaylık sağlamak için karakter ve alt simge arasında bağlantı kurmak amacıyla, algoritmayı açıklamak için "012" örneğini kullanırız. Başlangıçta temp = {} ve vis hepsi yanlıştır. Özyinelemeli dfs işlevini girdikten sonra, ilk dizeyi geçmeye başlar ve sonra Temp karakterleri ile doldurun.
Aşağıdaki prosedürü okumadan önce, herkesi, iki öğeye dikkat etmeye davet ediyorum, özyinelemeli düzeylerin sayısı ve mevcut özyinelemeli düzey altındaki i'nin değeri Bu iki öğe, doldurulacak bir sonraki karakteri doğrudan belirler.
Özyinelemeli düzeylerin sayısı ilk başta 0'dır. İ = 0'dan geçişi başlatın. İ = 0, vis = false olduğunda, temp değerini 0 doldurun, sonra vis değerini true olarak ayarlayın ve temp içindeki karakter sayısının 1 olduğunu belirtmek için cnt + 1 = 1 değerini geçirin ve bir sonraki özyineleme düzeyine geçin.
temp = {0}
Şu anda, özyinelemeli düzeylerin sayısı 1'dir. İ = 0'dan geçişi başlatın. İ = 0 olduğunda, vis = true, 0 temp ile doldurulmuş ve koşulları karşılamıyorsa; i = 1, vis = false olduğunda, temp olarak 1'i doldurun, sonra vis'i true olarak ayarlayın ve cnt + 1 = 2'yi belirtmek için iletin Temp'deki karakter sayısı 2'dir ve bir sonraki özyineleme düzeyi gerçekleştirilir. Şu anda
temp = {0,1}
Şu anda, özyinelemeli katman sayısı 2'dir. İ = 0'dan geçişi başlatın. İ = 0 olduğunda, vis = true, 0 temp ile doldurulmuş ve koşulu karşılamıyorsa; i = 1 olduğunda, vis = true, 1 temp ile doldurulmuş ve koşulu karşılamıyorsa; i = 2, vis = false, değiştir 2Sıcaklığı doldurun, sonra vis'i true olarak ayarlayın ve temp'deki karakter sayısının 3 olduğunu belirtmek için cnt + 1 = 3'ü geçirin ve bir sonraki özyineleme düzeyine geçin.
temp = {0,1,2}
Şu anda, özyinelemeli düzeylerin sayısı 3'tür. "Fabrika gereksinimlerini" karşılayan 3 karakterin geçici olarak doldurulduğuna ve çıktının önceki özyineleme düzeyine döndürüldüğüne karar verilir.
Şu anda, özyinelemeli katman sayısı 2'dir. 2 seviyeli özyinelemede en son i = 2'ye geçtiğimde, dfs'den döndükten sonra, temp sonundaki karakter 2 çıkarıldı, böylece vis tekrar yanlış olarak ayarlandı ve geçiş devam etti, i = 3 alt simge aralığını aştı, geçiş sona erdi ve geri dönüş döndürüldü. Bir düzey özyineleme. şu anda
temp = {0,1}
Şu anda, özyinelemeli düzeylerin sayısı 1'dir. Geçen sefer seviye 1 özyinelemede i = 1'e geçtim. Dfs'den döndükten sonra, temp sonundaki 1 karakteri çıkarıldı, bu nedenle vis yeniden yanlış olarak ayarlanır;
temp = {0}
Bu sırada i = 2, vis = false, 2'yi temp'ye doldurun, sonra vis'i true olarak ayarlayın ve temp'deki karakter sayısının 2 olduğunu belirtmek için cnt + 1 = 2'yi geçin ve bir sonraki özyineleme düzeyine geçin ,şu anda
temp = {0,2}
Şu anda, özyinelemeli katman sayısı 2'dir. İ = 0 olduğunda, vis = true, 0 temp ile doldurulmuş ve koşul karşılanmamış; i = 1 olduğunda, vis = false, temp olarak 1'i doldurun, sonra vis'i true olarak ayarlayın ve cnt + 1 = 3'ü belirtmek için iletin Temp'deki karakter sayısı 3'tür ve bir sonraki özyineleme düzeyi gerçekleştirilir. Şu anda
temp = {0,2,1}
Şu anda, özyinelemeli düzeylerin sayısı 3'tür. "Fabrika gereksinimlerini" karşılayan 3 karakterin geçici olarak doldurulduğuna ve çıktının önceki özyineleme düzeyine döndürüldüğüne karar verilir.
Şu anda, özyinelemeli katman sayısı 2'dir. 2-seviyeli özyinelemede en son i = 1'e geçtiğimde dfs'den döndükten sonra, temp sonundaki 1 karakteri çıkarıldı, bu yüzden vis yeniden yanlış olarak ayarlandı. şu anda
temp = {0,2}
Çapraz geçişe devam et, şu anda i = 2, vis = true, 2 geçici olarak dolduruldu ve koşulları karşılamıyor; geçişe devam et, i = 3 alt simge aralığını aşıyor, geçiş sona eriyor ve önceki özyineleme düzeyi döndürülüyor.
Şu anda, özyinelemeli düzeylerin sayısı 1'dir. Seviye 1 özyinelemede en son i = 2'ye geçtiğimde dfs'den döndükten sonra, temp sonundaki karakter 2 çıkarıldı, bu yüzden vis yeniden false olarak ayarlanır. şu anda
temp = {0}
Çapraz geçişe devam edin, i = 3 alt simge aralığını aşar, çapraz geçiş sona erer ve önceki özyineleme düzeyine geri döner.
Şu anda, özyinelemeli düzeylerin sayısı 0'dır. 0-seviye özyinelemede en son i = 0'a geçtiğimde, dfs'den döndükten sonra, temp sonundaki 0 karakteri çıkarıldı, bu yüzden vis tekrar yanlış olarak ayarlandı. şu anda
temp = {}
Bu sırada i = 1, vis = false, 1'i geçici olarak doldurun ve vis'i true olarak ayarlayın ve temp'deki karakter sayısının 1 olduğunu belirtmek için cnt + 1 = 1'i geçin ve bir sonraki özyineleme düzeyine geçin. ,şu anda
temp = {1}
Şu anda, özyinelemeli düzeylerin sayısı 1'dir. İ = 0'dan geçişi başlatın. İ = 0, vis = false olduğunda, temp olarak 0'ı doldurun, sonra vis'i true olarak ayarlayın ve temp'deki karakter sayısının 2 olduğunu belirtmek için cnt + 1 = 2'yi geçirin ve bir sonraki özyineleme düzeyine geçin.
temp = {1,0}
Şu anda, özyinelemeli katman sayısı 2'dir. İ = 0'dan geçişi başlatın. İ = 0 olduğunda, vis = true, 0 temp ile doldurulmuş ve koşulu karşılamıyorsa; i = 1 olduğunda, vis = true, 1 temp ile doldurulmuş ve koşulu karşılamıyorsa; i = 2, vis = false, değiştir 2Sıcaklığı doldurun, sonra vis'i true olarak ayarlayın ve temp'deki karakter sayısının 3 olduğunu belirtmek için cnt + 1 = 3'ü geçirin ve bir sonraki özyineleme düzeyine geçin.
temp = {1,0,2}
Şu anda, özyinelemeli düzeylerin sayısı 3'tür. "Fabrika gereksinimlerini" karşılayan 3 karakterin geçici olarak doldurulduğuna ve çıktının önceki özyineleme düzeyine döndürüldüğüne karar verilir.
Şu anda, özyinelemeli katman sayısı 2'dir. İkinci seviye özyinelemede en son i = 2'ye geçtiğimde. Dfs'den döndükten sonra, geçici'nin sonundaki 2 karakteri çıkarılır, böylece vis tekrar yanlış olarak ayarlanır; geçişe devam edin, i = 3 alt simge aralığını aşar, geçiş biter, yukarı dön Bir düzey özyineleme. şu anda
temp = {1,0}
Şu anda, özyinelemeli düzeylerin sayısı 1'dir. Seviye 1 özyinelemede en son i = 0'a geçtiğimde dfs'den döndükten sonra, temp'nin sonundaki 0 karakteri çıkarıldı, bu nedenle vis yeniden false olarak ayarlanır;
temp = {1}
Bu sırada i = 1, vis = true, 1 geçici olarak dolduruldu ve koşullar karşılanmadı; geçişe devam edin, şu anda i = 2, vis = false, geçici olarak 2'yi doldurun ve sonra vis'i true olarak ayarlayın, Gelen cnt + 1 = 2, temp'deki karakter sayısının 2 olduğu ve bir sonraki özyineleme düzeyinin gerçekleştirildiği anlamına gelir.
temp = {1,2}
Şu anda, özyinelemeli katman sayısı 2'dir. İ = 0'dan geçişi başlatın. İ = 0, vis = false olduğunda, temp 0'ı doldurun, sonra vis'i true olarak ayarlayın ve cnt + 1 = 3'ü geçirin, bu, temp'deki karakter sayısının 3 olduğu ve bir sonraki özyineleme düzeyinin gerçekleştirildiği anlamına gelir.
temp = {1,2,0}
Şu anda, özyinelemeli düzeylerin sayısı 3'tür. "Fabrika gereksinimlerini" karşılayan 3 karakterin geçici olarak doldurulduğuna ve çıktının önceki özyineleme düzeyine döndürüldüğüne karar verilir.
Şu anda, özyinelemeli katman sayısı 2'dir. İkinci düzey özyinelemede en son i = 0'a geçtiğimde. Dfs'den döndükten sonra, temp'nin sonundaki karakter gerçekte 0'dır, bu nedenle vis yeniden false olarak ayarlanır; geçiş yapmaya devam et, vis ve vis ikisi de doğru, yani, 1 ve 2 geçici durumdadır ve koşullar karşılanmaz, geçiş biter ve önceki özyineleme düzeyine geri döner. şu anda
temp = {1,2}
Şu anda, özyinelemeli düzeylerin sayısı 1'dir. Seviye 1 özyinelemede en son i = 2'ye geçtiğimde, dfs'den döndükten sonra, temp sonundaki karakter 2 çıkarıldı, bu yüzden vis yeniden false olarak ayarlandı;
temp = {1}
Çapraz geçişe devam edin, i = 3 alt simge aralığını aşar, çapraz geçiş sona erer ve önceki özyineleme düzeyine geri döner. şu anda
Şu anda, özyinelemeli düzeylerin sayısı 0'dır. Geçen sefer 0-seviyeli özyinelemede i = 1'e geçtim dfs'den döndükten sonra, temp sonundaki 1 karakteri çıkarıldı, bu yüzden vis yeniden yanlış olarak ayarlanır;
temp = {}
Bu sırada i = 2, vis = false, 2'yi temp'ye doldurun, sonra vis'i true olarak ayarlayın ve temp'deki karakter sayısının 1 olduğunu belirtmek için cnt + 1 = 1'i geçin ve bir sonraki özyineleme düzeyine geçin ,şu anda
temp = {2}
Şu anda, özyinelemeli düzeylerin sayısı 1'dir. İ = 0'dan geçişi başlatın. İ = 0, vis = false olduğunda, temp olarak 0'ı doldurun, sonra vis'i true olarak ayarlayın ve temp'deki karakter sayısının 2 olduğunu belirtmek için cnt + 1 = 2'yi geçirin ve bir sonraki özyineleme düzeyine geçin.
temp = {2,0}
Şu anda, özyinelemeli katman sayısı 2'dir. İ = 0'dan geçişi başlatın. İ = 0 olduğunda, vis = true, 0 temp ile doldurulmuş ve koşul karşılanmamış; i = 1 olduğunda, vis = false, temp olarak 1'i doldurun, sonra vis'i true olarak ayarlayın ve cnt + 1 = 3'ü belirtmek için iletin Temp'deki karakter sayısı 3'tür ve bir sonraki özyineleme düzeyi gerçekleştirilir. Şu anda
temp = {2,0,1}
Şu anda, özyinelemeli düzeylerin sayısı 3'tür. "Fabrika gereksinimlerini" karşılayan 3 karakterin geçici olarak doldurulduğuna ve çıktının önceki özyineleme düzeyine döndürüldüğüne karar verilir.
Şu anda, özyinelemeli katman sayısı 2'dir. Geçen sefer ikinci özyineleme seviyesinde i = 1'e geçtim dfs'den döndükten sonra, temp'nin sonundaki 1 karakteri çıkarıldı, bu yüzden vis tekrar false olarak ayarlanır;
temp = {2,0}
Çapraz geçişe devam et, şu anda i = 2, vis = true, 2 geçici olarak dolduruldu ve koşulları karşılamıyor; geçişe devam et, i = 3 alt simge aralığını aşıyor, geçiş sona eriyor ve önceki özyineleme düzeyi döndürülüyor.
Şu anda, özyinelemeli düzeylerin sayısı 1'dir. Seviye 1 özyinelemede en son i = 0'a geçtiğimde dfs'den döndükten sonra, temp'nin sonundaki 0 karakteri çıkarıldı, bu nedenle vis yeniden false olarak ayarlanır;
temp = {2}
Bu sırada i = 1, vis = false, temp olarak 1 doldurun, sonra vis değerini true olarak ayarlayın ve temp'deki karakter sayısının 2 olduğunu belirtmek için cnt + 1 = 2'yi geçin ve bir sonraki özyineleme düzeyine geçin. ,şu anda
temp = {2,1}
Şu anda, özyinelemeli katman sayısı 2'dir. İ = 0'dan geçişi başlatın. İ = 0, vis = false olduğunda, temp 0'ı doldurun, sonra vis'i true olarak ayarlayın ve cnt + 1 = 3'ü geçirin, bu, temp'deki karakter sayısının 3 olduğu ve bir sonraki özyineleme düzeyinin gerçekleştirildiği anlamına gelir.
temp = {2,1,0}
Şu anda, yinelemeli düzeylerin sayısı 3'tür. "Fabrika gereksinimlerini" karşılayan 3 karakterin geçici olarak doldurulduğuna ve çıktının önceki özyineleme düzeyine döndürüldüğüne karar verilir.
Şu anda, özyinelemeli katman sayısı 2'dir. En son ikinci özyineleme seviyesinde i = 0'a geçtiğimde dfs'den döndükten sonra, temp sonundaki 0 karakteri çıkarılır, bu yüzden vis yeniden false olarak ayarlanır;
temp = {2,1}
Çapraz geçişe devam et, vis ve vis her ikisi de true, yani hem 1 hem de 2 geçici durumdadır ve koşullar karşılanmaz, geçiş biter ve önceki özyineleme düzeyi döndürülür.
Şu anda, özyinelemeli düzeylerin sayısı 1'dir. Geçen sefer seviye 1 özyinelemede i = 1'e geçtim dfs'den döndükten sonra, temp sonundaki 1 karakteri çıkarıldı, bu nedenle vis yeniden yanlış olarak ayarlanır;
temp = {2}
Çapraz geçişe devam et, şu anda i = 2, vis = true, 2 geçici olarak dolduruldu ve koşulları karşılamıyor; geçişe devam et, i = 3 alt simge aralığını aşıyor, geçiş sona eriyor ve önceki özyineleme düzeyi döndürülüyor.
Şu anda, özyinelemeli düzeylerin sayısı 0'dır. Geçen sefer 0-seviyeli özyinelemede i = 2'ye geçtim dfs'den döndükten sonra, temp sonundaki karakter 2 çıkarıldı, bu yüzden vis yeniden yanlış olarak ayarlandı. şu anda
temp = {}
Alt simge aralığının ötesinde, i = 3'ü geçmeye devam edin, geçiş biter.
Tüm düzenleme bitti, temp ve vis orijinal durumlarına geri döndü.
Altın üç gümüş dörtlü röportaj sezonu yine, herkesin istediği teklifi alabileceğini umuyorum.
