Generating all possible numbers

[andrepd]

Hi guys. I'm sure this is pretty simple, but I'm stumped for a way to do this. Essentially if I have an array with P collumns and V^P rows, how can I fill in all the combinations, that is, essentially, all possible numbers in base V of P digits. For example, for P=3 and V=2

000
001
010
011
100
101
110
111

Keep in mind that this is an 2 dimensional array, not an array of ints.

For P=4 and V=3.

0000
0001
0002
0010
0011
0012
....

Having this array generated, the rest of work for what I'm trying to devolop is trivial. So having some code/tips on how to do this would be greatly appreciated. Thanks.


This is a code I've written that should do the trick, but for some reason it gives this error on compiling: "main.cpp:65: error: invalid types `double[3][9][double]' for array subscript"

for(i=0;i<P;i++) {
        for(j=0;j<pow(V,i);j++) {
            for(k=0;k<V;k++) {
                for(l=0;l<pow(V,(P-i-1));l++) {
                    a[i][(j*V*pow(V,P-i-1) + l + k*pow(V,P-i-1))];
                }
            }            
        }
    }

Any help would be welcome.

[nuzzle]

error: invalid types

It's a type error. Pow returns a floating point and an integer is expected.

[andrepd]

Yes, if I cast the result of "pow" to short it works fine.

However, the algorithm produces odd unexpected results. Does anybody know of an algorithm to perform what I described in the OP (filling in the with all possible value combinations)?

[Eri523]

However, the algorithm produces odd unexpected results.

Looks like one more of these ubiquotious floating point oddities that have been discussed many times around here. For instance, here's a discussion going on right now: http://forums.codeguru.com/showthread.php?t=523168

Generating all possible symbol combinations has been discussed quite some times as well. For instance, this may be interesting: http://forums.codeguru.com/showthread.php?t=508086

More related discussions can be found using a forum search.

[monarch_dodra]

For instance, this may be interesting: http://forums.codeguru.com/showthread.php?t=508086

It's funny, because back when I posted my solution, it looked like total overkill for binary counting (and was), however, if you want to count in any other base (eg, 3), then it works perfectly. My old code, parametrized with the OP's P and V:

#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;
}

const int P = 4;
const int V = 3;

int main()
{
  std::vector<int> vect(P, 0);
  do
  {
    std::copy(vect.rbegin(), vect.rend(), std::ostream_iterator<int>(std::cout));
    std::cout << std::endl;
  } while(increment(vect.begin(), vect.end(), 0, V-1));
}

generates:

0000
0001
0002
0010
0011
0012
0020
...

[nuzzle]

Yes, if I cast the result of "pow" to short it works fine.

However, the algorithm produces odd unexpected results. Does anybody know of an algorithm to perform what I described in the OP (filling in the with all possible value combinations)?

Since int is the "natural" integer it's better to cast to int actually.

Regarding the algorithm. It's just to generate all numbers between 0 and V^P - 1. That would be the rows. From each row number you extract P digits in base V and place in the colums.

[gakushya]

Generating all possible numbers?
I thought this was some sort of philosophical thing when I clicked here