Array combinations of 0s and 1s

What is a good algorithm to fill an array with 0s and 1s combinations. For example if I have three columns the combinations would be: (1 1 1) (0 1 1) (1 0 1) (0 0 1) (1 1 0) (0 1 0) (1 0 0) (0 0 0) It makes a total of 8 rows (I hope I'm right here). So how to determine the needed number 开发者_如何学Goof rows in advance (depending on the N number of columns) and then how to fill the array out programatically? Any programming language is fine (I tagged C and lisp because of familiarity) it's the algorithm that is needed. Thanks

Count up from 0 in base 2

0 = 000
1 = 001
2 = 010
...
7 = 111

The number of combinations is simply 2 to the power of N (or 1 << N in C). The values are simply the binary representations of the numbers 0 to N-1.

It's 2 ^ (NUMBER_OF_COLUMNS)

This is simply the number of subsets of a set. You have 3 columns, where each column is a 0 or 1.

You want to know how many rows you'll need.

You have N columns. Let each column be an item. There are two possibie choices for this column, and there are two choices for each column after. Since there are N columns and 2 choices per column, you have 2^N subsets.

Here's an alternative way to fill out the array:

for (unsigned i = 0; i < nRows; ++i) {
        for (unsigned j = i, k = nCols-1; j != 0; j >>= 1, --k)
            bin[i][k] = j & 1;
}

just remember to initialize the array to zero.

@polygenelubricants is right with his comment. It's needlessly wasteful to actually fill an array in this case. If you need a collection, here's an incredibly simple implementation of the List interface that does what you want:

class BinarySequenceList extends AbstractList<String> {
    private final int digits;
    public BinarySequenceList(int digits) {
        if ( digits >= 32 || digits <= 0 ) { throw new IllegalArgumentException(); }
        this.digits = digits;
    }

    public String get(int index) {
        if ( index < 0 || index >= size() ) {
            throw new IndexOutOfBoundsException();
        }
        String padded = "00000000000000000000000000000000" + 
            Integer.toBinaryString(index);
        return padded.substring(padded.length() - digits);
    }

    public int size() { return 1 << digits; }
}

//usage:
List<String> seq = new BinarySequenceList(5);
for ( String s : seq ) {
    System.out.println(s);
}

//prints:
00000
00001...

#include "stdafx.h"
#include <cmath>

void converttobin(const int row, const int cols, int** parrbin)
{
    int j = cols;
    int val = row;
    while (val){
        parrbin[row][--j] = val % 2;
        val /= 2;
    }
    for (int i=0; i<j; i++)
        parrbin[row][i] = 0;
}

void testfun()
{
double cols;
cout << "Number of columns - ";
cin >> cols;
int maxrows = pow(2, cols);
int **parrbin = new int*[maxrows];
for (int i=0; i<maxrows; i++)
    parrbin[i] = new int[static_cast<int>(cols)];

for (int row=0; row<maxrows; row++)
{
    converttobin(row, cols, parrbin);
    cout << row << ": ";
    for (int i=0; i<cols; i++)
        cout << parrbin[row][i] << '\t';
    cout << endl;
}

for (int i=0; i<maxrows; i++)
    delete [] parrbin[i];

delete [] parrbin;
}