الگوریتم به دست آوردن زیر مجموعه های یک مجموعه

[momal2008]

دوستان سلام
به کمکتون نیاز دارم
دنبال یه الگوریتم پیچیده میگردم.
الان دقیقا یک هفتس که دارم روش فکر میکنم اما راهی براش پیدا نکردم،دیگه فکرم به جایی قد نمیده.
خواهش میکنم اگه امکان داره کمکم کنید.

دنبال یه الگوریتمم که تمام زیر مجموعه های mعضوی از یک مجموعه ی nعضوی رو چاپ کنه
n,m رو کاربر میده و m<n
مجموعه nعبارت است از:{1,2,3,4,5,6…n}
تکرار در زیر مجموعه ها مجاز نیست.یعنی:{1,2,3},{2,1,3}یکی هستند.

ممنون میشم اگه راهنماییم بکنید.
راستی اگه خواستید سورس بفرستید به زبان C++باشه.

[whitehat]

اين كار زياد پيچيده نيست ، بد نيست نگاهي به پياده سازي تركيب (Combination) بياندازيد. تعداد مجموعه هاي m عضوي از يك مجموعه n عضوي برابر تركيب m از n
پ.ن:اينجا بخش الگوريتم ها است و قرار نيست سورس كدي نوشته شود ، سوالات در مورد زبان مورد نظر را در بخش مربوطه بپرسيد

[momal2008]

آقا ممنون.میشه یکم بیشتر توضیح بدید؟

[hafizi]

با سلام
فکر می کنم که جوابتون در این فایل باشه.

[Arya Lee]

سلام

راستش الان کد رو ندارم. اما روش خیلی ساده است. از یک الگوی بیتی استفاده میشه. اگر مجموعه شما رو 3 عضوی فرض کنیم، کل زیر مجموعه ها 8 تا میشه که این تعداد اعداد باینری قابل تولید بوسیله 3 بیت هم هست. پس شما برای تولید کل زیر مجموعه ها کافیه که اعداد از 0 تا دو به توان n منهای یک رو بشمارید و در هر مرحله معادل باینری عدد رو تولید کنید و چاپ کنید. هر رقم صفر در این اعداد باینری نماینده عدم حضور عضو در زیر مجموعه و هر رقم 1 نماینده حضور اون عضو در زیر مجموعه فعلی است. مثلا اگر مجموعه شامل A,B,C باشه:

000= زیرمجموعه تهی

001=C
--------
A=100
--------
ABC=111
--------
AC=101

, الی آخر...
اگر نتونستید کدش رو بنویسید بهم بگید...

پیروز باشید

[alongway]

سلام این برنامه یک روش نسبتا ساده داره که می تونید در سایتhttp://ispc.schoolnet.ir/question-01.html توضیحاتی در موردش پیدا کنید برنامه رو هم میذارم اینجا.




#include<iostream>
using namespace std;
int n,k,a[20],tedad;
void print(){
for(int i=n-1;i>=0;i--){
if(a[i]==1){
cout<<n-i<<" ";
}
}
cout<<endl;
}
int main(){
while(true){
cin>>n>>k;
if(n==0 && k==0){
break;
}
cout<<"n="<<n<<",k="<<k<<endl;
tedad=n;
for(int i=0;i<n;i++){
a[i]=1;
}
int l;
while(tedad>0){
if(tedad==k){
print();
}
l=0;
while(a[l]==0){
tedad++;
a[l]=1;
l++;
}
a[l]=0;
tedad--;
}
}
return 0;
}

[newamir]

میشه تمام زیرمجموعه های مجموعه رو نوشت و زیر مجموعه های m تایی رو نوشت، ولی این روش زمان اجرای خیلی بدی داره. به نظر من این راه بازگشتی بهتره: عضو n رو در نظر بگیر، زیر مجموعه ها رو به دو دسته افراز میکنیم: دسته اول زیرمجموعه هایی که شامل n هستند که میشوند تمام زیر مجوعه های m-1 عضوی مجموعه یک تا n-1 که به اونها n اضافه شده، دسته دوم زیرمجموعه هایی که شامل n نیستند که میشوند زیرمجموعه های m-1 عضوی مجموعه یک تا n-1. حالا این راه بازگشتی رو میشه به صورت پویا هم نوشت.

[gilasse ghermez]

میشه تمام زیرمجموعه های مجموعه رو نوشت و زیر مجموعه های m تایی رو نوشت، ولی این روش زمان اجرای خیلی بدی داره. به نظر من این راه بازگشتی بهتره: عضو n رو در نظر بگیر، زیر مجموعه ها رو به دو دسته افراز میکنیم: دسته اول زیرمجموعه هایی که شامل n هستند که میشوند تمام زیر مجوعه های m-1 عضوی مجموعه یک تا n-1 که به اونها n اضافه شده، دسته دوم زیرمجموعه هایی که شامل n نیستند که میشوند زیرمجموعه های m-1 عضوی مجموعه یک تا n-1. حالا این راه بازگشتی رو میشه به صورت پویا هم نوشت.



سلام میشه بیشتر در مورد تابع بازگشتی واسه این الگوریتم (برای همه زیر مجموعه های یه مجموعه به زبان C) توضیح بدین؟؟؟ممنون

[gilasse ghermez]

دوستان کسی در مورد نوشتن همه ی زیر مجموعه های یه مجموعه با استفاده از تابع بازگشتی میتونه توضیحی واسم بده؟؟ممنون

[Mahdy_M_S]

سلام . با کمی تاخیر نسبت به شروع تاپیک....

دوستمان در خصوص راه حل بازگشتی مساله پرسیده بودند . من کد این حل به همراه توضیحاتش را برای شما میگذارم . خواستید به سایت ما هم سری بزنید .

