Generating all True/False Outcomes

[Alterah]

Hello,

First off, this isn't an assignment, just a problem I created for myself while doing homework for a Stats class. Anyhow, for some reason I just can't think at the moment and can't figure out how to approach the problem.

Lets say we have n true false questions (or questions each having m choices). All I want to do is generate a list of all possible answers to the n questions. So if we have 4 T/F questions we'd get something like:

TTTT, TTTF, TTFT, ...

This seems like a problem you would use backtracking on, but it's been about 8 months since I learned about backtracking and did anything with it. So, I don't really remember what it entails. I also want to assume that we don't know there are 2^4 answer sets. I would like this to use a counter to return the number of answer sets.

Thanks for any nudges

[Paul McKenzie]

Hello,

First off, this isn't an assignment, just a problem I created for myself while doing homework for a Stats class. Anyhow, for some reason I just can't think at the moment and can't figure out how to approach the problem.

Lets say we have n true false questions (or questions each having m choices). All I want to do is generate a list of all possible answers to the n questions. So if we have 4 T/F questions we'd get something like:

TTTT, TTTF, TTFT, ...

Just generate all n-digit binary numbers between 0 and 2^n-1 (n is the number of questions). Wherever there is a 0, make it a 'T', wherever you see a 1, make it an 'F'.

Example:

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1110
1111

So there are 2^n possibilities.

Regards,

Paul McKenzie

[Alterah]

That would be one way, but that assumes you know how many possibilities there are to begin with. I was/am trying to figure a way to have it go through all possibilities and increment a counter for each distinct one.

[Chris_F]

That would be one way, but that assumes you know how many possibilities there are to begin with. I was/am trying to figure a way to have it go through all possibilities and increment a counter for each distinct one.

2^n IS the way you determine the number of distinct combinations.

[monarch_dodra]

Something like this?

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <limits>

template <typename iter>
bool increment(iter first, iter last,
               typename std::iterator_traits<iter>::value_type min = std::numeric_limits<typename std::iterator_traits<iter>::value_type>::min(),
               typename std::iterator_traits<iter>::value_type max = std::numeric_limits<typename std::iterator_traits<iter>::value_type>::max())
{
  while((first!=last) && (*first == max))
  {
    *first = min;
    ++first;
  };
  if(first!=last)
  {
    ++*first;
    return true;
  }
  return false;
}

int main()
{
  std::vector<char> vect(5); //vector<bool> is not a container
  do
  {
    std::copy(vect.rbegin(), vect.rend(), std::ostream_iterator<bool>(std::cout));
    std::cout << std::endl;
  }while(increment(vect.begin(), vect.end(), false, true));
}

outputs

00000
00001
00010
00011
00100
00101
00110
00111
01000
01001
01010
01011
01100
01101
01110
01111
10000
10001
10010
10011
10100
10101
10110
10111
11000
11001
11010
11011
11100
11101
11110
11111

[Eri523]

Here's a thread on that topic: http://www.codeguru.com/forum/showthread.php?t=501123. The solutions posted there are less generic than the one given by monarch_dodra in post #5 but I think they're simpler.

HTH

[monarch_dodra]

Here's a thread on that topic: http://www.codeguru.com/forum/showthread.php?t=501123. The solutions posted there are less generic than the one given by monarch_dodra in post #5 but I think they're simpler.

HTH

I wouldn't consider my solution "complicated", it is actually very simple. The Generic STL-like interface just makes the syntax obscure.

I like your binary approach. Very nice.

[Alterah]

Thanks for the input. I will look into both. Also, I do realize that 2^n is the number of outcomes...or 3^n, etc. But, suppose I am lazy and want a program to generate all answer sets and spit out the total at the end. Anyway, I am on my phone right now. When I get home tonight I will check out the above.

[Lindley]

Thanks for the input. I will look into both. Also, I do realize that 2^n is the number of outcomes...or 3^n, etc. But, suppose I am lazy and want a program to generate all answer sets and spit out the total at the end. Anyway, I am on my phone right now. When I get home tonight I will check out the above.

