Permalink
Reply
N elemanın 6'lı kombinasyonlarını oluşturmanın bir yolu aşağıdaki gibidir. Aklıma gelen sakıncalarını açıklama satırlarına yazdım:
/**
* Kombinasyonları oluşturmak için elle yazılabilen işlev. Sakıncaları:
*
* - Hane adedi değiştiğinde kodun değiştirilmesi gerekir
*
* - Değişken isimleri hataya açık
*
* - Yalnızca RandomAccessRange aralıklarıyla kullanılabilir
*
* - Kombinasyonların koşut olarak işletilmeleri kolay değil çünkü en içteki
* döngü içinde std.parallesims.Task nesnelerinin açıkça oluşturulmaları,
* başlatılmaları, ve bitmelerinin açıkça beklenmeleri gerekir.
*/
void altıDöngülü(const int[] dilim)
{
writeln("Sırayla işleterek:");
foreach (i0; 0 .. dilim.length - 5) {
foreach (i1; i0 + 1 .. dilim.length) {
foreach (i2; i1 + 1 .. dilim.length) {
foreach (i3; i2 + 1 .. dilim.length) {
foreach (i4; i3 + 1 .. dilim.length) {
foreach (i5; i4 + 1 .. dilim.length) {
işle([dilim[i0], dilim[i1], dilim[i2],
dilim[i3], dilim[i4], dilim[i5] ]);
}
}
}
}
}
}
}
Kombinasyonları bir aralık olarak sunabilsek hem daha fazla aralık çeşidiyle kullanılabilir hem de koşut olarak işletilebilirler. Bayağı debelenerek :) aşağıdaki Kombinasyon aralığını yazdım. (Uyarı: Doğru çalıştığından emin olmadan kullanmayın!)
Deneyen programın tamamını veriyorum. Açıklamalar da ekledim:
import std.stdio;
import std.string;
import std.range;
import std.traits;
import std.conv;
import core.thread;
import std.parallelism;
import std.exception;
/**
* Verilen aralığın belirtilen sayıda elemandan oluşan kombinasyonlarını
* dilimler halinde üretir.
*/
struct Kombinasyon(A)
if (isForwardRange!A)
{
private:
size_t kaçlı; /* Kaçlı kombinasyon olduğu */
A[] karalama; /* Elemanları üretmek için kullanılan
* aralıklar. Bir anlamda bir karalama tablosu
* olarak kullanılacaklar. (Performans notu: Bu
* üye front() hiç çağrılmayacak olsa bile
* hesaplanır.) */
ElementType!A[] baştaki; /* Baştaki eleman (Performans notu: Bu üye
* front() hiç çağrılmayacak olsa bile
* hesaplanır.) */
/**
* Kombinasyonları üretmek için kullanılacak olan aralıkları ve baştaki
* elemanı hesaplar.
*/
void hazırla()
in
{
assert(!karalama.empty); /* Eksiği bulunabilir. */
assert(baştaki.length == kaçlı);
}
body
{
if (karalama.length == kaçlı) {
/* Karalama tablolarında düzenleme gerekmiyor. */
} else {
/* popFront() tarafından olasılıkla kaybedilmiş olan aralıkları
* yerine koy. Her aralık, bir önceki aralığın baştan bir eleman
* eksiğidir. */
karalama.length = kaçlı;
for (size_t i = 1; i < kaçlı; ++i) {
if (karalama[i].empty) {
karalama[i] = karalama[i - 1].save;
if (!karalama[i].empty) {
karalama[i].popFront();
}
}
}
}
/* Baştaki kombinasyon aralığını hesapla. */
foreach (i, aralık; karalama) {
if (!aralık.empty) {
baştaki[i] = aralık.front();
}
}
}
public:
this(A aralık, size_t kaçlı)
{
this.kaçlı = kaçlı;
this.karalama ~= aralık.save;
this.baştaki.length = kaçlı;
hazırla();
/* Uzunluğu belli olan aralıklarda ısrarcı olmamak için baştan
* aralık.length'e bakmıyoruz. Onun yerine, bütün aralıklar'ın
* dolabilmiş olmasına bakıyoruz. */
enforce(!karalama[$-1].empty,
format("Bu %s aralığıyla %s elemanlı kombinasyon oluşturulamaz",
typeid(A), kaçlı));
}
bool empty() const @property
{
return karalama.empty;
}
ElementType!A[] front() @property
{
enforce(!empty);
return baştaki.dup;
}
void popFront()
{
enforce(!empty);
/* Sondaki hanenin başındaki çıkart ve bütün karalama aralıklarını
* gerektiği kadar düzenle. */
karalama.back.popFront();
size_t i = kaçlı - 1;
for ( ; i > 0; --i) {
if (karalama[i].length < kaçlı - i) {
/* Bu hane için eleman kalmamış. Bunu çıkartalım ve bir önceki
* hanenin de başındakini çıkartalım. */
karalama.length = i;
karalama[i - 1].popFront();
} else {
/* Baştaki hanelere karşılık gelen karalama aralıklarına
* bakmaya gerek yok. */
break;
}
}
/* En baştaki karalama aralığında yeterli yer kalmadığında bütün
* işimiz bitmiş demektir. */
if (karalama[0].length < kaçlı) {
karalama.popFront();
assert(karalama.empty);
} else {
hazırla();
}
}
}
/**
* Kombinasyon türüyle ve onun şablon parametreleriyle uğraşmamak için
* kullanılan geleneksel kolaylık işlevi.
*/
auto kombinasyon(A)(A aralık, size_t kaçlı)
{
return Kombinasyon!A(aralık, kaçlı);
}
/**
* Üretilen aralıkları kullanan işlev.
*/
void işle(int[] aralık)
{
writeln("baş ", aralık);
Thread.sleep(dur!("msecs")(10));
writeln("son ", aralık);
}
/**
* Kombinasyonları oluşturmak için elle yazılabilen işlev. Sakıncaları:
*
* - Hane adedi değiştiğinde kodun değiştirilmesi gerekir
*
* - Değişken isimleri hataya açık
*
* - Yalnızca RandomAccessRange aralıklarıyla kullanılabilir
*
* - Kombinasyonların koşut olarak işletilmeleri kolay değil çünkü en içteki
* döngü içinde std.parallesims.Task nesnelerinin açıkça oluşturulmaları,
* başlatılmaları, ve bitmelerinin açıkça beklenmeleri gerekir.
*/
void altıDöngülü(const int[] dilim)
{
writeln("Sırayla işleterek:");
foreach (i0; 0 .. dilim.length - 5) {
foreach (i1; i0 + 1 .. dilim.length) {
foreach (i2; i1 + 1 .. dilim.length) {
foreach (i3; i2 + 1 .. dilim.length) {
foreach (i4; i3 + 1 .. dilim.length) {
foreach (i5; i4 + 1 .. dilim.length) {
işle([dilim[i0], dilim[i1], dilim[i2],
dilim[i3], dilim[i4], dilim[i5] ]);
}
}
}
}
}
}
}
void aralıklı(A)(A aralık)
{
writeln("Koşut işleterek:");
foreach(eleman; parallel(aralık, 1)) {
işle(eleman);
}
}
void main()
{
int[] dilim;
foreach (i; 0 .. 12) {
dilim ~= i;
}
writeln("Bütün elemanlar: ", dilim);
writeln("Altılı kombinasyonları:");
aralıklı(kombinasyon(dilim, 6));
// altıDöngülü(dilim);
}
Ali
--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]