Path: news.mathworks.com!not-for-mail From: <HIDDEN> Newsgroups: comp.soft-sys.matlab Subject: Re: list of all possible subsets of a set Date: Sat, 18 Dec 2010 19:57:05 +0000 (UTC) Organization: The MathWorks, Inc. Lines: 34 Message-ID: <iej3mh$7pa$1@fred.mathworks.com> References: <iegol3$iva$1@fred.mathworks.com> <ieht76$9dk$1@fred.mathworks.com> Reply-To: <HIDDEN> NNTP-Posting-Host: webapp-05-blr.mathworks.com Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Trace: fred.mathworks.com 1292702225 7978 172.30.248.35 (18 Dec 2010 19:57:05 GMT) X-Complaints-To: news@mathworks.com NNTP-Posting-Date: Sat, 18 Dec 2010 19:57:05 +0000 (UTC) X-Newsreader: MATLAB Central Newsreader 1187260 Xref: news.mathworks.com comp.soft-sys.matlab:696597 "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ieht76$9dk$1@fred.mathworks.com>... > Again this is called *subdivision* problem, not subset, because the split happens in order. Subset is a random selection within the set. > > I think I already suggest to use allVL1 function on FEX > > n=5 > k=3 > > % Engine > s = allVL1(k,n-k)+1; > splitfun = @(p) mat2cell(1:n,1,p); > c = arrayfun(@(i) splitfun(s(i,:)), 1:size(s,1), 'unif', 0); > > % display > for ci=c > cellfun(@(a) fprintf('%s ', mat2str(a)), ci{1}); > fprintf('\n'); > end > > 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 > [1 2 3] 4 5 > > Bruno - - - - - - - - - - A couple of points, Bruno. Antonis' request for "all possible subsets of a set" is actually not far from an accurate description of what is being sought. In the example you give for n = 5 and k = 3, one can consider that it is the four spaces between the five successive integers that constitute the "set" and that we seek subsets consisting of any two spaces among these as inner subdivision points. Hence the total number possible is (5-1)!/(3-1)!/(5-3)! = 6, which is the number of possibilities you obtained. The second point is that the condition "all subsets should have at least two elements" was placed on the selection, so that in fact there would really be no solutions for the n = 5 and k = 3 case. However, even with this restriction it can be regarded as a search for possible subsets of a given set. Suppose that n = 12 and k = 4. For every four subdivisions of the integers 1:12 in which each subdivision has a length of at least two we can always shorten each subdivision's length by one and adjust the values within so as to remain successive integers and we then have a unique subdivision of the integers 1:8 in which there is no restriction as to smallest length, the number of which as we have seen would be (8-1)!/(4-1)!/(8-4)! = 35. Conversely, for each of these 35 subdivisions we can increase each subdivision length by one and arrive at a unique subdivision of 1:12 satisfying the required condition, which gives us a one-to-one mapping between the two kinds of subdivisions and means that there are also 35 of the latter kind. Therefore this problem is in an indirect sense a search for subsets of a given "set" provided these sets are interpreted appropriately. Roger Stafford