n uzunluğundaki bir permütasyon, 1, 2, ..., n sayılarının tekrarı olmayan sıralı bir koleksiyondur. Örneğin, [3, 1, 2] ve [5, 4, 3, 2, 1] permütasyondur ancak [1, 2, 1, 3] ve [1, 2, 4] değildir.
Görev, n uzunluğundaki tüm permütasyonları yinelemenin gerekli olduğu gerçeğine indirgenirse, C++'da "sonraki_permütasyon" adı verilen uygun bir mekanizma kullanabilirsiniz.
Bununla ilgili daha fazla bilgiyi belgelerde okuyabilirsiniz, ancak önemli olan nokta, bu işlevin geçen diziyi değiştirmesidir sözlük sırasına göre müteakip permütasyona (ki bu genellikle açıktır ve adıdır).
next_permutation'ı kullanmak için algoritma kitaplığını eklemeniz gerekir (yani, programın başına #include <algorithm> yazın)
Örnekler:
vektör dizi;
dizi = { 1, 2, 3 }; // dizi [1, 2, 3]
next_permutation(arr.begin(), dizi.end()); // tüm diziyi işleve iletin
// dizi artık [1, 3, 2]
dizi = { 2, 3, 1 }; // dizi [2, 3, 1]
next_permutation(arr.begin(), dizi.end()); // tüm diziyi işleve iletin
// dizi artık [3, 1, 2]
next_permutation(arr.begin() + 1, dizi.begin() + 3); // bir dizinin bir bölümüne bir işlev uygulamak mümkündür, ancak pratikte buna nadiren ihtiyaç duyulur
// dizi artık [3, 2, 1]
Bu durumda, işlev, bir sonraki permütasyon oluşturulduysa true ve sonraki permütasyon yoksa false olan bir boolean dönüş değerine sahiptir (sözlük sırasına göre maksimum permütasyonun işleve iletildiği durum).
Bu, işlevi bir döngüde kullanmayı mümkün kılar, bu da tüm permütasyonları aynı anda yinelememize izin verir. Bir permütasyon resmi olarak 1'den n'ye kadar sayılar içermesine rağmen, 0 indeksleme nedeniyle pratikte 0'dan n - 1'e kadar sayıların bir permütasyonu ile çalışmak genellikle daha uygundur. Ancak neyse ki bu, kodda ek bindirmelere yol açmaz, çünkü next_permutation işlevi, 0 dizinli permütasyonlara (ve hatta bir dizideki yinelenen öğelere) uyarlanmıştır, ancak daha fazlasını kendi başınıza öğrenebilirsiniz).
Genel olarak, tüm permütasyonları yineleme kodu şöyle görünür:
int; // permütasyon boyutu
vektörperm(n); // perm, "permütasyon"un kısaltmasıdır, yani "permütasyon"
için (int ben = 0; ben
Bu kod O(n! * f(n)) şeklinde çalışır, burada f(n), belirli bir permütasyonu işlemeniz için geçen süredir.
|