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

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

1 голос
/ 12 ноября 2009

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

Например:

Двоичный номер: ........ 1. алгоритм должен вернуть оставшиеся 2 ^ 7 оставшихся двоичных чисел, например, 00000001,00000011 и т. д.

Спасибо, Sathish

Ответы [ 8 ]

4 голосов
/ 12 ноября 2009

Если это только для небольших чисел (возможно, до 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;
    }
}
4 голосов
/ 12 ноября 2009

В приведенном примере не перестановка!

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

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

2 голосов
/ 12 ноября 2009

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

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

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

например.

Е ( "% б", я); // не стандартно в C / C ++

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

1 голос
/ 28 апреля 2011

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

// 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);
    }
0 голосов
/ 10 октября 2014

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

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

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

Перестановки 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(); 
}
0 голосов
/ 25 августа 2010

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

Например, для 1xx1: вы хотите: 1001, 1011, 1101, 1111.

Алгоритм O (N) выглядит следующим образом.

Предположим, что биты определены в маске m. У вас также есть хеш h.

Для генерации чисел 

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

0 голосов
/ 12 ноября 2009

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

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

...