Re: Combinations with true and false

Discussion in 'C Programming' started by Ben Pfaff, Oct 27, 2010.

  1. Ben Pfaff

    Ben Pfaff Guest

    Max </> 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
     
    Ben Pfaff, Oct 27, 2010
    #1
    1. Advertising

  2. Ben Pfaff

    Chad Guest

    On Oct 27, 4:33 pm, "Trevor" <> wrote:
    > "Ben Pfaff" <> wrote in message
    >
    > news:...
    >
    >
    >
    > > 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.
     
    Chad, Oct 31, 2010
    #2
    1. Advertising

  3. Ben Pfaff

    Chad Guest

    On Oct 31, 8:21 am, Chad <> wrote:
    > On Oct 27, 4:33 pm, "Trevor" <> wrote:
    >
    >
    >
    > > "Ben Pfaff" <> wrote in message

    >
    > >news:...

    >
    > > > 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.
     
    Chad, Oct 31, 2010
    #3
  4. Ben Pfaff

    Willem Guest

    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
     
    Willem, Oct 31, 2010
    #4
  5. Ben Pfaff

    Nick Guest

    Willem <> 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
     
    Nick, Oct 31, 2010
    #5
  6. On 31 Oct, 18:23, "Trevor" <> 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
     
    MartinBroadhurst, Oct 31, 2010
    #6
  7. On 31 Oct, 18:55, MartinBroadhurst <>
    wrote:
    > On 31 Oct, 18:23, "Trevor" <> wrote:
    >
    >
    > This isn't correct.
    >

    [Snip]

    Drat! Willem got there before me!

    Martin
     
    MartinBroadhurst, Oct 31, 2010
    #7
  8. Ben Pfaff

    Chad Guest

    On Oct 31, 11:38 am, Willem <> 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.
     
    Chad, Oct 31, 2010
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Siemel Naran

    Does true ^ true return false?

    Siemel Naran, Jun 17, 2004, in forum: C++
    Replies:
    19
    Views:
    673
    Chris Theis
    Jun 18, 2004
  2. Pierre Quentel

    "0 in [True,False]" returns True

    Pierre Quentel, Dec 12, 2005, in forum: Python
    Replies:
    59
    Views:
    1,046
    Grant Edwards
    Dec 16, 2005
  3. André
    Replies:
    3
    Views:
    1,616
  4. bdb112
    Replies:
    45
    Views:
    1,370
    jazbees
    Apr 29, 2009
  5. Seebs

    Re: Combinations with true and false

    Seebs, Oct 27, 2010, in forum: C Programming
    Replies:
    2
    Views:
    313
    Seebs
    Oct 28, 2010
Loading...

Share This Page