Lập trình C | đưa ra tất cả tập con của 1 tập kí tự

[myNew]

mình làm bài này thì mắc vào 1 vấn đề mà mãi kô giải quyết được, (hình như có liên quan đến Quy hoạch động, mà mình chưa học).
với 1 xâu có n kí tự thì sẽ có 2^n -2 tập kt con (bỏ rỗng và chính nó)
giả sử

Input : ABCD
Output: A,B,C,D,AB,AC,AD,BC,BD,CD,ABC,ABD,ACD,BCD

có (2^4)-2 =14.

mình làm theo hướng mỗi tập kt con sẽ được biểu diễn = 1 số nhị phân đúng n bit. (n là số p tử xâu).

ví dụ 0001 = D, 0011 = CD ..v..v

nhưng bị hạn chế bộ nhớ lưu các xâu con vì nó lại phụ thuộc vào độ dài n.

đây là code, đoạn này chỉ chạy đc với n=10, trên 10 là lỗi ngay

#include <stdio.h>
#include <string.h>
#include <math.h>

char N[100];     // Luu xau ban dau can tim xau con.
char M[100];    // Luu xau nhi phan
char xaucon[1024][100]; //Luu cac xau con
int main(void)
 {
 int in,i,m;
 //bien in dung luu so trung gian khi tim nhi phan
 //Bien i,m dung chay vong lap
 int num;
 //Bien num dung luu so xau con cua 1 xau, num=2^(strlen)
 int x, y, j, k,l;
 //Bien x luu 2 gia tri 0,1
 //bien y de lap
 //Bien j,k de tang
 
 printf("Nhap xau N: ");
 fflush(stdin);gets(N);
 
 num = pow(2,strlen(N));
 printf("Se co %d xau con\n",num-2);

 for(m=1;m<num-1;m++)
 {
 x = y = j =0;
 k=0;
 in=m;
 for(y = strlen(N)-1; y >= 0; y--)
 {
  x = in / (1 << y);
  in = in - x * (1 << y);
  if(x==0)
  {
  M[j]='0';
  }
  else
  {
  M[j]='1';
  }
  j++;
 }
 for(i=0;i<strlen(M);i++)
 {
    if(M[i]=='1')
    {
     xaucon[m-1][k]=N[i];
     k++;
    }
 }
 printf("\n---> Xau con so %d  = %s ",m,xaucon[m-1]);
 }
 return 1;
} 

vấn đề là ở biến xaucon, làm sao để không bị hạn chế vì độ dài n nhỉ, mình không rành C cho lắm nên bó tay

thanks

[myNew]

hic....bạn nào help tớ với.....:(( khẩn khẩn

[nhc1987]

char N[100]; // Luu xau ban dau can tim xau con.
char M[100]; // Luu xau nhi phan
char xaucon[1024][100]; //Luu cac xau con

Tui nghĩ lỗi là do 3 cái này gây ra (tràn stack). Nếu đúng thì bạn giải quyết bằng cách cấp phát động.

P/s: thuật toán đọc khó hỉu quá :(. Chắc tại tui dở :(

[myNew]

Tui nghĩ lỗi là do 3 cái này gây ra (tràn stack). Nếu đúng thì bạn giải quyết bằng cách cấp phát động.

P/s: thuật toán đọc khó hỉu quá :(. Chắc tại tui dở :(

uh, thì do chỗ đó mà, với n phần tử thì sẽ có 2^n tập con, nếu lưu
xaucon[1024][100]; tức là chỉ lưu số xâu con của 1 xâu 10 ptử (2^10 =1024)

....

Cấp phát động là sao nhỉ:">, mà bạn nào có thuật toán hay hơn chỉ tớ với....

[whoru]

Theo mình nghĩ, bài toán có thể giải quyết một cách đơn giản hơn bạn nghĩ: ta đâu cần phải lưu các chuỗi nhị phân biểu diễn cho 1 xâu con?! Ứng với 1 số nguyên từ 1->2^n - 1 bạn in trực tiếp xâu con cho nó. Minh họa sau với giả sử bạn đã lưu các ký tự của chuỗi ban đầu trong mảng a[n]:

for( i = 1; i < 2 ^ n - 1; i++ ) {
  // in tổ hợp tương ứng với chuỗi i ra
  // chẳng hạn i = 1101 -> in ABD ra
  for( j = 0; j < n; j++ ) {
     if( i & ( 1<< ( n - j - 1))) // bit tương ứng với ký tự a[j] = 1
        cout << a[j];
  } 
  cout << ", ";
}

Nếu bạn muốn in theo đúng thứ tự, chẳng hạn A,B,C,D, AB, AC, AD,BC, BD, CD, ABC..., thì có lẽ bạn phải dùng cách khác.
Thân!