Velocity Reviews > Re: Combinations with true and false

# 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

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.

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.

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

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

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

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

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.