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 (8053) 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 203807 articles. 537 followers. Post

4 Replies
701 Views

Similar Articles

[PageSpeed] 42


  • 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. ...

List of lists of lists of lists...
I would like to have a list of lists N times deep, and my solution is (in pseudocode): def deep(x): a=[x] return a mylist=[] for N: mylist=deep(mylist) Is there a more elegant way to do it? The maine idea is: from a list having the numbre of steps along N dimensions, generate a list with an item at each possible point. Example 1: N=2 list=[2,3] result=[[1,2],[1,2],[1,2]] Example 2: N=3 list=[3,1,2] result=[[[1,2,3]],[[1,2,3]]] -- Ángel Gutiérrez Rodríguez - agr@fq.uniovi.es Instituto de Ciencia de los Materiales de Madrid - CSIC SpLine - European Syncrothorn Radiat...

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...

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 ...

list of lists of lists ....
Hi, I have a list of data (type A) my list can includes element of type A or a lists, these list can includes element of type A or a lists, and so on ... is there a simple way to obtain a single list of all the elemets of type A ? thanks yomgui I forgot the most important, I am looking for a non recursive method. thanks yomgui yomgui wrote: > > Hi, > > I have a list of data (type A) > my list can includes element of type A or a lists, > these list can includes element of type A or a lists, and so on ... > > is there a simple way to obtain a single list of all...

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...

Sort a List, in a List of Lists of Lists
Dear Mathgroup, I have a lsit of Lists of Lists: {{{1,2},{2,1},{1,1}},{{1,1},{1,1},{1,2}},{{2,1},{2,2},{1,2}},{{2,2},{1,2},{2,2}},{{1,1},{2,1},{1,2}},{{1,2},{2,2},{2,2}}} I would like to sort the elements in the lowest level of brackets to give {{{1, 2}, {1, 2}, {1, 1}}, {{1, 1}, {1, 1}, {1, 2}}, {{1, 2}, {2, 2}, {1, 2}}, {{2, 2}, {1, 2}, {2, 2}}, {{1, 1}, {1, 2}, {1, 2}}, {{1, 2}, {2, 2}, {2, 2}}} i.e retaining the same structure with the paired elements in the original order. I can't seem to get the syntax right to do this apart from the obvious {{Sort[{1,...

Algorithm to combine or-sets of and-sets, where each element of an and-set is an or-set of and-sets
As part of an abduction procedure, see http://code.google.com/p/biohacker/source/browse/trunk/BPS/ltms/abduction.lisp if interested, I need to efficiently solve the following problem: Given an or-set of and-sets, for example, (:OR (:AND A B C) (:AND D E A)) and given a dictionary, where each element of an and-set is listed, with another or-set of and-sets as value, for example, A -> (:OR (:AND 1 2) (:AND 3 4)) B -> (:OR (:AND 2 3) (:AND 4)) C -> (:OR (:AND 1) (:AND 3)) D -> (:OR (:AND 1) (:AND 3 4)) E -> (:OR (:AND 1 2) (:AND 3)) find a new minimal or-set of and-set consistent,...

Re: Sort a List, in a List of Lists of Lists
On 11/13/10 at 12:59 AM, leigh.pascoe@inserm.fr wrote: >I have a lsit of Lists of Lists: >{{{1,2},{2,1},{1,1}},{{1,1},{1,1},{1,2}},{{2,1},{2,2},{1,2}},{{2,2}, >{1,2},{2,2}},{{1,1},{2,1},{1,2}},{{1,2},{2, 2},{2,2}}} >I would like to sort the elements in the lowest level of brackets to >give >{{{1, 2}, {1, 2}, {1, 1}}, {{1, 1}, {1, 1}, {1, 2}}, {{1, 2}, {2, >2}, {1, 2}}, {{2, 2}, {1, 2}, {2, 2}}, {{1, 1}, {1, 2}, {1, 2}}, >{{1, 2}, {2, 2}, {2, 2}}} >i.e retaining the same structure with the paired elements in the >original order. I can't seem...

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...

