从给定的集合中罗列出符合条件的子集代码,C代码库,德仔网

代码语言

代码分类

【C】从给定的集合中罗列出符合条件的子集

作者:黃偉達 / 发布于2014/7/17/ 842

给定集合 {11, 9, 8, 7, 5, 3, 2, 1}，罗列出所有的子集，子集合中各个元素的和为给定值，如18.


	/*
	* Generate subset summing up equal to target
	*
	* Given set {11, 9, 8, 7, 5, 3, 2, 1};
	* Given TARGET 18
	* Output subsets which subject to subset sum equal target
	* Output
	* {11, 7}
	* {11, 5, 2}
	* {9, 8, 1}
	* {9, 7, 2}
	* {9, 5, 3, 1}
	* {8, 7, 3}
	* {8, 7, 2, 1}
	* {8, 5, 3, 2}
	* {7, 5, 3, 2, 1}
	*/
	
	#include <stdio.h>
	#include <stdlib.h>
	#include <memory.h>
	
	#define END_OF_ARRAY(idx, lenth_of_array) (idx)==((lenth_of_array)-1)
	#define EMPTY(stack,top) ((top)==0)
	#define PRINT_STK(arr, stack,top) do{printf("{");\
	 for(int j = 0; j<top; ++j) {\
	 printf("%d, ", arr[stack[j]]); }}while(0);
	
	#define PUSH_STK(stack,v, top) do{stack[*(top)]=v; ++*(top);}while(0);
	
	
	int continuous_pop_out(int stack[], // in
	 int *_top); // out
	
	/*
	* Return the sum of the stack,
	* Only invoke after continuous_pop_out()
	*/
	int cal_sum(int stack[], // in
	 int arr[], // in
	 int top) // in
	{
	 int ret = 0;
	 for( int i=0; i<top; ++i) {
	 ret += arr[stack[i]];
	 }
	 return ret;
	}
	
	void gen_subset(int a[], // in, full set, should be a descending positive array
	 int len, // in, size of the set
	 int target) // in
	{
	 int *stack = (int*)malloc(sizeof(int)*(len+1)); // store index of the array
	 memset(stack, 0x0, sizeof(int)* len);
	 int _top = 0; // top of stack
	 int _sum =0;
	
	 int sum_temp = 0;
	 int hit_cnt = 0; // hit count
	
	 for( int i=0; i<len; ++i) {
	 sum_temp += a[i];
	 if( sum_temp>target ) {
	 sum_temp = _sum; // restore
	 }
	 else if( sum_temp==target ){
	 PRINT_STK(a, stack, _top);
	 printf("%d, }\n", a[i]);
	 ++hit_cnt;
	
	 sum_temp = _sum; // restore
	 }
	 else { // sum_temp < target
	 _sum = sum_temp;
	 PUSH_STK(stack, i, &_top);
	 }
	
	 if( END_OF_ARRAY(i, len) ) {
	 PUSH_STK(stack, i, &_top);
	 i = continuous_pop_out(stack, &_top);
	 if (i==-1) {
	 break;
	 }
	 _sum = cal_sum(stack, a, _top);
	 sum_temp = _sum;
	 }
	 }
	 printf("There exists %d subset fulfil target %d\n", hit_cnt, target);
	 free(stack);
	}
	/*
	* Continous pop out,
	* pop out the continous part backwards, besides of this,
	* also pop out the first incontinous element, and return the larger
	* neibougher of it.
	*
	* stack_before = {1, 4, 5, 6}, _top = 4, after continous pop out
	* stack_after = {}, _top = 0, return 2,
	*
	* stack_before = {1, 4, 6, 7}, _top = 4, after continous pop out
	* stack_after = {1}, _top = 1, return 5,
	*
	* stack_before = {1, 3}, _top = 2, after continous pop out
	* stack_after = {}, _top = 0, return 2
	*
	* stack_before = {1, 2}, _top = 2, after continous pop out
	* stack_after = {}, _top = 0, return -1
	*
	* stack_before = {5, 6}, _top = 2, after continous pop out
	* stack_after = {}, _top = 0, return -1
	*
	* stack_before = {1}, _top = 1, after continous pop out
	* stack_after = {}, _top = 0, return -1
	*/
	int continuous_pop_out(int stack[], // in
	 int *top ) // out
	{
	 if(*top<=1) { // {} or {1}
	 *top = 0;
	 return -1;
	 }
	
	 int gap_gt1_found = 0; // =1 means finding gap greater than 1, say 4, 2, 1
	
	 do {
	 --*top;
	 if( (stack[*top]-stack[*top-1])>1 ) {
	 gap_gt1_found = 1;
	 break;
	 }
	 } while (*top>1);
	
	 --*top;
	 if (gap_gt1_found) {
	 return stack[*top];
	 }
	 else {
	 return -1;
	 }
	}
	
	int descending_check(int a[], int l)
	{
	 for( int i=0; i<l-1; ++i) {
	 if( a[i]<a[i+1] ){
	 printf("ascend found in %d, %d\n", a[i], a[i+1]);
	 return 0;
	 }
	 }
	 return 1;
	}
	void gen_subset_UT(void)
	{
	 //int arr[] = {3, 2, 1,}; int TARGET = 6;
	 //int arr[] = {3, 2, 1,}; int TARGET = 7;
	 //int arr[] = {11, 9, 8, 7, 5, 4, 3, 2, 1,}; int TARGET = 18;
	 //int arr[] = {20, 14, 9, 8, 7, 5,};int TARGET = 21;
	
	 int l = sizeof(arr)/sizeof(arr[0]);
	 if(!descending_check(arr, l)) {
	 return;
	 }
	 gen_subset(arr, l,TARGET);
	}
	int main(void)
	{
	 gen_subset_UT();
	 exit(0);
	}

试试其它关键字

　子集　

同语言下

可能有用的

黃偉達贡献的其它代码(1)

.从给定的集合中罗列出符合条件的子集