19 Haziran 2017 Pazartesi

STL Permuting Algoritmaları

Giriş
STL algoritmalarını işlevlerine göre gruplamak anlamayı çok daha kolaylaştırıyor.

Permütasyon Nedir
Permütasyon kümenin tüm elemanlarını farklı sıralarda üretir.

Kombinasyon Nedir
Kombinasyon ise kümenin tüm alt kümelerini verir. Alt kümelerde sıra önemli değildir. Elimizde 0 , 1 olsun .Kombinasyon yaparsak

0
1,
0 ,1
alırız.

is_permutation metodu
Elimizde iki tane string olsun. Bu iki string'in birbirlerini permütasyonu olduğunu anlamak için şöyle yaparız.
return std::is_permutation( str1.begin(),str1.end(), str2.begin(), str2.end() );
next_permutation metodu
Eleman sayısı faktoriyel kadar sonuç döndürür.

Elimizde 1,2 olsun. Permütasyon olarak
1,2
2,1
alırız.

Elimizde 1,2,3 olsun. Permütasyon olarak
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
alırız.

Elimizde 1,2,3,4 olsaydı 24 tane permütasyon olurdu. Sonuç dizisi uzun olduğu için yazmıyorum .

Bu işleme başlamadan önce

1. vector küçükten büyüğe sıralı olmalıdır.
2. Sıralanacak yapının < operatörü olmalıdır. Eğer kendi yapımız ise şöyle yaparız.
class Foo
{
public:
  int x = 0;
  int y = 0;
  
  bool operator <( const Foo& rhs )
  {
    ...
  }
};
Şöyle yaparız.
vector<int> v = ...;
do {
  ...
} while(next_permutation(v.begin(), v.end()));
Aradaki permutasyonları almak istersek şöyle yaparız.
vector<int> v = ...;
vector < vector<int>> outVal ;

sort( v.begin() , v.end() );
do
{
  outVal.push_back (v);
} while (next_permutation (v.begin() , v.end() ) );
prev_permutation metodu
Örnek ver

Hiç yorum yok:

Yorum Gönder