List of Atom or List of List??
how can detect some element of list is list o Atom?? for example when i try head (head p1) where p1=[[1,2],2] return 1 but when try head (head p1) where p1=[1,2] it returns Error plz help me..it my project and i have just 2 hours..:( i want to replace on Atom by another in list..for example: replace 1 2 [1,2] => [2,2] but sometime i have replace 1 2 [[1,2],2]=>[[2,2],2] i want to detect if first element of list is list then recurcively call head on that element.. is there any solutions?? On 8 Apr 2007 02:46:25 -0700, kheirandish.amin@gmail.com wrote: >how can detect some eleme...

convert list of lists to list
Is there a way to convert list_of_listsA to list_of_listsB, where one list in listof lists A is one element of listB? list_of_listsA: [['klas*', '*', '*'], ['mooi*', '*', '*', '*'], ['koe'], ['arm*', '*', '*(haar)'], ['groei*', '*', '*', '*', '*']] listB: ['klas* * *', 'mooi* * * *, 'koe', 'arm* * * (haar)', 'groei* * * * *'] Thankx! antar2 wrote: > Is there a way to convert list_of_listsA to list_of_listsB, where one >...

Extracting a List from a List of lists
Hi, I have an ArrayList of ArrayLists. I want to extract all the lists, but I dont know how many ArrayLists will be in the ArrayList. I know I can do it if i know how many lists are there using the ArrayList get() method. this is how i'm doing it List<String> list1 = new ArrayList<String>(); list1 = res.get(0); List<String> list1 = new ArrayList<String>(); list2 = res.get(1); List<String> list1 = new ArrayList<String>(); list3 = res.get(2); But if theres only two lists in the list i get a NullPointerException Is there any way i can loop through the l...

How to have a list of lists (or array of lists)
Hi, I want to have many lists, such as list0, list1, list2, ..., each one holding different number of items. Is there something like list[0] list[1] list[2] so that I can iterate through this list of lists? Thanks! bahoo On Apr 3, 7:12 pm, "bahoo" <b83503...@yahoo.com> wrote: > Hi, > > I want to have many lists, such as list0, list1, list2, ..., each one > holding different number of items. > Is there something like > list[0] > list[1] > list[2] > > so that I can iterate through this list of lists? > > Thanks! > bahoo listOfLists = [...

Copying a List to a List of Lists
Hi, I am having trouble with the following: I wish to have a list of lists of type Double called A. I then have a separate List of Doubles called B which i wish to add to A. I then want to be able to clear B and reuse it without clearing what I have added to A. Currently my code looks like: for(int i=0;i<seqLength;i++) { B.clear(); for(int j=i+1;j<seqLength;j++) { if(fourGameteTest(i,j)) { B.add(segPositions.get(j)); } } A.get(i).add(B); } However, it seems that due to, I guess the element held in A being a reference to the same pl...

lists of lists
I'm using C++ and I'm trying to create a list of a list and it won't let me create an iterator for it. if I do a list of an int, everything is fine. my syntax is list<list<string> > some_list; and my iterator would be someting like list<list>::Iterator blah; or maybe list<list<string> >::Iterator blah; ?? neither work, ofcourse. basicaly I'm trying to parse a text file, each line is token that contains tokens and I have a function that takes a string and returns the list of the tokens. so I have my the parent list to contain lists to t...

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 -:-...

Lists of list
Hi All I am having problem with delete line if its belong to another one , example ['0132442\n', '13\n', '24\n'] the 2nd and 3rd are already in the first line , how can do this !!! Thanks Mohammed Altaj wrote: > Hi All > > I am having problem with delete line if its belong to another one , example I think, you mean to remove all lines that are substrings of another line. l = ['0132442\n', '13\n', '24\n'] l = [e.strip() for e in l] i = 0 while True: try: for j in range(len(l)): if i == j: continue if l[j]...

list*list
There must be a better way to multiply the elements of one list by another: a = [1,2,3] b = [1,2,3] c = [] for i in range(len(a)): c.append(a[i]*b[i]) a = c print a [1, 4, 9] Perhaps a list comprehension or is this better addressed by NumPy? Thanks, jab > There must be a better way to multiply the elements of one list by > another: > > a = [1,2,3] > b = [1,2,3] > c = [] > for i in range(len(a)): > c.append(a[i]*b[i]) > a = c > print a > [1, 4, 9] > > Perhaps a list comprehension or is this better addressed by NumPy? First of all: it's ...

When is a List not a List?
g[x_, n_] := x^n FullForm[Table[g[x, n], {n, 1, 2}]] FullForm[{g[x, 1], g[x, 2]}] Plot[{g[x, 1], g[x, 2]}, {x, 0, 1}, PlotStyle -> {Red, Blue}] Plot[Table[g[x, n], {n, 1, 2}], {x, 0, 1}, PlotStyle -> {Red, Blue}] The FullForm[]s are identical. One Plot[] has red and blue curves; the other has two blue curves. Quirky! AES wrote: > g[x_, n_] := x^n > FullForm[Table[g[x, n], {n, 1, 2}]] > FullForm[{g[x, 1], g[x, 2]}] > Plot[{g[x, 1], g[x, 2]}, {x, 0, 1}, PlotStyle -> {Red, Blue}] > Plot[Table[g[x, n], {n, 1, 2}], {x, 0,...

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...