listing all subsets of a given set

  • Permalink
  • submit to reddit
  • Email
  • Follow


Hi All,

Is there a function in MATLAB that produces all subsets of a given
set?

Or alternatively, what is an efficient way to list all subsets in
MATLAB?

The original set is a vector of indices (integers).

(context: I need this for some model-selection experiments in
regression analysis.)
0
Reply mahani (4) 9/4/2004 8:47:27 PM

See related articles to this posting


I wrote a simple recursive function that does the job with the
following performance compared to "perms" in MATLAB:

Number Number
of of time time
elements repetitions perms my-function
------------------------------------------
% 4 1000 0.2 0.23
% 5 1000 0.36 0.491
% 6 1000 0.851 1.022
% 7 1000 7.291 2.013
% 8 100 6.119 0.41
% 9 10 7.041 0.09

(Of course, for n>4 the two are not directly comparable: 2^5=32
5!=120)

If there are faster algorithms please let me know.

reza

reza mahani wrote:
>
>
> Hi All,
>
> Is there a function in MATLAB that produces all subsets of a given
> set?
>
> Or alternatively, what is an efficient way to list all subsets in
> MATLAB?
>
> The original set is a vector of indices (integers).
>
> (context: I need this for some model-selection experiments in
> regression analysis.)
0
Reply mahani (4) 9/5/2004 2:17:23 AM

reza:
<SNIP favorably compares his/her algo to ML's <perms> and
asks for even better ways of doing it...

well, could you show CSSM your code?
us
0
Reply us1 (8054) 9/5/2004 2:23:17 AM

function S = AllSubsets(V)
% 9/4/04: [Reza Mahani]

% Lists all subsets of a set given by the vector V of length
n.

% Assumption: No "nan" in V.

% I use a "recursive" algorithm, AllSubsets call itself on
one-element-smaller subsets.

% CALL: S = AllSubsets(V)

[m n] = size(V);

if m>n, n=m; V=V'; end % makes V a row vector

S = nan*zeros(2^n,n); % initialization

%

i0 = 1;

%

if max(m,n)==1

    S(i0,:) = V;

    return

end

if n==2

    S(i0:i0+2,:) = [V ; V(1) nan ; nan V(2)];

    return

end

for i=1:(n-1)

    S1 = AllSubsets(V(i+1:n));

    S(i0:i0+2^(n-i)-1,i:n) = [ones(2^(n-i),1)*V(i) , S1];

    i0 = i0 + 2^(n-i);

end

S(i0,n) = V(n);

return
0
Reply mahani (4) 9/5/2004 2:33:59 AM

I just found out how stupid was my question. The following line gives
the result:

---------------------------------------

function SI = AllSubsets2(n)

SI = dec2bin(0:2^n-1,n);

---------------------------------------

Yes, just one line. However, my previous code was not very bad, see
how the two are compared:

      n repetitions first second
    3.0000 100.0000 0.0100 0.0100
    4.0000 100.0000 0.0200 0.0200
    5.0000 100.0000 0.0500 0.0100
    6.0000 100.0000 0.1010 0.0200
    7.0000 100.0000 0.2010 0.0400
    8.0000 100.0000 0.4110 0.0600
0
Reply mahani (4) 9/5/2004 8:22:16 PM
comp.soft-sys.matlab 203181 articles. 525 followers. Post

4 Replies
570 Views

Similar Articles

[PageSpeed] 59


  • Permalink
  • submit to reddit
  • Email
  • Follow


Reply:

Similar Artilces:

list of all possible subsets of a set
I want to divide an array [1 .. N] all integers and array is sorted into k segments. The output should be a list of all possible k-subset no permutation allowed All subsets should have at least two elements but this is easy to do. f.e. k=2, N=5 ===> a=[1 2 3 4 5] [1] [2 3 4 5] less than 2 elements in set - delete [1 2 3 4] [5] less than 2 elements in set - delete [1 2] [3 4 5] [1 2 3] [4 5] k=3 [1] [2 3] [4 5] [1] [2 3 4] [5] [1] [2] [3 4 5] [1 2] [3] [4 5] [1 2 3] [ 4] [5] (actually for this case there is no solution - all cases have one subset of one element. ...

Find all subset of given set in a table
Hi all, i have a problem, i have a table like this: A | B ------------ 1 | 1 1 | 2 2 | 1 2 | 4 2 | 5 3 | 3 and a given set like C=('1', '2', '3'). I would to retrieve all A where B of A is a subset of the set C, in this example the result will be 1 and 3. Is this possible with low complexity and with a single query? Thanks, Igor Igor wrote: > Hi all, > > i have a problem, i have a table like this: > > A | B > ------------ > 1 | 1 > 1 | 2 > 2 | 1 > 2 | 4 > 2 | 5 > 3 | 3 >...

list of unique non-subset sets
Hi, I have many set objects some of which can contain same group of object while others can be subset of the other. Given a list of sets, I need to get a list of unique sets such that non of the set is an subset of another or contain exactly the same members. Tried to do the following: s1=set(['a','b','c']) s2=set(['a','c']) s3=set(['a','d','e','f']) s4=set(['r','k','l']) s5=set(['r','k','l']) L=[s1,s2,s3,s4,s5] ----------------------- > cleaned-up list should contain s1,...

Calculate the Correlation Coefficient of Subsets of a given set
Hi guys I wanna calculate the correlation coefficient of all subsets of a given sets. I know how I can calculate the CC of each subset but the problem is that how I can extract all the subsets and found each subset contains which members of set. Best Regards Mojgan "Mojgan " <ariamahsa@yahoo.com> wrote in message <kkd1fk$i0u$1@newscl01ah.mathworks.com>... > Hi guys > > I wanna calculate the correlation coefficient of all subsets of a given sets. > I know how I can calculate the CC of each subset but the problem is that how I can extract all the ...

set a attribute to random values in a given list
Hi, I like to have a SQL script which could update a table to set one attribute to a random value picked from a given list. The prototyping code is as below: select @value_list = ('John', 'David', 'Mathew', 'Paul') .... update EMP set emp_name = @random_name where ... where random name is randomly got from the given list. Of course there will be a cursor so that different row may have different random name but not necessary unique. Also the attribute and the list could be any valid common SQL data types Thanks! Ximing "Ximing Zheng" <xz...

Breaking Python list into set-length list of lists
Hey everyone-- I'm pretty new to Python, & I need to do something that's incredibly simple, but combing my Python Cookbook & googling hasn't helped me out too much yet, and my brain is very, very tired & flaccid @ the moment.... I have a list of objects, simply called "list". I need to break it into an array (list of lists) wherein each sublist is the length of the variable "items_per_page". So array[0] would go from array[0][0] to array[0][items_per_page], then bump up to array[1][0] - array[1] [items_per_page], until all the items in the origin...

function for searching a given path list for a given file
Hi, I am looking for a c callable function to search a path list for a given file. Many thanks in advance, Aaron On 7/28/2010 5:22 PM, Aaron Gray wrote: > Hi, > > I am looking for a c callable function to search a path list for a given > file. I think what you are after is globbing capabilities. http://www.gnu.org/s/libc/manual/html_node/Globbing.html#Globbing Does that link give you a head start for what you want? ...

How to list all files with an ACL and also list the ACL settings
Hi, I am using AIX 5.3 with MP 7 and I am investigating the use of ACL=92s to assist in setting various security constraints. I have found that you can use ls and find to obtain a list of the objects that have ACL=92s applied to them. The command =93find=94 with the =93-ea=94 option appears to be the better option of the two. My question is: Is there any tool available on AIX that will keep a list of the objects and their applied ACL=92s in a file or files. I could write a script to do all of this by making use of find and aclget. However if there is already a tool or script etc that is...

Set / List
The most common implementation of Set is HashSet. Why did they create this set backed by a Map, when they could have extended ArrayList and just overridden the add(Object obj) method ? In article <zLGdnZkSNY_SBQ2iRVn-sw@giganews.com>, Andrew Smith wrote: > The most common implementation of Set is HashSet. Why did they create this > set backed by a Map, when they could have extended ArrayList and just > overridden the add(Object obj) method ? Because it makes for an interesting question to ask on homework problems? -- ..:[ dave benjamin (ramenboy) -:- www.ramenfest.com -:-...

sets and subsets
By using lists, I can create sets of number. Suppose I have three lists. One list is the super-set, one is a set that contains all the numbers (just like the super-set) and the last is sub-set of the super-set. For example: a = [1,2,3,4,5] # The super-set. b = [1,2,3,4,5] # Looks just like the super-set, but it's not. c = [2,4] # A sub-set I'd like to remove 2 & 4 from set b BECAUSE they are present in set c... this would make the sets look like this: a = [1,2,3,4,5] b = [1,3,5] c = [2,4] How do I test set c to find what it contains and then look at set b to see if it cont...

subsets of a set
In page 226 of John Gray's Mastering Mathematica (unfortunately I had the 1994's edition) there is the following exercise: "Given a finite set (presented as a list) and an integer k find all k-element subsets of the set". There is one solution however for practicing (no there is no professor that asked me this for homeworks! I work individually...) I search for other So considering the following list lst = Tuples[Range[7], 3]; I can erase the sublists containg at least two same elements Cases[lst, {x_, y_, z_} /; x ߉ y && x ߉ z && y ߉ ...

List Subsets
Hi, I'm hoping you could show me examples of how a functional/declarative language could be used to consicely describe resticted subsets of elements. I'm looking for a 'specification' style definition so any ideas/input would be very welcome. Thanks for your time, Simon. -- Say I have a list of items which is considered ordered... ['iA', 'iB', 'iC', 'iD', 'iE', 'iF'] ( which could also be enumerated if needed... [(0,'iA'), (1,'iB'), (2,'iC'), (3,'iD'), (4,'iE'), (5,'iF')] ) ...

Subsets from a set
Hello, I was just playing with some coding problem, when I figured out I'll need to retrieve all the subsets from a given set. As I'm not very good at solving that kind of algorithms, the code produced would get too dirty and slow, that's why I'm wondering if someone can provide me a simple algorithm procedure or code snippet. The code I'm playing with is made in C and uses arrays to emulate sets. stdazi@gmail.com wrote: > Hello, > > I was just playing with some coding problem, when I figured out I'll > need to retrieve all the subsets from a given set. A...

list subsetting
Hello All, Say I have a list like this: a = [0 , 1, 3.14, 20, 8, 8, 3.14] Is there a simple python way to count the number of 3.14's in the list in one statement? In R I do like this a = c(0 , 1, 3.14, 20, 8, 8, 3.14) length( a[ a[]==3.14 ] ) How do I do that in standard python? (Note that this is just an example, I do not mean to use == in floating point operations.) Thank you culpritNr1 -- View this message in context: http://www.nabble.com/list-subsetting-tp21593123p21593123.html Sent from the Python - python-list mailing list archive at Nabble.com. On Jan 21, 4:53=A0pm, ...

programmatically determine if argument is list compatible to a given lambda list
I'd like to write a function which at run-time will determine whether a given list of arguments is compatible to a given lambda list. For example. (callable-as '(3) '(x)) ==> return t because you CAN apply (lambda (x) nil) to '(3) (callable-as '(3) '(x &rest y)) ==> return t because you CAN apply (lambda (x &rest y) nil) to '(3) (callable-as '(3) '(x y)) ==> return nil because you CANNOT apply (lambda (x y) nil) to '(3) Here is my attempt which fails miserably. (defun callable-as (arg-list lambda-list) (unwind-protect (appl...

generate all possible strings of given length given a set of characters
Hi everybody! I am just at the beginning as a programmer, so maybe this is a stupid question...Anyway,I need to write a function in C to generate generate all possible strings of given length given a set of characters (allowing repetitions of the same character) For example given the characters 'E' and 'H' and maximum length 3 the function should generate the sequences H E HH EE HE EH HHH EEE HEE EHE EEH HHE HEH EHH Anybody can help? "chiara" <chiaramicca@gmail.com> wrote in message news:1128357679.432094.39470@g47g2000cwa.googlegroups.com... .... > For...

List Subsets
Hi, I'm hoping you could show me examples of how a functional/declarative language could be used to consicely describe resticted subsets of elements. I'm looking for a 'specification' style definition so any ideas/input would be very welcome. Thanks for your time, Simon. -- Say I have a list of items which is considered ordered... ['iA', 'iB', 'iC', 'iD', 'iE', 'iF'] ( which could also be enumerated if needed... [(0,'iA'), (1,'iB'), (2,'iC'), (3,'iD'), (4,'iE'), (5,'iF')] ) ...

More on lists and sets
I think we've recently discussed lists and sets at length in the context of the problem domain. IMO, we can give that a rest, at least for a while. We've discussed how a set (or pizza toppings) might be stored in a list, for the sake of convenience, but the retrieve dand used as if it were a set. We've also discussed how a set of tuples, with one attribute thrown in for sequencing purposes, can, for all intents and purposes, be treated as if if were a list. I want to turn my attention to the discussion of lists and sets from the logical and or physical design perspect...

Sets and Lists, again
Recently, in a thread on implementing both threads and lists in a programming language, the example of lists or sets of Presidents arose. I mentioned that in a list of presidents, Grover Cleveland would appear once, but in a list of presidencies, he would appear twice. Bob Badour asked what purppose would be served by a list of presidents, or words to that effect. I'm interested. If one could have a set of presidents, why would one ever want a list? In general, if a language implements sets, why would the same language need to also implement lists? What does it buy you...

convert list of strings to set of regexes; convert list of strings to trie
Hello, I need a function that converts a list into a set of regexes. Like so: string_list = ["blaa", "blab", "raaa", "rabb"] print string_list2regexes(string_list) This should return something like: ["bla(a|b)", "ra(aa|bb)"] I am aware of the fact that converting the list to a *trie* would almost do the job. But I couldn't find anything about Python modules that produce tries. Are there any modules that I could use? Or do I have to implement it myself? Klaus [Klaus Neuner] > I need a function that converts a li...

Is there any advantage or disadvantage to using sets over list comps to ensure a list of unique entries?
Howdy guys, I am new. I've been converting lists to sets, then back to lists again to get unique lists. e.g Python 2.5.2 (r252:60911, Jan 20 2010, 21:48:48) [GCC 4.2.4 (Ubuntu 4.2.4-1ubuntu3)] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> foo = ['1','2','3'] >>> bar = ['2','5'] >>> foo.extend(bar) >>> foo = list(set(foo)) >>> foo ['1', '3', '2', '5'] I used to use list comps to do this instead....

Can training set be divided further into subsets of training set for training neural networks?
I have read on some forum that there are training methods. one is to train = NN on whole training data at once, 2nd is to train NN in parts like first f= rom 1 to 1000 samples, then 1 to 2000 samples and so on. 3rd is to train NN= in parts like first from 1 to 1000 samples, then 1000 to 2000 samples and = so on. I want to ask that whether all these methods correct and which to us= e when?? On Fri, 4 Jul 2014 01:47:17 -0700 (PDT), Aamir Nawaz <engr.aamir09@gmail.com> wrote: >I have read on some forum that there are training methods. one is to train NN on whole training data...

subseting inquiry data set CO to get matches and nomatches with reference data set EA
Suppose I have two data sets: CO and EA and I want to find the subset of CO that are matches to EA and likewise the subset of CO that aren't matches to EA The following code works. However when CO and EA are over a million observations the proc sql procedure is very very very slow. I want to know if there is an optimized way to do what I am doing below: /*************CO *********************/ data home.CO; input fname $ lname $; datalines; John Smith Mary Jane Will Smith Eric Manelow Christina Aguilera ; data home.CO; set home.CO; FL = CATS(fname,lname); run; data home.EA; inpu...

wxMac help on open file dialog to set into List mode (path: /.../myapp.app/Contents/MacOS/Setting )
------_=_NextPart_001_01C6D8FF.13861A3B Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: quoted-printable Hi, =20 Since I have put setting folder under app bundle, I run into a problem At opening a file under the path /.../myapp.app/Contents/MacOS/Setting/. =20 If Finder is set to Column, the Finder window will not show the path under the app Bundle further. i.e., the window is not showing any thing under the bundle. =20 If Finder is set to List, the Setting folder shows. =20 =20 How can I set file dialog window to sh...