COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### problem with subsets

• Email
• Follow

```Hi everyone,

I'm struggling to write a set of equations. Suppose I have the vector
N={1  2 3 ... 10}
and I write the loop

for i=1:1:N
fprintf(' + x%d ', i);
end
fprintf(' = 1');

But now I need to write the same equation for all possible subsets of
N, ranging from 2 to 8 elements.
So it can be only elements {1, 2}, {1, 3}, ... {5, 10}, up to all
combinations until 8 elements.

Any ideas of hints are very welcome.
Thnaks
```
 0
Reply leandro.cc (1) 4/27/2010 4:36:43 PM

See related articles to this posting

```Leandro Callegari Coelho wrote:
> Hi everyone,
>
> I'm struggling to write a set of equations. Suppose I have the vector
> N={1  2 3 ... 10}
> and I write the loop
>
> for i=1:1:N
>    fprintf(' + x%d ', i);
> end
> fprintf(' = 1');
>
> But now I need to write the same equation for all possible subsets of
> N, ranging from 2 to 8 elements.
> So it can be only elements {1, 2}, {1, 3}, ... {5, 10}, up to all
> combinations until 8 elements.
>
> Any ideas of hints are very welcome.

Consider the results of the following...

for idx=1:N
nchoosek(1:N,idx)
end

You might find w/ N rather small first more easily enlightening... :)
--
```
 0

```You need to give an example which doesn't fail.  Perhaps a simpler version of your actual problem, with the inputs and outputs shown explicitly, would help.

>> N = {1 2 3 4 5 6 7 8 9 10};
>> for i=1:1:N
fprintf(' + x%d ', i);
end
fprintf(' = 1');
??? Undefined function or method '_colonobj' for input arguments of type 'cell'.

>>
```
 0

```On Apr 27, 8:55=A0am, "Matt Fig" <spama...@yahoo.com> wrote:
> You need to give an example which doesn't fail. =A0Perhaps a simpler vers=
ion of your actual problem, with the inputs and outputs shown explicitly, w=
ould help.
>
> >> N =3D {1 2 3 4 5 6 7 8 9 10};
> >> for i=3D1:1:N
>
> =A0 =A0fprintf(' + x%d ', i);
> end
> fprintf(' =3D 1');
> ??? Undefined function or method '_colonobj' for input arguments of type =
'cell'.
>
>

Matt, here's a simple version (believe me, the equations I'm trying to
write are much more complex than this).

N=3D5
for i=3D1:1:N
fprintf(' + x%d', i);
end

This will write:
x1 + x2 + x3 + x4 + x5

Now I want something to write approx 2^N equations, the output would
be

x1 + x2
x1 + x3
x1 + x4
x1 + x5
x2 + x3
....
than w/ 3 elements:
x1 + x2 + x3
x1 + x2 + x4
x1 + x2 + x5
....

If N is 10, than I need all possible combinations from 2 to 8
elements(2 to (N-2) elements).

I'll try with dbp's suggestion (thanks!)

Regards
```
 0

```Something like this:

N = 10;

for jj = 2:8
T = nchoosek(1:N,jj);

for ii = 1:size(T,1)
fprintf(['x%i',repmat(' + x%i',1,size(T,2)-1),'\n'],T(ii,:))
end
fprintf('\n\n\n')
end
```
 0

```On Apr 27, 9:34=A0am, "Matt Fig" <spama...@yahoo.com> wrote:
> Something like this:
>
> N =3D 10;
>
> for jj =3D 2:8
> =A0 =A0 T =3D nchoosek(1:N,jj);
>
> =A0 =A0 for ii =3D 1:size(T,1)
> =A0 =A0 =A0 =A0 fprintf(['x%i',repmat(' + x%i',1,size(T,2)-1),'\n'],T(ii,=
:))
> =A0 =A0 end
> =A0 =A0 fprintf('\n\n\n')
> end

Matt, thanks a lot. It works, I just need to adapt it to my equations.
```
 0

```Leandro Callegari Coelho wrote:
> On Apr 27, 9:34 am, "Matt Fig" <spama...@yahoo.com> wrote:
>> Something like this:
>>
>> N = 10;
>>
>> for jj = 2:8
>>     T = nchoosek(1:N,jj);
....
>
> Matt, thanks a lot. It works, I just need to adapt it to my equations.
> I really appreciate your attention.

for jj = 2:8
T = nchoosek(1:N,jj);

looks somehow remarkably similar to dpb's hint to explore

for idx=1:N
nchoosek(1:N,idx)

:)

--

```
 0

```dpb <none@non.net> wrote in message <hr7hat\$7kd\$1@news.eternal-september.org>...
> Leandro Callegari Coelho wrote:
> > On Apr 27, 9:34 am, "Matt Fig" <spama...@yahoo.com> wrote:
> >> Something like this:
> >>
> >> N = 10;
> >>
> >> for jj = 2:8
> >>     T = nchoosek(1:N,jj);
> ...
> >
> > Matt, thanks a lot. It works, I just need to adapt it to my equations.
> > I really appreciate your attention.
>
> for jj = 2:8
>       T = nchoosek(1:N,jj);
>
> looks somehow remarkably similar to dpb's hint to explore
>
> for idx=1:N
>    nchoosek(1:N,idx)
>
> :)
>
> --
I went with
N=[1 2 3 4];
len=length(N);
for i =0:1:2^(len)-1
subset=dec2bin(i,len)=='1';
for j= N(subset)
fprintf(' + x%d ', j);
end
fprintf('=1\n');
end

if you don't want the empty set (ie =1) just switch the loop over i to start with 1
I also changed N from a struct to a vector
```
 0

