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 0 0） 它總共有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

這是2^(NUMBER_OF_COLUMNS)

Answer 4

這簡直是一個集的子集的數量。你有3列，其中每列是0或1.

你想知道你需要多少行。

您有N列。讓每列成爲一個項目。該列有兩種可能的選擇，並且之後每列有兩種選擇。由於每列有N列和2個選項，因此您有2^N個子集。

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

這裏有一個替代的方式來填寫數組：

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 7

@polygenelubricants對他的評論是正確的。在這種情況下實際填充數組是不必要的浪費。如果你需要一個集合，這裏是一個令人難以置信的簡單的實現你想要的列表界面：

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