Лучший алгоритм для поиска всех возможных перестановок заданных двоичных битов

Приведенный пример не перестановка!

Перестановка — это переупорядочивание входных данных.

Таким образом, если ввод 00000001, 00100000 и 00000010 являются перестановками, а 00000011 — нет.

Если это только для небольших чисел (вероятно, до 16 бит), просто переберите их все и игнорируйте несоответствия:

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

чтобы найти все, что вы не собираетесь делать лучше, чем перебирать все числа, например. если вы хотите перебрать все 8-битные числа

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

если вам нужно вывести в двоичном формате, посмотрите на параметры форматирования строки, которые у вас есть на любом языке, который вы используете.

e.g.

printf("%b",i); // не стандартно в C/C++

для расчета база должна быть нерелевантной в большинстве языков.

Я прочитал ваш вопрос как: «данное двоичное число с некоторыми битами всегда установлено, создайте оставшиеся возможные двоичные числа».

Например, учитывая 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, хотя он вам не понадобился в исходном вопросе, он может быть полезен.

Зачем усложняешь! Это так же просто, как следующее:

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

Существует множество алгоритмов генерации перестановок, которые вы можете использовать, например этот:

#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 бит и т. д.).

Если вы действительно ищете перестановки, то следующий код должен подойти.

Например, чтобы найти все возможные перестановки данной двоичной строки (шаблона).

Перестановки 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(); 
}

Если вы намерены сгенерировать все комбинации строк для 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);
    }
}