زیرمجموعه های k عضوی یک مجموعه n

**razroz** · دوشنبه 18 آذر 1392, 15:54 عصر

سلام دوستان من میخوام زیرمجموعه های k عضوی یک مجموعه n عضوی رو توسط یک تابع پیدا کنم طوری که تابع خروجی به صورت آرایه دو بعدی n*kبه برنامه برگرداند!!!!!!!
لطفا کمکم کنید تا یه جاهایی رفتم ولی نمیشه

**rahnema1** · سه شنبه 19 آذر 1392, 00:40 صبح

تا هر جا پیش رفتی برنامه اش را بذار اینجا ببینیم مشکل چیه؟

**razroz** · سه شنبه 19 آذر 1392, 17:55 عصر

نوشته شده توسط rahnema1

تا هر جا پیش رفتی برنامه اش را بذار اینجا ببینیم مشکل چیه؟

اینو از یه سایتی کمک گرفتم یکم تغیرات دادم
حالا میخوام هر زیر مجموعه kتایی رو هم همه زیر مجموعه های tتایی اش رو پیدا کنم!!!!!
ولی نمیدونم چی رو به تابع subset بدم؟؟
امیدورم متوجه شده باشید
ممنون میشم اگه کمک کنید
#include<iostream>

#include<conio.h>
#include<time.h>

int **m;
long q=0;
long num=0;
long number=0;

long fact( long n )
{
return ( n > 0 ? n*fact(n-1) : 1 );
}

long C( long n , long r )
{
return ( fact(n)/(fact(r)*fact(n-r)) );
}

bool isPrinted(int *a, long n)
{
bool is=true;
for(long i=0;i<num;i++)
{
is=true;
for(long j=0;j<n;j++)
{
if(a[j]!=m[i][j])
{
is=false;
}
}
if(is)return true;
}
return false;
}

void print(int *a,long n)
{
int swap=0;
for(long i=0;i<n;i++)
{
for(long j=i;j<n;j++)
{
if(a[j]<a[i])
{
swap=a[i];
a[i]=a[j];
a[j]=swap;
}
}
}
if(!isPrinted(a,n))
{
number++;
cout<<number<<".{";
for(long i=0;i<n;i++)
{
cout<<a[i];
m[q][i]=a[i];
if(i!=n-1)
{
cout<<",";
}
}
q++;
cout<<"}"<<endl;
}
}

void printAll(int *a,int *b,long n,long k)
{
if(q<num)
{
if(k==1)
{
print(a,n);
}
if(k==0)
{
print(a,n);
}
else if(k>0)
{
int *c, *d;
long p=0;
for(long j=0;j<k;j++)
{
p=0;
c=new int[k-1];
for(long t=0;t<k;t++)
{
if(t!=j)
{
c[p]=b[t];
p++;
}
}
d=new int[n];
for(long i=-1;i<n;i++)
{
for(long t=0;t<n;t++)
{
d[t]=a[t];
}
if(i!=-1)
{
d[i]=b[j];
}
printAll(d,c,n,k-1);
}
}
delete c , d;
}
}
}
void subset (int *a,long n,long k){ int *b=new int[k];
int *c=new int[n-k];
for(long i=0;i<n;i++)
{
if(i<k)
{
b[i]=a[i];
}
else
{
c[n-i-1]=a[i];
}
}
num=C(n,k);
m=new int*[C(n,k)];
for(long i=0;i<C(n,k);i++)
{
m[i]=new int[k];
}
printAll(b,c,k,n-k);

delete a , b , c;
for(int j=0;j<num;j++){
cout<<"{" ;
for(int s=0;s<k;s++){

cout<<m[j][s]<<"," ;

}
cout<<"}";
}}

int main()

