Algorithmus zum Generieren aller möglichen Arrays von Einsen und Nullen einer gegebenen Länge

Question

Wie kann ich alle möglichen Bitkombinationen in einem Array von Bits der Länge n generieren. Wenn ich mit allen Nullen in meinem Array anfange, gibt es n Möglichkeiten, das erste Bit zu platzieren, und für diese n Möglichkeiten gibt es n-1 Möglichkeiten, das zweite Bit zu platzieren. Einheit Alle n Bits sind auf eins gesetzt. Aber bis jetzt habe ich es nicht geschafft, es zu programmieren.

Auch viele Leute haben darauf hingewiesen, dass ich dies tun kann, indem ich von 0 bis (2^n) -1 zähle und die Zahl binär abdrucke. Dies wäre ein einfacher Weg, um das Problem zu lösen, aber in diesem Fall lasse ich die Maschine nur zählen, anstatt ihr zu sagen, wo sie platziert werden soll. Ich mache das für das Lernen, also würde ich gerne wissen, wie man den Ein-Platz-Ansatz programmiert.

Answer 1

Wie würden Sie manuell auf Papier zählen? Du würdest die letzte Ziffer überprüfen. Wenn es 0 ist, setzen Sie es auf 1. Wenn es bereits 1 ist, setzen Sie es zurück auf 0 und fahren mit der nächsten Ziffer fort. Es ist also ein rekursiver Prozess.

Das folgende Programm erzeugt alle möglichen Kombinationen durch eine Sequenz mutiert:

#include <iostream> 

template <typename Iter> 
bool next(Iter begin, Iter end) 
{ 
    if (begin == end)  // changed all digits 
    {      // so we are back to zero 
     return false;  // that was the last number 
    } 
    --end; 
    if ((*end & 1) == 0) // even number is treated as zero 
    { 
     ++*end;   // increase to one 
     return true;  // still more numbers to come 
    } 
    else     // odd number is treated as one 
    { 
     --*end;   // decrease to zero 
     return next(begin, end); // RECURSE! 
    } 
} 

int main() 
{ 
    char test[] = "0000"; 
    do 
    { 
     std::cout << test << std::endl; 
    } while (next(test + 0, test + 4)); 
} 

Das Programm mit einer beliebigen Reihenfolge jeder Art funktioniert. Wenn Sie alle möglichen Kombinationen gleichzeitig benötigen, legen Sie sie einfach in eine Sammlung, anstatt sie auszudrucken. Natürlich benötigen Sie einen anderen Elementtyp, da Sie C-Arrays nicht in einen Vektor einfügen können. Werfen wir einen Vektor von Strings verwenden:

#include <string> 
#include <vector> 

int main() 
{ 
    std::vector<std::string> combinations; 
    std::string test = "0000"; 
    do 
    { 
     combinations.push_back(test); 
    } while (next(test.begin(), test.end())); 
    // now the vector contains all pssible combinations 
} 

Wenn Sie hier nicht Rekursion mögen, ist eine äquivalente iterative Lösung:

template <typename Iter> 
bool next(Iter begin, Iter end) 
{ 
    while (begin != end)  // we're not done yet 
    { 
     --end; 
     if ((*end & 1) == 0) // even number is treated as zero 
     { 
      ++*end;   // increase to one 
      return true;  // still more numbers to come 
     } 
     else     // odd number is treated as one 
     { 
      --*end;   // decrease to zero and loop 
     } 
    } 
    return false;    // that was the last number 
} 

Answer 2

FredOverflow befindet sich direkt im Allgemeinen.

jedoch für 1s & 0s solltest du besser erhöhen nur eine ganze Zahl von 0:

int need_digits = 10 
unsigned int i=0 
while (! i>>need_digits){ 
    # convert to binary form: shift & check, make an array, or cast to string, anything. 
    } 

... Ich denke, Sie werden nicht mehr als 32 Bits benötigen, oder Sie an die Kette mehrere haben würde Ganzzahlen .. und bleiben Sie bei der vorherigen Antwort :)

Answer 3

Solche Probleme sind trivial funktional gelöst. Um die Lösungen der Länge n zu finden, finden Sie zuerst die Lösungen der Länge n-1 und fügen dann '0' und '1' an diese Lösungen an, wodurch der Lösungsraum verdoppelt wird.

Hier ist ein einfaches rekursives Programm Haskell:

comb 0 = [[]] 

comb n = 
    let rest = comb (n-1) 
    in map ('0':) rest 
    ++ map ('1':) rest 

Und hier ist ein Testlauf:

> comb 3 
["000","001","010","011","100","101","110","111"] 

Answer 4

A "wirklich" rekursive Ansatz in C++:

#include <iostream> 
#include <string> 

void print_digits(int n, std::string const& prefix = "") { 
    if (!n) { 
     std::cout << prefix << std::endl; 
     return; 
    } 
    print_digits(n-1, prefix + '0'); 
    print_digits(n-1, prefix + '1'); 
} 

int main(int, char**) { 
    print_digits(4); 
} 

Answer 5

Optimal Lösung ist hier:

http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation

Answer 6

Dies ist meine Antwort. Der Vorteil ist, dass alle Kombinationen in einem zweidimensionalen Array gespeichert werden, aber der Nachteil ist, dass Sie es nur für einen Stich bis zu 17 Ziffern verwenden können !!

#include <iostream> 

using namespace std; 

int main() 
    { 
    long long n,i1=0,i2=0, i=1, j, k=2, z=1; 
    cin >> n; 
    while (i<n){ 
     k = 2*k; 
     i++; 
    } 
    bool a[k][n], t = false; 
    j = n-1; 
    i1=0; 
    i2 = 0; 
    z = 1; 
    while (j>=0){ 
     if(j!=n-1){ 
     z=z*2; 
     } 
     i2++; 
     t = false; 
     i = 0; 
    while (i<k){ 
     i1 = 0; 
     while (i1<z){ 
      if(t==false){ 
      a[i][j]=false; 
      } 
      else { 
       a[i][j]= true; 
      } 
      i1++; 
      i++; 
     } 
     if(t==false){ 
      t = true; 
     }else { 
      t = false; 
     } 
    } 
    j--; 
    } 
    i = 0; 
    j = 0; 
    while (i<k){ 
     j = 0; 
     while (j<n){ 
      cout << a[i][j]; 
      j++; 
     } 
     cout << endl; 
     i++; 
    } 
    return 0; 
}