I guess I'm confused about what's wrong with the binary approach. It tells you how many possible answers there are given the number of questions, and it generates what those answers are, and it can be written in just a few lines. What's wrong with it?

[monarch_dodra]

Or if you don't feel like thinking, you could try a bogo approach:

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <iterator>

#include <ctime>
#include <cstdlib>

typedef std::vector<char> line;

char binary_random_generator()
{
  return std::rand()%2;
}

int main()
{
  std::srand(std::time(0));

  std::set<line> a_set;

  line a_line(5);

  int fail_counter = 0;
  while(fail_counter < 1000)
  {
    std::generate_n(a_line.begin(), 5, binary_random_generator);
    if(a_set.insert(a_line).second)
    {
      fail_counter = 0;
    }
    else
    {
      ++fail_counter;
    }
  }
  std::cout << "There are " << a_set.size() << " Posibilities." << std::endl;
}

outputs

There are 32 Posibilities.

Disclaimer: Bogo is of factorial complexity.

[TheGreatCthulhu]

Alterah, if you don't want to use the math formula than u can use what some mathematicians call the lexical method - you take a set of symbols and form 'words', arranging them in as if you were writing a dictionary, until you have exhausted all possibilities.
(This, of course, requires that it is possible to order the set - but this is not a problem since whatever your choices ('answers') are, they can be abstracted into numbers.)

Forom what I can see, this is exactly what monarch_dodra's first solution does, it's just a matter of adding a counter. OK, maybe it's a bit hard to read, but it's the algorithm that matters.

BTW (a bit off-topic, but) can some of you C++ experts give me a brief answer to something.
I found monarch_dodra's code interesting, so it got me reading up about iterators, and then I ended up on a page about template specialization and partial specialization here... From what I've learned, it seems that the term 'specialization' is somewhat misguiding, in the sense that there is no parent-child relationship between the specialized and the original template; no code is inherited. Is this true?
If so, than it's just syntactic sugar (since basically it allows to define a completely separate class or a template using the same name)?
And, am I right if I say that, under the hood, template specializations are just classes but appear as templates in code, and partial specializations are just separate templates that get picked out if the right conditions are met?
I wouldn't want to pollute this thread with an unrelated topic, so if someone can give me a short answer, or direct me to some reference material, it would be great. Tnx

[Lindley]

BTW (a bit off-topic, but) can some of you C++ experts give me a brief answer to something.
I found monarch_dodra's code interesting, so it got me reading up about iterators, and then I ended up on a page about template specialization and partial specialization here... From what I've learned, it seems that the term 'specialization' is somewhat misguiding, in the sense that there is no parent-child relationship between the specialized and the original template; no code is inherited. Is this true?
If so, than it's just syntactic sugar (since basically it allows to define a completely separate class or a template using the same name)?
And, am I right if I say that, under the hood, template specializations are just classes but appear as templates in code, and partial specializations are just separate templates that get picked out if the right conditions are met?
I wouldn't want to pollute this thread with an unrelated topic, so if someone can give me a short answer, or direct me to some reference material, it would be great. Tnx

Essentially correct. For example, std::vector<bool> is a specialization which is space-optimized to use 1 bit (instead of 1 byte as you might expect) per bool. This has actually been regarded as a bad design decision in retrospect, but it's a prime example of template specialization.

There are some times when template specialization is required for metaprogramming. The typical example is compile-time computation of the Fibanacci sequence:

template <int N>
struct Fib
{
    const static int val = Fib<N-1>::val + Fib<N-2>::val;
};

template <>
struct Fib<0>
{
    const static int val = 1;
};

template <>
struct Fib<1>
{
    const static int val = 1;
};

[nuzzle]

I was/am trying to figure a way to have it go through all possibilities and increment a counter for each distinct one.

Its simple, just use nested loops. For example with 4 T/F questions you have 4 nested loops with each loop variable counting from 0 to 1.

As a dynamic alternative to static loop nesting you can use recursion. The recursive method has one loop only and each recursive call represents one level deeper down the loop nesting.