{
// time_t start , end;
long n = 0 , k = 0,t=0;
cout<<"Tedade ozv haye majmue:";
cin>>n;
cout<<"Tedade ozv haye zir majmue:";
cin>>k>>t;
cout<<"Ozv haye majmue ra vared konid:"<<endl;
int *a=new int[n];
for(long i=0;i<n;i++)
{
cin>>a[i];
}

cout<<"S={";
for( long i = 0 ; i < n ; i++ )
{
cout<<a[i];
if( i != n-1 )
cout<<",";
}
cout<<"}"<<endl;
num=C(n,k);
subset(a,n,k);
int **z;
z=new int *[num];
for(int j=0;j<num;j++){
z[j]=new int[k];
for(int s=0;s<k;s++){
z[j][s]=m[j][s];

}
}
int *b1;
b1=new int [k];
for(int j=0;j<k;j++){
b1[j]=z[0][j];

cout<<b1[j]<<"," ;

cout<<"."<<endl; }
subset(b1,num,t) ;

delete b1,z;

getch();
return 0;

}

**sr2m72** · سه شنبه 19 آذر 1392, 18:24 عصر

سلام
لطفا کدهاتون رو توی تگ قرار بدین تا واضح باشه.

**razroz** · سه شنبه 19 آذر 1392, 18:31 عصر

نوشته شده توسط sr2m72

سلام
لطفا کدهاتون رو توی تگ قرار بدین تا واضح باشه.

چشم ببخشید
منظورتون این طوریه؟؟

[ #include<iostream>
#include<conio.h>
#include<time.h>

int **m;
long q=0;
long num=0;
long number=0;

long fact( long n )
{
return ( n > 0 ? n*fact(n-1) : 1 );
}

long C( long n , long r )
{
return ( fact(n)/(fact(r)*fact(n-r)) );
}

bool isPrinted(int *a, long n)
{
bool is=true;
for(long i=0;i<num;i++)
{
is=true;
for(long j=0;j<n;j++)
{
if(a[j]!=m[i][j])
{
is=false;
}
}
if(is)return true;
}
return false;
}

void print(int *a,long n)
{
int swap=0;
for(long i=0;i<n;i++)
{
for(long j=i;j<n;j++)
{
if(a[j]<a[i])
{
swap=a[i];
a[i]=a[j];
a[j]=swap;
}
}
}
if(!isPrinted(a,n))
{
number++;
cout<<number<<".{";
for(long i=0;i<n;i++)
{
cout<<a[i];
m[q][i]=a[i];
if(i!=n-1)
{
cout<<",";
}
}
q++;
cout<<"}"<<endl;
}
}

void printAll(int *a,int *b,long n,long k)
{
if(q<num)
{
if(k==1)
{
print(a,n);
}
if(k==0)
{
print(a,n);
}
else if(k>0)
{
int *c, *d;
long p=0;
for(long j=0;j<k;j++)
{
p=0;
c=new int[k-1];
for(long t=0;t<k;t++)
{
if(t!=j)
{
c[p]=b[t];
p++;
}
}
d=new int[n];
for(long i=-1;i<n;i++)
{
for(long t=0;t<n;t++)
{
d[t]=a[t];
}
if(i!=-1)
{
d[i]=b[j];
}
printAll(d,c,n,k-1);
}
}
delete c , d;
}
}
}
void subset (int *a,long n,long k){ int *b=new int[k];
int *c=new int[n-k];
for(long i=0;i<n;i++)
{
if(i<k)
{
b[i]=a[i];
}
else
{
c[n-i-1]=a[i];
}
}
num=C(n,k);
m=new int*[C(n,k)];
for(long i=0;i<C(n,k);i++)
{
m[i]=new int[k];
}
printAll(b,c,k,n-k);

delete a , b , c;
for(int j=0;j<num;j++){
cout<<"{" ;
for(int s=0;s<k;s++){

cout<<m[j][s]<<"," ;

}
cout<<"}";
}}

int main()

{
// time_t start , end;
long n = 0 , k = 0,t=0;
cout<<"Tedade ozv haye majmue:";
cin>>n;
cout<<"Tedade ozv haye zir majmue:";
cin>>k>>t;
cout<<"Ozv haye majmue ra vared konid:"<<endl;
int *a=new int[n];
for(long i=0;i<n;i++)
{
cin>>a[i];
}

cout<<"S={";
for( long i = 0 ; i < n ; i++ )
{
cout<<a[i];
if( i != n-1 )
cout<<",";
}
cout<<"}"<<endl;
num=C(n,k);
subset(a,n,k);
int **z;
z=new int *[num];
for(int j=0;j<num;j++){
z[j]=new int[k];
for(int s=0;s<k;s++){
z[j][s]=m[j][s];

}
}
int *b1;
b1=new int [k];
for(int j=0;j<k;j++){
b1[j]=z[0][j];

cout<<b1[j]<<"," ;

cout<<"."<<endl; }
subset(b1,num,t) ;

delete b1,z;

getch();
return 0;

}]

