PDA

View Full Version : ترکیب های مختلف یک رشته



zizi_zizi69
چهارشنبه 29 اردیبهشت 1389, 18:41 عصر
سلام

من یک arraylist دارم که شامل یکسری کاراکترهای رشته ای است،میخوام یک رشته فرضی را بهش بدم و اگر اون رشته شامل کاراکتر های بود که در arraylist هست یک بار در رشته باشه یک بار نباشه.

مثلا
ورودی {َ"B","A"} و AaBD
خروجی:َaBD,AaD,aD,AaBD

میشه راههای مختلفی را بفرمایید.
ممنون

Ehsan.Saradar
چهارشنبه 29 اردیبهشت 1389, 22:03 عصر
امیدوارم درست باشه :

private void Form1_Load(object sender, EventArgs e)
{
ArrayList mylist = new ArrayList();
mylist.Add('A');
mylist.Add('B');
string pattern = "AaBD";
label1.Text = pattern + Environment.NewLine;
rec(mylist,pattern,0);
}

private void rec(ArrayList lst, string patern ,int index)
{
if (index >= lst.Count)
return;
if (patern.IndexOf((char)(lst[index])) == -1)
rec(lst, patern, index + 1);
string temp = patern.Remove(patern.IndexOf((char)lst[index]),1);
label1.Text+=temp + Environment.NewLine;
rec(lst, temp, index + 1);
rec(lst, patern, index + 1);
}

zizi_zizi69
چهارشنبه 29 اردیبهشت 1389, 22:50 عصر
میشه درباره کدتون توضیح بدید،

مشکل من اینکه وقتی رشته تکراری از کاراکترهای موجود در arraylist هست وقتی از دستور replace استفاده می کنم،دوتا را همزمان replace می کنه برای همین یکسری از ترکیب ها رو از دست می دم!؟:افسرده:

zizi_zizi69
شنبه 01 خرداد 1389, 12:52 عصر
گویا سوالم را واضح مطرح نکردم،

ببینید اگر در رشته ای دوتا از یک کاراکتر باشه مثلا :
رشته "SbS" ،
در این رشته "S" رشته ای از arraylist ما باشه،{"S"}
در اون صورت خروجی ما "bS"و "Sb" و"b" باید باشه
در حالی که با دستور replace نتیجه نهایی فقط "b" هست،
کسی نظری یا پیشنهادی نداره؟

ممنون

محمد سلیم آبادی
شنبه 01 خرداد 1389, 14:00 عصر
سلام

من یک arraylist دارم که شامل یکسری کاراکترهای رشته ای است،میخوام یک رشته فرضی را بهش بدم و اگر اون رشته شامل کاراکتر های بود که در arraylist هست یک بار در رشته باشه یک بار نباشه.

مثلا
ورودی {َ"B","A"} و AaBD
خروجی:َaBD,AaD,aD,AaBD

میشه راههای مختلفی را بفرمایید.
ممنون


گویا سوالم را واضح مطرح نکردم،

ببینید اگر در رشته ای دوتا از یک کاراکتر باشه مثلا :
رشته "SbS" ،
در این رشته "S" رشته ای از arraylist ما باشه،{"S"}
در اون صورت خروجی ما "bS"و "Sb" و"b" باید باشه
در حالی که با دستور replace نتیجه نهایی فقط "b" هست،
کسی نظری یا پیشنهادی نداره؟

ممنون

نتایج نمونه هایی که آوردین با همدیگر سازگانی ندارن.
در مثال اول یکبار نیز کل رشته انتخاب میشه ولی در مثال دوم شما SbS را جز نتیجه مورد نظر قرار ندادین چرا؟

از طرفی با این توضیحات، فکر می کنم شما اگر رشته ی sBsDs را داشته باشین و S کاراکتر مورد نظر باشه 2 به توان 3 ترکیب نیاز دارین یعنی اینها:

sBsDs
sBD
BsD
BDs
sBsD
BsDs
sBDs
BD

و حالا رشته ی sBBsDDEsK را تصور کنید کاراکتر های s و K هدف ما هستند، چه زیر رشته هایی از رشته ی اصلی را نیاز دارین بدست آورین؟
آیا این substring ها را نیاز دارین (البته یکی از عناصر را پیدا نکردم)

sBBsDDEsk
sBBDDE
sBBsDDE
sBBsDDEs
sBBDDEs
sBBDDEk
sBBsDDEk
BBsDDEsk
BBsDDEs
BBsDDEk
BBDDEsk
BBDDEs
BBDDEk
BBDDE
BBsDDE


اگر این نتیجه، نتیجه ی دلخواه شما باشد، در واقع این مساله، مساله ی معروف Power Set خواهد بود که تعداد زیر مجموعه های آن برابر است با 2 به توان N (در مثال N برابر با عناصر هدف هست یعنی تعداد s جمع بر تعداد k که می شود 4) که در مثال ما 16 زیر مجموعه خواهد بود،
به این مثال توجه کنید:

A = {a, b, c} --d
P(A) = { {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}, {null}} --d


پیشنهاد من این هست که دنبال الگوریتم Power Set در اینترنت بگردین.
موفق باشید.

Ehsan.Saradar
شنبه 01 خرداد 1389, 16:28 عصر
فکر می کنم مشکل برنامه حل شده و برای ورودی مورد نظر شما هم درست جواب داد

private void Form1_Load(object sender, EventArgs e)
{

ArrayList mylist = new ArrayList(); // لیستی از حروف که باید جستجو و حذف شود
ArrayList answer = new ArrayList(); // لیستی که پاسخ ها را در آن ذخیره می شود
mylist.Add('S');
string pattern = "SBS"; // رشته اصلی
answer.Add(pattern);
rec(mylist,ref answer, pattern,0); // محاسبه ترکیب ها
for(int i=0;i<answer.Count;i++) // چاپ نتایج
label1.Text += answer[i].ToString() + Environment.NewLine;

}

private void rec(ArrayList lst, ref ArrayList answer, string patern, int index)
{
if(index>=lst.Count)
return; // اگر تمام حروف بررسی شده بود پایان کار تابع است
for(int i=0;i<patern.Length;i++)
if (patern[i] ==(char) lst[index])
{
string temp = patern.Remove(i, 1);
if (answer.Contains(temp) == false)
answer.Add(temp); // جلوگیر از چاپ نتایج به صورت تکراری
rec(lst,ref answer, temp, index); // ادامه کار با حذف حرف مورد نظر از رشته اصلی
rec(lst,ref answer, patern, index+1); // ادامه کار بدون حذف حرف مورد نظر از رشته اصلی
}
rec(lst,ref answer, patern, index + 1);
}

zizi_zizi69
شنبه 01 خرداد 1389, 17:30 عصر
نتایج نمونه هایی که آوردین با همدیگر سازگانی ندارن.
در مثال اول یکبار نیز کل رشته انتخاب میشه ولی در مثال دوم شما SbS را جز نتیجه مورد نظر قرار ندادین چرا؟



درست می فرمایید در مثال دوم باید SbS هم می اوردم.

مثالی که زدید دقیقا اون چیزی هست که میخوام از راهنماییتون ممنون.