Solved

Sub sets of a set

Posted on 1997-07-20
2
245 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
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

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
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…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.

689 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