**razroz** · سه شنبه 19 آذر 1392, 18:34 عصر

ببخشید من نمیدونم منظورتون چیه؟؟

**sr2m72** · سه شنبه 19 آذر 1392, 18:44 عصر

نوشته شده توسط razroz

ببخشید من نمیدونم منظورتون چیه؟؟

اینطوری:



#include<iostream>

#include<conio.h>

#include<time.h>



int **m;

long q=0;

long num=0;

long number=0;



long fact( long n )

{

    return ( n > 0 ? n*fact(n-1) : 1 );

}



long C( long n , long r )

{

    return ( fact(n)/(fact(r)*fact(n-r)) );

}



bool isPrinted(int *a, long n)

{

     bool is=true;

     for(long i=0;i<num;i++)

     {

             is=true;

             for(long j=0;j<n;j++)

             {

                      if(a[j]!=m[i][j])

                      {

                                is=false;

                      }

             }

             if(is)return true;

     }

     return false;

}



void print(int *a,long n)

{

     int swap=0;

     for(long i=0;i<n;i++)

     {

             for(long j=i;j<n;j++)

             {

                     if(a[j]<a[i])

                     {

                                  swap=a[i];

                                  a[i]=a[j];

                                  a[j]=swap;

                     }

            }

     }

     if(!isPrinted(a,n))

     {

     number++;

     cout<<number<<".{";

     for(long i=0;i<n;i++)

     {

            cout<<a[i];

             m[q][i]=a[i];

             if(i!=n-1)

             {

                  cout<<",";

             }

     }

     q++;

     cout<<"}"<<endl;

     }

}



void printAll(int *a,int *b,long n,long k)

{

     if(q<num)

     {

     if(k==1)

     {

             print(a,n);

     }

     if(k==0)

     {

             print(a,n);

     }

     else if(k>0)

     {

          int *c, *d;

          long p=0;

          for(long j=0;j<k;j++)

          {

                  p=0;

                  c=new int[k-1];

                  for(long t=0;t<k;t++)

                  {

                          if(t!=j)

                          {

                                  c[p]=b[t];

                                  p++;

                          }

                  }

                  d=new int[n];

                  for(long i=-1;i<n;i++)

                  {

                          for(long t=0;t<n;t++)

                          {

                                  d[t]=a[t];

                          }

                          if(i!=-1)

                          {

                                   d[i]=b[j];

                          }

                          printAll(d,c,n,k-1);

                  }

          }

          delete c , d;

     }

     }

}

void subset (int *a,long n,long k){ int *b=new int[k];

    int *c=new int[n-k];

    for(long i=0;i<n;i++)

    {

            if(i<k)

            {

                b[i]=a[i];

            }

            else

            {

                c[n-i-1]=a[i];

            }

    }

    num=C(n,k);

    m=new int*[C(n,k)];

    for(long i=0;i<C(n,k);i++)

    {

            m[i]=new int[k];

    }

    printAll(b,c,k,n-k);

    delete a , b , c;

    for(int j=0;j<num;j++){

    cout<<"{"   ;

   for(int s=0;s<k;s++){

  cout<<m[j][s]<<","  ;

  }

    cout<<"}";

                }}



int main()