```Guys, since you're posting here again, I'll ask your help once again.
Turns out the equation I'm trying to write is way too hard to me.

Take a look at the equation here: http://twitpic.com/1iy2bu
Using your ideas I could almost finish the left side.

Explaining from the right to the left:
Big-fancy t can be small, i.e 3
Big-fancy M is what we're using N here, so it can be something like 5.

(for the ones that are curious this equation avoids subtours on a
vehicle routing model)

Anyone with enough time to tackle this?
```
 0

```On Apr 27, 1:35=A0pm, Leandro Callegari Coelho <leandro...@gmail.com>
wrote:
> Guys, since you're posting here again, I'll ask your help once again.
> Turns out the equation I'm trying to write is way too hard to me.
>
> Take a look at the equation here:http://twitpic.com/1iy2bu
> Using your ideas I could almost finish the left side.
>
> Explaining from the right to the left:
> Big-fancy t can be small, i.e 3
> Big-fancy M is what we're using N here, so it can be something like 5.
>
> (for the ones that are curious this equation avoids subtours on a
> vehicle routing model)
>
> Anyone with enough time to tackle this?

bump
```
 0

9 Replies
435 Views

Similar Articles

12/19/2013 11:17:33 PM
page loaded in 37457 ms. (0)

Similar Artilces:

Subset Sum Problem
Here is a problem you don't always see in VB... Given a set of numbers, e.g. 1 to 10 your goal is to find all the possible combinations that make the sum 11. Repetition is not allowed, i.e. you can't do a 1+1 and 1+2 = 2+1. Here is what I came up with, sort the data and create a tree and then follow down each limb till you hit the sum or go bust and roll back one step. Once you hit the number roll back two steps and continue down. Did anyone get that? Hope so =) And do this for every item in the set, the good thing is that as you do down the list in the set, the tree gets smaller. ...

ordered subset problem
I need to obtain all the ordered subsets of containing 7 elements from a list of 15 elements. From what I remember, the number of ordered sets is given by the formula numOfSets = 15! / (15-8)! = 32,432,400 Unfortunately, I'm not familiar with permutation algorithms. Could someone please point me in the right direction to solve this problem? John John Trunek wrote: > I need to obtain all the ordered subsets of containing 7 elements from a > list of 15 elements. From what I remember, the number of ordered sets is > given by the formula > numOfSets = 15! / (15-8...

Subset Sum Problem Algorithms
So I was thinking about the subset sum problem and the case where the subset is bounded to only two numbers. This case is obviously not np- complete. Anyway for the fastest way to solve this specific case is something I want to know. I'm unsure if there are any books that delve into it but I know on the internet there are some examples. For instance when asked to see if Z is in the subset of a set K with N numbers first sort the set and find the largest/smallest number and compare this with Z. IF it is greater, then increase the smaller number, if it is less then decrease the largest ...

Classic Subset problem... help needed
PLEASE SOS I need something that needs to be done by this 12th or 13th May . I want a C/c++ program for this problem. There are some sets of numbers given in the text files I have attached. I need to divide these sets into subsets (each set into max of 2 subsets).i.e. there can be max of 2 subsets for a given set.(either two subsets containing numbers or the set itself and a null subset)that is options can be Say for example in snort_13_dfa-nfa file, 1 indicates the index or serial number of number of sets in the file. You can ignore this. Now consider the first set [0 1]. Thi...

Embedding and subsetting fonts in a .pdf
Hi all, I have a problem embedding and subsetting fonts in a PDF. In particular, I can embed and subset all fonts correctly using Adobe Acrobat 6.0 but the ligatures like "fi", "fl", etc. dissapear when I embed the fonts. The document I�m using has been generated in latex using miktex 2.3 and WinEdt 5.3, creating firstly a .dvi, then a .ps and finally converting the .ps to .pdf using Acrobat Distiller 6.0. I hope somebody out there can have an answer for that. Thanks in advance. Antonio. ...

Imaginary Polynomial Time Algorithm for Subset sum Problem
Imaginary Polynomial Time Algorithm for Subset sum Problem This is a very abstract algorithm requiring a lot of imagination. It starts with an imaginary piece of infinitely large paper and an infinitely precise ruler with an automatic marking system. Say you wanted to mark the distance 6.5520525, it would automatically put a perfect precision mark at that point in ink. The paper is marked with an origin and single axis (forming a number line). Not only this but there exists two of these papers and a machine is created that can stamp one on top of another instantly transferring all the i...

Problem Combining 2 PDF Files: Same Subset fonts
Hello and thanks in advance, I'm using Acrobat 5 Professional ... I'm trying to combine 2 PDF files into 1 file (they are chapters of a book. I don't have the original files before they were made into a PDF.). But I get an error message: "These documents have subsets fonts with the same name, and cannot be merged." What can I do to solve this problem? ... Thanks again ... RW Hello, I had this problem last year and I solved it like this: 1- Use "extract pages" feature in Acrobat 5, to pull out the pages from the chapters that would not combine (or, if the...