Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
list of all possible subsets of a set

Subject: list of all possible subsets of a set

From: Antonis

Date: 17 Dec, 2010 22:36:20

Message: 1 of 5

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.

any help appreciated.

Subject: list of all possible subsets of a set

From: Roger Stafford

Date: 18 Dec, 2010 05:50:27

Message: 2 of 5

"Antonis " <trelof_avoidspamremovethis@gmail.com> wrote in message <iegol3$iva$1@fred.mathworks.com>...
> 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.
>
> any help appreciated.
- - - - - - - - - - - -
  You can use 'nchoosek' to do this. I am not sure how you want the segments displayed. I have chosen to use the rows of arrays b and e to give the indices of the segments' beginnings and ends, respectively. For example with N = 11 and k = 3 the segments [1 2],[3 4 5 6],[7 8 9 10 11] would be indicated by a row of b equal to [1 3 7] and a corresponding row of e equal to [2 6 11].

 c = bsxfun(@plus,nchoosek(1:N-k-1,k-1),1:k-1);
 b = [repmat(1,size(c,1),1),c+1];
 e = [c,repmat(N,size(c,1),1)];

For this code to work, you must have N >= 2*k. Otherwise there would be no possible solutions. Also I have assumed in the code you want at least two segments so that k must be greater than 1. (Otherwise the problem is trivial.)

  Warning: I have made an assumption here about the 'nchoosek' routine which is not specified but only hinted at in their documentation. I assume that the subsets in their input vector argument will not be given out of order in the rows of the output. That is, with the argument vector 1:N-k-1 I assume that each row of the output will have a subset of k-1 of these still in ascending order.

  Mathworks is sometimes reluctant to commit themselves as to exactly how their algorithms function but I rather think this particular assumption is valid. Perhaps one of their personnel would be willing to commit them on this point. If that assumption were to prove false, then an added sort operation would be necessary in the above code.

Roger Stafford

Subject: list of all possible subsets of a set

From: Bruno Luong

Date: 18 Dec, 2010 09:00:22

Message: 3 of 5

"Antonis " <trelof_avoidspamremovethis@gmail.com> wrote in message <iegol3$iva$1@fred.mathworks.com>...
> 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.
>
> any help appreciated.

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

Subject: list of all possible subsets of a set

From: Roger Stafford

Date: 18 Dec, 2010 19:57:05

Message: 4 of 5

"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

Subject: list of all possible subsets of a set

From: Bruno Luong

Date: 18 Dec, 2010 20:38:04

Message: 5 of 5

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <iej3mh$7pa$1@fred.mathworks.com>...
> "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

Hi Roger, yes I do understand the relation between both methods. But I believe Antonis uses the word "subset" to designate the sub-interval, and not the set of inner break points.

To me finding all subsets of a set is an entirely different problem we have few old posts on this topics a year ago, and we had a great fun to make a code (especially with Matt Fig).

If the requirement is at least 2 elements by interval, then the only change in my code is this first command that change to:

s = allVL1(k,n-2*k)+2;

Bruno

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us