{

   // time_t start , end;

    long n = 0 , k = 0,t=0;

    cout<<"Tedade ozv haye majmue:";

    cin>>n;

    cout<<"Tedade ozv haye zir majmue:";

    cin>>k>>t;

    cout<<"Ozv haye majmue ra vared konid:"<<endl;

    int *a=new int[n];

    for(long i=0;i<n;i++)

    {

            cin>>a[i];

    }

    cout<<"S={";

    for( long i = 0 ; i < n ; i++ )

    {

         cout<<a[i];

         if( i != n-1 )

             cout<<",";

    }

    cout<<"}"<<endl;

   num=C(n,k);

     subset(a,n,k);

     int **z;

     z=new int *[num];

    for(int j=0;j<num;j++){

    z[j]=new int[k];

    for(int s=0;s<k;s++){

    z[j][s]=m[j][s];

    }

    }

    int *b1;

    b1=new int [k];

    for(int j=0;j<k;j++){

    b1[j]=z[0][j];

    cout<<b1[j]<<","      ;

   cout<<"."<<endl; }

   subset(b1,num,t)  ;

    delete b1,z;

    getch();

    return 0;

}

**razroz** · سه شنبه 19 آذر 1392, 18:53 عصر

ممنون
خودتون زحمت کشیدید
میتونید کمک کنید؟؟

**rahnema1** · سه شنبه 19 آذر 1392, 21:18 عصر

مگه میشه؟ آخه زیرمجموعه های k عضوی یک مجموعه n عضوی برابره با



n!/(k!*(n-k)!)

حالا چه طور می خواهی اون رو توی یک ماتریس n*k جابدید؟

اصلاح: درسته میشه. فکر کردم n تا سطر داره و یک ستون که در هر ستونش یک مجموعه K عضویه

**razroz** · چهارشنبه 20 آذر 1392, 13:29 عصر

نوشته شده توسط rahnema1

مگه میشه؟ آخه زیرمجموعه های k عضوی یک مجموعه n عضوی برابره با



n!/(k!*(n-k)!)

حالا چه طور می خواهی اون رو توی یک ماتریس n*k جابدید؟

اصلاح: درسته میشه. فکر کردم n تا سطر داره و یک ستون که در هر ستونش یک مجموعه K عضویه

این قسمتشو یه کاری کردم
حالا میخوام دوباره تابع subsetرو فرا خوانی کنم برای هر کدوم از این زیر مجموعه های kتایی ولی نمیدونم چ ظور؟؟؟
شما میدونید؟؟

**amirhossein.ha** · چهارشنبه 20 آذر 1392, 21:35 عصر

اینم کدش با C++‎‎‎ خیلی ساده تر از اونی که بالا گذاشتی اگه توضیح خواستی بگو
اول تعداد اعضای مجموعه بعد اعضاش و بعد هم k رو وارد میکنیم :



#include <iostream>



using namespace std;



int a[1000000]  , n , k , c;



int main()

{

    cin >> n ;

    for(int i = 0 ; i < n ; i++)

        cin >> a[i] ;

    cin >> k ;

    for(int i = 0 ; i < (1<<n) ; i++)

    {

        for(int j = 0  ; j <= n ; j++)

        {

            if( i & (1<<j))

            {

                C++‎‎‎ ;

            }

        }

        if (c == k)

        {

            for(int j = 0  ; j <= n ; j++)

            {

                if( i & (1<<j))

                {

                    cout << a[j] << ' ' ;

                }

            }

            cout << '\n' ;

        }

        c = 0 ;

    }

    return 0;

}

**razroz** · پنج شنبه 21 آذر 1392, 01:15 صبح

نوشته شده توسط amirhossein.ha

اینم کدش با C++‎‎‎ خیلی ساده تر از اونی که بالا گذاشتی اگه توضیح خواستی بگو
اول تعداد اعضای مجموعه بعد اعضاش و بعد هم k رو وارد میکنیم :



#include <iostream>



using namespace std;



int a[1000000]  , n , k , c;



int main()

{

    cin >> n ;

    for(int i = 0 ; i < n ; i++)

        cin >> a[i] ;

    cin >> k ;

    for(int i = 0 ; i < (1<<n) ; i++)

    {

        for(int j = 0  ; j <= n ; j++)

        {

            if( i & (1<<j))

            {

                C++‎‎‎ ;

            }

        }

        if (c == k)

        {

            for(int j = 0  ; j <= n ; j++)

            {

                if( i & (1<<j))

                {

                    cout << a[j] << ' ' ;

                }

            }

            cout << '\n' ;

        }

        c = 0 ;

    }

    return 0;

}

