giúp em liệt kê tập con k của n phần tử ?

[tun_tun]

Ví dụ :
em có mảng 4 phần tử ( 3 , 10 , 20 , 30 )

Em sẽ có
3 20 30
3 10 30
3 10 20
10 20 30

4 phần tử có thể là 1 số nào đó bất kì
Mong các anh chị giúp đỡ em về thuật toán và có thể cho em xem đoạn code C cài đặt luôn nha ! Thanks

[Ada]

/*===================================================================*/
/* C program for distribution from the Combinatorial Object Server.  */
/* Generates the k-combinations of [n] by transpositions via a       */
/* direct algorithm (see the book for what "direct" means).          */
/* No input error checking.  Assumes 0 <= k <= n <= MAX.             */
/* Outputs both the bitstring and the transposition (x,y) (meaning   */
/* that x leaves the subset and y enters).                           */
/* Algorithm is CAT (Constant Amortized Time).                       */
/* The program can be modified, translated to other languages, etc., */
/* so long as proper acknowledgement is given (author and source).   */     
/* Programmer: Frank Ruskey, 1995.                                   */
/* The latest version of this program may be found at the site       */
/* http://theory.cs.uvic.ca/inf/comb/CombinationsInfo.html            */
/*===================================================================*/

#define MAX 100   /* maximum value of n */

int b[MAX+1];
int n, k;
int cnt=0;

void PrintIt ( int x, int y ) {
  int i;
  printf( "%8d: ", ++cnt );
  for ( i=1; i<=n; ++i ) printf( "%d ", b[i] );  
  if (x != 0) printf( "     (%d,%d)", x,y ); 
  printf( "\n" );
} /*of PrintIt*/;

void swap ( int x, int y ) {
  int t;
  b[x] = 1;  b[y] = 0;
  PrintIt( x, y ); 
} /* of swap */;

void NEG ( int n, int k );
void GEN ( int n, int k ); 

void GEN ( int n, int k ) {
  if (k > 0 && k < n) {
     GEN( n-1, k );
     if (k == 1) swap( n, n-1 );  else swap( n, k-1 );
     NEG( n-1, k-1 );
  }
} /* of GEN */;

void NEG ( int n, int k ) {
  if (k > 0 && k < n) {
     GEN( n-1, k-1 );
     if (k == 1) swap( n-1, n );  else swap( k-1, n );
     NEG( n-1, k );
  }
} /* of NEG */;

void main () {
  int i;
  printf( "Enter n,k: " );  scanf( "%d %d", &n, &k );
  for ( i=1; i<=k; ++i) b[i] = 1;
  for ( i=k+1; i<=n; ++i) b[i] = 0;
  PrintIt( 0, 0 ); 
  GEN( n, k );
}

Ví dụ:

Enter n,k: 5 3
       1: 1 1 1 0 0
       2: 1 0 1 1 0      (4,2)
       3: 0 1 1 1 0      (2,1)
       4: 1 1 0 1 0      (1,3)
       5: 1 0 0 1 1      (5,2)
       6: 0 1 0 1 1      (2,1)
       7: 0 0 1 1 1      (3,2)
       8: 1 0 1 0 1      (1,4)
       9: 0 1 1 0 1      (2,1)
      10: 1 1 0 0 1      (1,3)

Hướng dẫn hack:

Các hàm gen() và neg() thực thi thuật toán. Chúng làm việc với tập hợp {1,...,n}. Chúng hoàn toàn độc lập với cấu trúc dữ liệu của tập hợp mẹ (n phần tử) và tập con (k phần tử). Chúng không biết và không cần biết cấu trúc dữ liệu của các tập hợp này.

Hàm swap() và printit() làm việc với cấu trúc dữ liệu. swap(x,y) có tác dụng đưa x vào tập con và lấy y ra khỏi tập con. printit() xuất cấu trúc dữ liệu ra màn hình.

Bởi thế, nếu muốn nhập và xuất ra theo dạng yêu cầu của đề bài, hãy sửa các hàm swap(), printit() và viết một hàm, chẳng hạn scanit(), để nhập dữ liệu.

Ví dụ, theo đề bài này của bạn, thì

+ Tập hợp mẹ được thực thi bằng một mảng a[1...n] chứa các số bất kỳ. Tham số x, y cho swap(x,y) là 2 chỉ số của phần tử trong mảng. Chỉ số chạy từ 1 đến n vì gen() và neg() làm việc trên tập {1...n}.

+ Tập hợp con có thể được thực thi bằng mảng con a[1...k] của mảng a[1...n] nói trên. Khi đó swap(x,y) sẽ phải hoán đổi giá trị a[x] với a[y].

+ scanit() sẽ phải nhập tập hợp mẹ, tức là nhập a[1...n].

+ printit() sẽ phải xuất tập hợp con, tức là xuất a[1...k].