# مهندسی نرم افزار > مباحث مرتبط با مهندسی نرم‌افزار > الگوریتم، کامپایلر، هوش مصنوعی و ساختمان داده ها >  الگوریتم به دست آوردن زیر مجموعه های یک مجموعه

## 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  (سایت دانشجویان مهندسی نرم افزار کامیپوتر فردوسی مشهد ورودی 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 
*پیاده سازی این الگوریتم در جاوا به صورت زیر است:* publicstaticvoid 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%...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
https://barnamenevis.org/showthread.p...A-%D9%87%D8%A7
http://www.parsiland.com/21125-%D8%A...%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;
                }
            }
        }
        //-----------------------------------------------------------------------------------------------------------------------
    }
}

----------

