bir soru :)

[CrazyCat]

bir soru:



1,2,...n kümesinin bütün permütasyonlarını içeren en kısa sayı dizisinin bulunması gerekiyor. her bir permütasyon, dizi içerisinde kesintisiz bir alt-dizi olarak yer alması gerekiyor. istenilen verilen bir n değeri için böyle bir diziyi üretmek.

Varsayımlar
0<n<10
Girdi:
sayi.inp dosyasından okunacak bir n değeri
Çıktı:
dizi.out adlı metin dosyasına yazılacak rakamlar arasında boşluk olmayacak.

Örnek:
sayi.inp
3

dizi.out
312313213

(birer atlamayla 3 ün permütasyonları elde ediliyor)


bu soru (sanırım) bilgisayar olimpiyatlarında daha önce sorulmuş. olimpiyatlarda finale kalan bir öğrenci getirdi bir ilk etapta bir çözüm yazıp verdim. ama olması gerektiği gibi sade ve hızlı olmadı. sonucun 3 saniyeden daha kısa zamanda üretilmesi gerekiyor.

sorun şurda eğer olası permütasyonlar kümesi bir linked list yapısı içerisine kaydedilirse istenilen hız elde edilebilir. fakat list yapısı için delete ve find yöntemleri falan da yazılması gerekiyor. program oldukça uzunlaşıyor. yazmak için yeterince süre yok. (bütün sorular için 5 saat zaman var.)

birde *nix bir sistemde denenirse çalışma zamanı daha doğru hesaplanabilir.

l.list yapısı kullanılmadan cevaplayabilirmisiniz? yada nasıl bir çözüm önerirsiniz.

bir de mümkün olduğunca standart ansi c/c++ kullanılması daha doğru. Örneğin (perm. hesaplamak için STL yöntemlerini kullanmaktan kaçındık) birde çok karmaşık olmayan veriyapıları tercih sebebi çünkü öğrenci lise 2. sınıf öğrencisi ve sadece 15 gün C dersi almış :)

biraz kafa yormak belki iyi gelir. güzel sonuçlar çıkarsa çözdüğümüz ve çözemediğimiz :D diğer sorularla cevaplaını da burda yazarım:) bütün arkadaşlar için antreman olur.

bu arada da ara sıra böyle sorularda gelmese hazıra alışıp mayışacaktık. bir dahaki sefere gençlere karşı mahçup olmamak için diğer soruları da ufak ufak çözmeye başladım :D

[acehreli]

"perm. hesaplamak için STL yöntemlerini kullanmaktan kaçındık" derken STL'deki tam da bu işi yapan işlevi mi kullanmadığınızı söylemek istiyorsunuz? Tabii next_permutation'ı kullansak zaten soruyu çözmüş olmazdık. :)

Stroustrup'un kitabından aldığım şu örneği vermemek için kendimi ancak bir gün tutabildim:



#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
char sayilar[] = "01234";
size_t toplamSayi = sizeof(sayilar) / sizeof(*sayilar) - 1;

cout << sayilar << '\n';
while(next_permutation(sayilar, sayilar + toplamSayi))
{
cout << sayilar << '\n';
}
}



Bu program sizin istediğiniz kadar hızlı değil, çünkü next_permutation bir işlev olduğu için, bilgi saklayamıyor. Daha önceden kaldığı yeri hatırlamadığı için, bir sonraki permütasyonu her çağrıldığında tekrar hesaplamak zorunda.

Ali

[CrazyCat]

STL deki işlevleri kullanmaktan kaçındık anlamında söylemiştim. Çünkü öğrenci daha önce adını bile duymamış. sadece temel C bilgisi var.

dolayısıyla problami çözerken STL deki "next_permutation" işlevi yerine kendimiz bir "SonrakiPerm" işlevi yazmak zorunda kaldık..

sorun şurda permutasyonların listesini bulmak problemin sadece küçük bir parçası ve ben ilk etapta yazarken bu işlevi bile olması gerektiğinden daha uzun ve karmaşık yaptığımın farkına vardım. belli bir süre içinde çözülmesi gerektiğinden üzerinde çok fazla düşünemiyorsunuz.

örneğin permutasyonların listesini oluşturan kısım aşağıdaki gibi oldu. :(





#include <iostream>

int N=4; //dosyadan okutulacak
int Sayilar[10];

void swap (int a, int b);
void PermYaz();
void SayiDoldur(int n);

int SonrakiPerm()
{
int i = N - 1;
while (Sayilar[i-1] >= Sayilar[i]) i = i-1;
int j = N;

while (Sayilar[j-1] <= Sayilar[i-1]) j = j-1;
swap(i-1, j-1);

i++; j = N;

while (i < j)
{
swap(i-1, j-1);
i++;
j--;
}
return *Sayilar;
}


void swap (int a, int b)
{
int foo;
foo=Sayilar[a];
Sayilar[a]=Sayilar[b];
Sayilar[b]=foo;
}

void PermYaz()
{
for (int i=0;i<N;i++)
cout<<Sayilar[i];
cout<<endl;
}

void SayiDoldur (int n)
{
for ( ;n>=1;n--)
{
Sayilar[n-1]=n;

}
}

int main()

{
SayiDoldur(N);
PermYaz();

while(SonrakiPerm())
{
PermYaz();
}

cin.get();
}



ilk etapta çok uzun bir kod. ve aslında permutasyonlar kümesi string bir ifade olasaydı programın devamında daha rahat kullanılırdı. ama ilk yazılım sırasında "N" ifadesi dosyadan okutulacağını düşünerek "Sayılar" kümesinin içeriğini doldurmak için yazdığım SayıDoldur işlevini de göz önünde bulundurarak int tanımladım. pişman oldum :)
mesela PermYaz işlevine gerek kalmazdı.

--------

soruyu çözebilmek için daha sonra elde edilen bütün permütasyon dizilimini bir veri yapısı içinde tutup mümkün olan en kısa altküme dizilimi için veri yapısı içinde arama silme işlemleri yapmak gerekti.

bana ilk etapta "linked list" yapısı uygun geldi ama yazıldıkça oldukça uzun bir prg olmaya başladı :)

daha basit bir çözüm bulunabilir mi?


düşündüğüm algoritma şu şekilde işliyor:

1. dosyadan okutulan sayıların perm. listesi bir veri yapısına yazılıyor.

2. listenin bir kopyasında ilk perm. kümesi alınıyor.
örneğin 3 ün permütasyonları için ilk sıra

123

3. sonra ilk karakterden sonra gelen karakterlerle başlayan ikinci perm alt kümesi alınıyor.

231
ve dizi
1231
şekline geliyor.
4. her alınan alt küme veri yapısında siliniyor.
5. en son elde edilen dizi bir geçici olarak dosyaya yazdırılıyor.
6. daha sonra veri yapısının farklı bir kopyasında ikinci sıradaki perm. alt kümesinden başlanarak aynı işlemler tekrar ediliyor.

en son elde edilen dizilim dosyadakinden kısa ise dosyaya yazılıyor.

en son elde edilen dizilim en kısa sayı dizisini oluşturuyor.. :)

daha hızlı çalışan bir çözüm aklına gelen var mı? bu işi bir veri yapısı kullanmadan nasıl yaparız.

tabi en önemlisi ne kadar hızlı çalışacak. birisinin linux da falan denemesi lazım. win de çalışma süresini ölçecek bir sistem komutu bulamadım. :(