주어진 이진 비트의 모든 순열을 찾을 수있는 최상의 알고리즘

Question

주어진 2 진수의 가능한 모든 순열을 찾는 최적의 알고리즘을 찾고 있습니다.

예 :

이진수는 ........ 1입니다. 알고리즘은 사티시 등 0000000100000011처럼

감사 나머지 2^7 나머지 진수를 반환해야

Answer 1

등이 하나 당신이 사용할 수있는 많은 순열 생성 알고리즘이 있습니다

#include <stdio.h> 

void print(const int *v, const int size) 
{ 
    if (v != 0) { 
    for (int i = 0; i < size; i++) { 
     printf("%4d", v[i]); 
    } 
    printf("\n"); 
    } 
} // print 


void visit(int *Value, int N, int k) 
{ 
    static level = -1; 
    level = level+1; Value[k] = level; 

    if (level == N) 
    print(Value, N); 
    else 
    for (int i = 0; i < N; i++) 
     if (Value[i] == 0) 
     visit(Value, N, i); 

    level = level-1; Value[k] = 0; 
} 

main() 
{ 
    const int N = 4; 
    int Value[N]; 
    for (int i = 0; i < N; i++) { 
    Value[i] = 0; 
    } 
    visit(Value, N, 0); 
} 

은

소스 :http://www.bearcave.com/random_hacks/permute.html

당신이 당신의 요구에 관련 상수 적응해야합니다 (이진수, 7 비트 등)

Answer 2

모든 번호를 반복하는 것보다 더 잘할 수없는 항목을 찾으려면 예 : 당신은 당신이 사용하는 무엇을 적 언어로 당신이 서식 옵션을 문자열 보면 바이너리 출력해야하는 경우 루프 8 온통 비트 숫자

for (int i =0; i < (1<<8) ; ++i) 
{ 
    //do stuff with i 
} 

를 원하는 경우.

printf ("% b", i); // C/C++ 표준이 아님

계산을위한베이스는 대부분의 언어에서 관련이 없어야합니다.

Answer 3

주어진 예제는 이 아니며, 순열!

순열은 입력의 순서를 바꾸는 것입니다.

따라서 입력이 00000001이면 00100000과 00000010은 순열이지만 00000011은 그렇지 않습니다. 이 (아마도 최대 16 비트) 작은 숫자 만 있으면

는

Answer 4

, 그럼 그냥 그들 모두를 반복하고 불일치를 무시 :

int fixed = 0x01; // this is the fixed part 
int mask = 0x01; // these are the bits of the fixed part which matter 
for (int i=0; i<256; i++) { 
    if (i & mask == fixed) { 
     print i; 
    } 
} 

Answer 5

내가 아니라 귀하의 질문에 읽기 : "일부 진수와 부여를 일부 비트는 항상 설정되고 나머지 가능한 2 진수를 만듭니다. " 예를 들어

주어진 1xx1 : 당신은 원하는 다음과 같다 : 1001, 1011, 1101

1111 O (N) 알고리즘이다.

비트가 마스크 m에서 정의된다고 가정하십시오. 당신은 해쉬 h도 가지고 있습니다.

는 숫자 < N-1, 의사 코드를 생성하는 방법 :

 
counter = 0 
for x in 0..n-1: 
    x' = x | ~m 
    if h[x'] is not set: 
    h[x'] = counter 
    counter += 1 

코드의 아이디어는 0부터 n-1까지의 모든 숫자를 통해 걸어 1로 사전 정의 된 비트를 설정한다

결과 숫자를 실행중인 카운터 값에 매핑하여 결과 숫자를 메모합니다 (아직 메모되지 않은 경우).

h의 키는 순열입니다. 보너스로 h [p]에는 순열 p에 대한 고유 색인 번호가 포함됩니다. 원래 질문에는 필요하지 않지만 유용 할 수 있습니다.

Answer 6

왜 복잡하게 만드나요? 은 다음과 같이 간단하다 : 당신이 정말로 순열을 찾고 있다면 다음 코드가해야 할

// permutation of i on a length K 
// Example : decimal i=10 is permuted over length k= 7 
// [10]0001010-> [5] 0000101-> [66] 1000010 and 33, 80, 40, 20 etc. 

main(){ 
int i=10,j,k=7; j=i; 
do printf("%d \n", i= ((i&1)<< k + i >>1); while (i!=j); 
    } 

Answer 7

.

주어진 바이너리 문자열 (패턴)의 모든 가능한 순열을 찾으려면. 1000

순열 1000, 0100, 0010, 0001이다 :

void permutation(int no_ones, int no_zeroes, string accum){ 
    if(no_ones == 0){ 
     for(int i=0;i<no_zeroes;i++){ 
      accum += "0"; 
     } 

     cout << accum << endl; 
     return; 
    } 
    else if(no_zeroes == 0){ 
     for(int j=0;j<no_ones;j++){ 
      accum += "1"; 
     } 

     cout << accum << endl; 
     return; 
    } 

    permutation (no_ones - 1, no_zeroes, accum + "1"); 
    permutation (no_ones , no_zeroes - 1, accum + "0"); 
} 

int main(){ 
    string append = ""; 

    //finding permutation of 11000 
    permutation(2, 6, append); //the permutations are 

    //11000 
    //10100 
    //10010 
    //10001 
    //01100 
    //01010 

    cin.get(); 
} 

Answer 8

는 N 비트의 모든 문자열 조합, 다음 문제가 역 추적을 이용하여 해결할 수를 생성하고자하는 경우. 여기

당신은 갈 :

//Generating all string of n bits assuming A[0..n-1] is array of size n 
public class Backtracking { 

    int[] A; 

    void Binary(int n){ 
     if(n<1){ 
      for(int i : A) 
      System.out.print(i); 
      System.out.println(); 
     }else{ 
      A[n-1] = 0; 
      Binary(n-1); 
      A[n-1] = 1; 
      Binary(n-1); 
     } 
    } 
    public static void main(String[] args) { 
     // n is number of bits 
     int n = 8; 

     Backtracking backtracking = new Backtracking(); 
     backtracking.A = new int[n]; 
     backtracking.Binary(n); 
    } 
}