Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Re: Combinations with true and false

Reply
Thread Tools

Re: Combinations with true and false

 
 
Ben Pfaff
Guest
Posts: n/a
 
      10-27-2010
Max <(E-Mail Removed)/> writes:

> I have a set of variables and I want to find all of the
> combinations and the ways they can be true or false at the same
> time. E.g. if my set is (a, b, c) I want to get
>
> a
> !a
> b
> !b
> [...]
> a b
> !a !b
> [...]
> a b c
> !a !b !c


It sounds like you want to iterate over three possibilities for
each variable: false, true, and don't care. This should be
trivial with nested "for" loops, for a fixed number of variables,
and only a little harder if the number of variable is itself
variable.

This isn't really a C question.
--
Ben Pfaff
http://benpfaff.org
 
Reply With Quote
 
 
 
 
Chad
Guest
Posts: n/a
 
      10-31-2010
On Oct 27, 4:33*pm, "Trevor" <(E-Mail Removed)> wrote:
> "Ben Pfaff" <(E-Mail Removed)> wrote in message
>
> news:(E-Mail Removed)...
>
>
>
> > It sounds like you want to iterate over three possibilities for
> > each variable: false, true, and don't care.

>
> Yes!
>
> > *This should be
> > trivial with nested "for" loops, for a fixed number of variables,

>
> No!
>
> > and only a little harder if the number of variable is itself
> > variable.

>
> Just don't use recursion, though. That's all I ask.


Why not use recursion? I mean, it seems fairly simple finding all the
combinations of a string.
 
Reply With Quote
 
 
 
 
Chad
Guest
Posts: n/a
 
      10-31-2010
On Oct 31, 8:21*am, Chad <(E-Mail Removed)> wrote:
> On Oct 27, 4:33*pm, "Trevor" <(E-Mail Removed)> wrote:
>
>
>
> > "Ben Pfaff" <(E-Mail Removed)> wrote in message

>
> >news:(E-Mail Removed)...

>
> > > It sounds like you want to iterate over three possibilities for
> > > each variable: false, true, and don't care.

>
> > Yes!

>
> > > *This should be
> > > trivial with nested "for" loops, for a fixed number of variables,

>
> > No!

>
> > > and only a little harder if the number of variable is itself
> > > variable.

>
> > Just don't use recursion, though. That's all I ask.

>
> Why not use recursion? I mean, it seems fairly simple finding all the
> combinations of a string.


I mean, it seems fairly simple to find all the possible combinations
of a string using recursion.
 
Reply With Quote
 
Willem
Guest
Posts: n/a
 
      10-31-2010
Trevor wrote:
) It you use recursion, you don't get *any* of the results until you get *all*
) of the results.

False.

) You need to put all of the results in a data structure and return it, unless
) what you are doing with them is so trivial you can put it inside the
) function that gets them.

Equally false.

) The memory used is the size of the output.

Idem.

) You can't bail out early if you are looking for a particular combination.

Aaand false.

That's four for four. I think the second point is your main thinking
error, the rest are corollaries of that.

Doing something with the results can be as complicated as you
like inside 'the function that gets them'. Just call a function
'do_something_with_the_results', or provide a callback if you want
it to be generic. The function could, for example, return a boolean
that indicates bailing out early.

So, recursion it is then.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
 
Reply With Quote
 
Nick
Guest
Posts: n/a
 
      10-31-2010
Willem <(E-Mail Removed)> writes:

> Trevor wrote:
> ) It you use recursion, you don't get *any* of the results until you get *all*
> ) of the results.
>
> False.
>
> ) You need to put all of the results in a data structure and return it, unless
> ) what you are doing with them is so trivial you can put it inside the
> ) function that gets them.
>
> Equally false.
>
> ) The memory used is the size of the output.
>
> Idem.
>
> ) You can't bail out early if you are looking for a particular combination.
>
> Aaand false.
>
> That's four for four. I think the second point is your main thinking
> error, the rest are corollaries of that.
>
> Doing something with the results can be as complicated as you
> like inside 'the function that gets them'. Just call a function
> 'do_something_with_the_results', or provide a callback if you want
> it to be generic. The function could, for example, return a boolean
> that indicates bailing out early.
>
> So, recursion it is then.


While all that is true, it's not difficult to iterate over all instances
of a number of items (they were, IIRC, true, false and unknown in this
case) using a single numeric iterator and treating it as being in an
appropriate base (three in this case).