حیلی ممنونم خیلی خوبه
فقط این یعنی چی؟using namespace std
ببخشید اگه سوال خیلی ضایع ایه

**razroz** · پنج شنبه 21 آذر 1392, 02:04 صبح

نوشته شده توسط amirhossein.ha

اینم کدش با C++‎‎‎ خیلی ساده تر از اونی که بالا گذاشتی اگه توضیح خواستی بگو
اول تعداد اعضای مجموعه بعد اعضاش و بعد هم k رو وارد میکنیم :



#include <iostream>



using namespace std;



int a[1000000]  , n , k , c;



int main()

{

    cin >> n ;

    for(int i = 0 ; i < n ; i++)

        cin >> a[i] ;

    cin >> k ;

    for(int i = 0 ; i < (1<<n) ; i++)

    {

        for(int j = 0  ; j <= n ; j++)

        {

            if( i & (1<<j))

            {

                C++‎‎‎ ;

            }

        }

        if (c == k)

        {

            for(int j = 0  ; j <= n ; j++)

            {

                if( i & (1<<j))

                {

                    cout << a[j] << ' ' ;

                }

            }

            cout << '\n' ;

        }

        c = 0 ;

    }

    return 0;

}

ببخشید یه سوال دارم شرط این خلقه یعنی چی؟؟

for(int i = 0 ; i < (1<<n) ; i++)

و آیا میشه این برنامه رو به شکل تابع کرد با خروجی آرایه ای ؟؟؟
من نتونستم !!

**amirhossein.ha** · جمعه 22 آذر 1392, 14:25 عصر

اینم با ارایه :‌ با فراخوانی تابع subset که دوتا ورودی داره زیر مجموعه های k عضویش رو توی یه ارایه ی دوبعدی به اسم sub میریزه :

#include <iostream>



using namespace std;



int a[1000000]  , n , k , c , sub[1000][1000];



void subset(int n ,int k)

{

    int  g = 0 , h = 0 ;

    for(int i = 0 ; i < (1<<n) ; i++)

    {

        for(int j = 0  ; j <= n ; j++)

        {

            if( i & (1<<j))

            {

                C++‎ ;

            }

        }

        if (c == k)

        {

            g = 0 ;

            for(int j = 0  ; j <= n ; j++)

            {

                if( i & (1<<j))

                {

                    sub[g][h] = a[j] ;

                    g++ ;

                }

            }

            h++ ;

        }

        c = 0 ;

    }

}

int main()

{

    cin >> n ;

    for(int i = 0 ; i < n ; i++)

        cin >> a[i] ;

    cin >> k ;

    subset(n,k) ;

    return 0;

}

using name space std برای اینه که نیاز نباشه قبل دستورات از std:: استفاده کنیم اگه این رو ننویسیم برنامه به صورت زیر میشه :



int main()

{

    std::cin >> n ;

    return 0;

}

ولی وقتی اون رو مینویسیم دیگه نیازی نیست std:: بزاریم
برای اطلاعات بیشتر میتونی این رو بخونی :‌ http://www.cplusplus.com/forum/beginner/49748/

">>" این هم یکی از عمگر های بیتوایز (Bitwise operation) در C++‎ هست و برای شیفت دادن ازش استفاده میشه و در مبنای دو کار میکنه به این صورت که اگر مثلا متغیر ما در مبنای دو به صورت 100101 باشد بعد از یکبار شیفت به 001010 تبدیل میشه یعنی اولین عدد از سمت چپ حذف میشه و یک صفر به سمت راست اضافه میشه در نتیجه اگر یک رو که در مبنای دو به صورت 1 هست رو n بار شیفت بدیم به 2 به توان n میرسیم و این هم به همین معناست .

**razroz** · جمعه 22 آذر 1392, 15:56 عصر

ممنون
ولی ارایه درsub درست نیست؟؟
نمیدونم چرا؟
درسته معذرت میخوام
ممنون بی نهایت

