주어진 길이의 1과 0으로 가능한 모든 배열을 생성하는 알고리즘

Question

길이가 n 인 비트 배열에서 가능한 모든 비트 조합을 어떻게 생성 할 수 있습니까? 내 배열의 모든 0으로 시작할 경우 첫 번째 비트를 배치 할 n 가지 가능성이 있으며 두 번째 비트를 배치 할 n-1 가지 가능성이 n 가지 가능성이 있습니다. 단위는 모두 n 비트가 1로 설정됩니다. 그러나 지금까지 나는 그것을 프로그램 할 수 없었다.

또한 많은 사람들이 0에서 (2^n) -1까지 세어 이진수로 숫자를 인쇄함으로써이 작업을 수행 할 수 있다고 지적했습니다. 이것은 문제를 해결하는 쉬운 방법이 될 것이지만,이 경우 컴퓨터를 어디에 놓을 지 계산하는 대신 계산하게합니다. 학습을 위해이 작업을 수행하므로 일괄 배치 방식을 프로그래밍하는 방법을 알고 싶습니다.

Answer 1

수동으로 종이에 기록 하시겠습니까? 마지막 자릿수를 확인합니다. 0이면 1로 설정하고, 1이면 다시 0으로 설정하고 다음 숫자로 계속 진행합니다. 그래서 재귀적인 과정입니다.

다음 프로그램 시퀀스 돌연변이의 모든 가능한 조합을 생성

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

프로그램은 어떤 형태의 임의의 시퀀스로 작동한다. 가능한 모든 조합이 동시에 필요하면 인쇄하지 말고 컬렉션에 넣으십시오. 물론 C 배열을 벡터에 넣을 수 없으므로 다른 요소 유형이 필요합니다. 의 문자열의 벡터를 사용하자 :

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

당신이 재귀 마음에 들지 않으면, 여기에 해당하는 반복적 인 솔루션입니다 :

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 일반적으로 권리입니다.

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

... 난 당신이 32 개 이상의 비트를 필요하지 않습니다 또는 체인 여러해야 할 것 같아요

그러나, 1 초 & 0 당신은 더 나은 단지 0의 정수를 증가 거라고 정수 .. 그리고 이전 대답에 충실 :)

Answer 3

이러한 문제는 trivially 기능적으로 해결됩니다. 길이 n의 솔루션을 찾으려면 먼저 길이 n-1의 솔루션을 찾은 다음 해당 솔루션에 '0'과 '1'을 추가하여 솔루션 공간을 두 배로 늘립니다. 여기

간단한 재귀 하스켈 프로그램입니다 :

comb 0 = [[]] 

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

그리고 여기 실행을 테스트 :

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

Answer 4

++ C에서 A "진정으로"재귀 방법 : 최적의

#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

해결책은 여기에 있습니다 :

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

Answer 6

이것은 내 대답입니다. 장점은 모든 조합이 2 차원 배열에 저장되지만 단점은 최대 17 자리까지 오랫동안 사용할 수 있다는 점입니다!

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