Solved

Sub sets of a set

Posted on 1997-07-20
2
239 Views
Last Modified: 2012-05-05
I need a nice alogrithm to find all the sub sets of various sets of integers. Anyone know an elagent way of doing this. The set I am working with is stored simply as an integer array.
0
Comment
Question by:simonc
2 Comments
 
LVL 1

Accepted Solution

by:
8051 earned 100 total points
ID: 1252437
The undefined "subset" means that you can not use
tricks like a bit tests and a lot of things, can
be implemented if you have a constant subset. OK,
the only thing possible in this case - to sort
subset and check each element of set for highest
and lowest range of subset.

If you can sort set - sort it, find a range where
elements can be a members of subset and check only
this elements.

Another way (if you have enough memory, for bytes
for example) to create array of mask that keeps 1
for each element that is a member.

//example for bytes

unsigned char member[0x100];

void make_subset(char * subset, int len)
{
   int tmp;
   for (tmp=0;tmp<0x100;tmp++) member[tmp]=0;
   for (tmp=0;tmp<len;tmp++) member[subset[tmp]]=1;
}

int is_member(unsigned char x)
{
   return member[x];
}

Look Borland C 3.1 RTL how to use it with maximum
performance.

Regards

0
 
LVL 84

Expert Comment

by:ozo
ID: 1252438
int set[]={...};
for( i=0;i < 1<<sizeof(set)/sizeof(set[0]); i++ ){
/* if this overflows, you'd never have finished finding all subsets anyway*/
        printf("subset %d:",i);
       for( j=0; j<sizeof(set)/sizeof(set[0]); j+= 1){
                if( i&(1<<j) ){ print(" %d",set[j]); }
        }
      printf("\n");
}
0

Featured Post

Live: Real-Time Solutions, Start Here

Receive instant 1:1 support from technology experts, using our real-time conversation and whiteboard interface. Your first 5 minutes are always free.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

815 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now