So you can loop over 7 items using (for i=0;i<2187;i++)

I'll leave arguing about whether the best way to break i down into 7
values from 0-3 uses iteration or not to others.
--
Online waterways route planner | http://canalplan.eu
Plan trips, see photos, check facilities | http://canalplan.org.uk
 
Reply With Quote
 
MartinBroadhurst
Guest
Posts: n/a
 
      10-31-2010
On 31 Oct, 18:23, "Trevor" <(E-Mail Removed)> wrote:
> It you use recursion, you don't get *any* of the results until you get *all*
> of the results.
> You need to put all of the results in a data structure and return it, unless
> what you are doing with them is so trivial you can put it inside the
> function that gets them.
> The memory used is the size of the output.


This isn't correct.

You can't *yield*, in the way you can in Python or C#, if that's what
you mean, although I'm sure you can implement yield using a thread.

More importantly, though, your recursive function can expose an "event
API", in which the client passes in a function that is called every
time a new combination has been constructed.

For example, here is a recursive form of the algorithm. I've just
taken the vector-based solution I suggested before and changed the
loops to recursive calls:

typedef unsigned int sos_func(unsigned int *, unsigned int, void *);

void subsets_of_subsets(unsigned int *ar, size_t n, unsigned int
index,
unsigned int *changed, sos_func func, void *data)
{
if (ar[index] < 2) {
/* Increment */
ar[index]++;
*changed = 1;
}
else {
/* Roll over */
ar[index] = 0;
}
if (*changed) {
/* Finished this combination */
const unsigned int stop = func(ar, n, data);
if (!stop) {
*changed = 0;
subsets_of_subsets(ar, n, n - 1, changed, func, data);
}
}
else if (index > 0) {
subsets_of_subsets(ar, n, --index, changed, func, data);
}
}

You could use it like this to get the output Max wanted:

unsigned int my_sos_func(unsigned int *ar, unsigned int n, void *data)
{
const char **variables;
unsigned int v;
unsigned int started = 0;

variables = data;
for (v = 0; v < n; v++) {
if (ar[v]) {
if (started) {
putchar(' ');
}
else {
started = 1;
}
if (ar[v] == 1) {
fputs(variables[v], stdout);
}
else if (ar[v] == 2) {
printf("!%s", variables[v]);
}
}
}
putchar('\n');

return 0;
}

int main(void)
{
unsigned int ar[] = {0, 0, 0};
const char *variables[] = {"a", "b", "c"};
size_t len = sizeof(ar) / sizeof(unsigned int);
unsigned int changed = 0;

subsets_of_subsets(ar, len, len - 1, &changed, my_sos_func,
(void*)variables);

return 0;
}


> You can't bail out early if you are looking for a particular combination.
>


Yes you can. You just have the function pointer return a value that
indicates that the algorithm should stop, as I have done above.

Martin
 
Reply With Quote
 
MartinBroadhurst
Guest
Posts: n/a
 
      10-31-2010
On 31 Oct, 18:55, MartinBroadhurst <(E-Mail Removed)>
wrote:
> On 31 Oct, 18:23, "Trevor" <(E-Mail Removed)> wrote:
>
>
> This isn't correct.
>

[Snip]

Drat! Willem got there before me!

Martin
 
Reply With Quote
 
Chad
Guest
Posts: n/a
 
      10-31-2010
On Oct 31, 11:38*am, Willem <(E-Mail Removed)> wrote:
> Trevor wrote:
>
> ) It you use recursion, you don't get *any* of the results until you get *all*
> ) of the results.
>
> False.
>
> ) You need to put all of the results in a data structure and return it, unless
> ) what you are doing with them is so trivial you can put it inside the
> ) function that gets them.
>
> Equally false.
>
> ) The memory used is the size of the output.
>
> Idem.
>


I believe the recursive solution to the combination problem I wrote
this morning proves parts of Trevor's statements wrong. I think. But
don't quote me on that.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: Combinations with true and false Seebs C Programming 2 10-27-2010 11:55 PM
[False,True] and [True,True] --> [True, True]????? bdb112 Python 45 04-29-2009 02:35 AM
debug="false" in web.config and <%@ debug="true" ...%> in aspx file => true or false? André ASP .Net 3 08-28-2006 12:02 PM
False positive, false intrusion, false alarm Nick Computer Security 3 04-26-2006 07:40 PM
Does true ^ true return false? Siemel Naran C++ 19 06-18-2004 11:06 AM



Advertisments