Массив комбинаций 0 и 1

Question

Какой хороший алгоритм для заполнения массива комбинациями 0 и 1.Например, если у меня есть три столбца, комбинации будут: (1 1 1) (0 1 1) (1 0 1) (0 0 1) (1 1 0) (0 1 0) (1 0 0) (0 00) Всего 8 строк (надеюсь, я прямо здесь).Итак, как заранее определить необходимое количество строк (в зависимости от количества столбцов N), а затем как заполнить массив программно?Любой язык программирования хорош (я пометил C и lisp из-за знакомства), это алгоритм, который нужен.Спасибо

Answer 1

Подсчет от 0 в базе 2

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

Answer 2

Количество комбинаций просто 2 к степени N (или 1 << N в C).Значения - это просто двоичные представления чисел от 0 до N-1.

Answer 3

@ polygenelubricants правильно с его комментарием. В этом случае ненужно расточительно заполнять массив. Если вам нужна коллекция, вот невероятно простая реализация интерфейса List, которая делает то, что вы хотите:

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...

Answer 4

Вот альтернативный способ заполнить массив:

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

просто не забудьте инициализировать массив нулем.

Answer 5

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

Answer 6

Это просто количество подмножеств набора.У вас есть 3 столбца, где каждый столбец равен 0 или 1.

Вы хотите знать, сколько строк вам понадобится.

У вас есть N столбцов.Пусть каждый столбец будет предметом.Есть два возможных варианта для этого столбца, и есть два варианта для каждого столбца после.Поскольку существует N столбцов и 2 варианта на столбец, у вас есть 2 ^ N подмножеств.

Answer 7

Это 2 ^ (NUMBER_OF_COLUMNS)