نمک 88 (http://www.namak88.ir) (سایت دانشجویان مهندسی نرم افزار کامیپوتر فردوسی مشهد ورودی 88) . آنجا تا دلتان بخواهد در انجمن ها صحبت سر این جور چیزهاست.

راه حلی که در زیر می آید ، زیباترین شیوه حل تا کنون است .

الگوریتم آن به این صورت است :

R <- []
L <- [ e1, e2 ... en ]
c <- 0
function: powerSet(L, c)
R <- R union L
for e in L starting at c
powerSet(L\{e}, c)
end
return R
end

پیاده سازی این الگوریتم در جاوا به صورت زیر است:
public static void powerSet(List<String> list, int count)
{
result.add(list);
for(int i = count; i < list.size(); i++)
{
List<String> temp = new ArrayList<String>(list);
temp.remove(i);
powerSet(temp, i);
} }

توضیح الگوریتم : اگر ما بتوانیم مجموعه را به دو زیر مجموعه ای که در یکی یک عضو خاص آمده باشد و در دیگری نیامده باشد ، افراز کنیم ، توانسته ایم یک گام بزرگ در حل بازگشتی مساله برداریم . در این الگوریتم ابتدا لیست شامل اعضا مجموعه گرفته میشود . سپس powerSet در هر مرحله یک عضو خاص را از مجموعه حذف میکند و تمام زیر مجموعه های بدون عضو خاص را به result اضافه میکند.

مشخص شدن عضوی که در هر مرحله باید حذف شود ، توسط اندیس ارسال شده به powerSet انجام میشود و عمل حذف در کد جاوا در خط temp.remove(i) صورت میگیرد. سپس دوباره تابع فراخوانی میشود . برای فهم بهتر یک بار تابع را با A={a,b,c} دنبال کنید.

اشکال این الگوریتم تنها مرتبه زمانی بالای آن (2^n) است.

[amir.mt2]

آقا،
میشه یه الگوریتم برای ساختن و نمایش تمام افراز های مجموعه ای ک اعضاش رو بهش ، به عنوان ورودی میدیم ، رو بهم معرفی کنین !؟
میخوام ترجیحا توی متلب ، یا پیادش کنم ؟

افراز با زیر مجموعه فرق داره ها ...

تعریف و مثال افراز از وکی پدیا ... http://fa.wikipedia.org/wiki/%D8%A7%D9%81%D8%B1%D8%A7%D8%B2_%D9%85%D8%AC%D9%85% D9%88%D8%B9%D9%87

[majid.fe]

به وبلاگ زیر هم یه سری بزنین. شاید به دردتون بخوره:
http://decoding.blogfa.com/

[hodhod21]

درود دوستان
من تازه وارد برناه نویسی شدم. یک تمرینی دارم که موفق به نوشتن حلقه هاش نمیشم و شبیه سوال همین تاپیکه با یک تفاوت . میخوام برنامه مثلا 4 تا رقم ( عدد تک رقمی حتی صفر ) را از کاربر بگیره و تمام حالتهایی که این 4 تا رقم میتونند کنار هم قرار بگیرند را در مونیتور نشون بده مثلا 0369 0396 0693 0639 و ...
فقط حلقه هاشو راهنمایی کنید کافیه . مرسی و بدرودی

[pishvaei]

اگر چهار رقم متمایزباشد ، شما به الگوریتم جایگشت (Permutation) نیاز دارید :
http://neohoosh.tk/post/142
http://open-mind.ir/?p=857
http://barnamenevis.org/showthread.php?364171-%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85-%D9%86%D9%85%D8%A7%DB%8C%D8%B4-%D8%AC%D8%A7%DB%8C%DA%AF%D8%B4%D8%AA-%D9%87%D8%A7
http://www.parsiland.com/21125-%D8%A8%D8%B1%D9%86%D8%A7%D9%85%D9%87-%D9%86%D9%85%D8%A7%DB%8C%D8%B4-%D8%AC%D8%A7%DB%8C%DA%AF%D8%B4%D8%AA-%D9%87%D8%A7%DB%8C-n-%D8%B4%DB%8C.html

[pishvaei]

یک برنامه جمع و جور کنسولی برای جایگشت . توجه کنید که برای ورودی از شما یک استرینگ درخواست میشود مثل ABC .
در خروجی جایگشتهای آن ، یعنی ABC، ACB، BAC و ... درج میشود . میدانیم که تعداد جایگشتهای n شی متمایز برابر n فاکتوریل است .

//-------------------------------------------------//
//---- نوشته شده توسط محمد جواد پيشوايي ----- //
//---- Microsoft Visual Studio 2010 ----- //
//---- ConsoleApplication ----- //
//------- جایگشتهای n عنصر --------------------//
//-------------------------------------------------//
using System;
using System.Linq;
using System.Collections;
using System.Text;
using System.IO;
using System.Collections.Generic;
using System.Data;
using System.Diagnostics;


namespace ConsoleApplication
{
class Program
{
static int n;
static char[] mArr;
static void Main(string[] args)
{
string str;
Console.Write("we obtain permutation of n character In a string . please input string (Ex:ABC) =>");
str = Console.ReadLine();
mArr=str.ToCharArray();
n=mArr.Length-1 ;
perm(0 );
Console.ReadKey();
}
//-----------------------------------------------------------------------------------------------------------------------
static void perm(int k)
{
if (k == n)
Console.WriteLine ( String.Concat(mArr));
else
{
for (int i = k; i <= n; i++)
{
char temp = mArr[i];
mArr [i] = mArr[k];
mArr[k] = temp;
perm(k + 1);
mArr[k] = mArr[i];
mArr[i] = temp;
}
}
}
//-----------------------------------------------------------------------------------------------------------------------
}
}