**Hesamhosseini** · سه شنبه 26 فروردین 1393, 14:15 عصر

نوشته شده توسط amirhossein.ha

اینم با ارایه :‌ با فراخوانی تابع subset که دوتا ورودی داره زیر مجموعه های k عضویش رو توی یه ارایه ی دوبعدی به اسم sub میریزه :

#include <iostream>



using namespace std;



int a[1000000]  , n , k , c , sub[1000][1000];



void subset(int n ,int k)

{

    int  g = 0 , h = 0 ;

    for(int i = 0 ; i < (1<<n) ; i++)

    {

        for(int j = 0  ; j <= n ; j++)

        {

            if( i & (1<<j))

            {

                C++‎‎‎ ;

            }

        }

        if (c == k)

        {

            g = 0 ;

            for(int j = 0  ; j <= n ; j++)

            {

                if( i & (1<<j))

                {

                    sub[g][h] = a[j] ;

                    g++ ;

                }

            }

            h++ ;

        }

        c = 0 ;

    }

}

int main()

{

    cin >> n ;

    for(int i = 0 ; i < n ; i++)

        cin >> a[i] ;

    cin >> k ;

    subset(n,k) ;

    return 0;

}

using name space std برای اینه که نیاز نباشه قبل دستورات از std:: استفاده کنیم اگه این رو ننویسیم برنامه به صورت زیر میشه :



int main()

{

    std::cin >> n ;

    return 0;

}

ولی وقتی اون رو مینویسیم دیگه نیازی نیست std:: بزاریم
برای اطلاعات بیشتر میتونی این رو بخونی :‌ http://www.cplusplus.com/forum/beginner/49748/

">>" این هم یکی از عمگر های بیتوایز (Bitwise operation) در C++‎‎‎ هست و برای شیفت دادن ازش استفاده میشه و در مبنای دو کار میکنه به این صورت که اگر مثلا متغیر ما در مبنای دو به صورت 100101 باشد بعد از یکبار شیفت به 001010 تبدیل میشه یعنی اولین عدد از سمت چپ حذف میشه و یک صفر به سمت راست اضافه میشه در نتیجه اگر یک رو که در مبنای دو به صورت 1 هست رو n بار شیفت بدیم به 2 به توان n میرسیم و این هم به همین معناست .

سلام آقا من دقیقا همینطوری که هست برنامه رو نوشتم ورودی ها رو که میدم بعدش که اینتر میزنم کاری انجام نمیده!! مشکلش چیه؟؟

نام تاپیک: زیرمجموعه های k عضوی یک مجموعه n

ابزار های تاپیک

نمایش

زیرمجموعه های k عضوی یک مجموعه n

نقل قول: زیرمجموعه های k عضوی یک مجموعه n

نقل قول: زیرمجموعه های k عضوی یک مجموعه n

نقل قول: زیرمجموعه های k عضوی یک مجموعه n

نقل قول: زیرمجموعه های k عضوی یک مجموعه n

نقل قول: زیرمجموعه های k عضوی یک مجموعه n

نقل قول: زیرمجموعه های k عضوی یک مجموعه n

نقل قول: زیرمجموعه های k عضوی یک مجموعه n

نقل قول: زیرمجموعه های k عضوی یک مجموعه n

نقل قول: زیرمجموعه های k عضوی یک مجموعه n

نقل قول: زیرمجموعه های k عضوی یک مجموعه n

نقل قول: زیرمجموعه های k عضوی یک مجموعه n

نقل قول: زیرمجموعه های k عضوی یک مجموعه n

نقل قول: زیرمجموعه های k عضوی یک مجموعه n

نقل قول: زیرمجموعه های k عضوی یک مجموعه n

نقل قول: زیرمجموعه های k عضوی یک مجموعه n

تاپیک های مشابه

یافتن تعداد زیرمجموعه‌های یک مجموعه

سوال: لود شدن زیرمجموعه های مرتبط با یک مجموعه

زیر مجموعه های k عضوی

سوال: زیرمجموعه های یک مجموعه

پیدا کردن زیرمجموعه های یک فولدر

قوانین ایجاد تاپیک در تالار