Best algorithm to find all possible permutation of given binary bits

I am looking for an optimal algorithm to find out remaining all possible permutation of a give开发者_Go百科 binary number.

For ex:

Binary number is : ........1. algorithm should return the remaining 2^7 remaining binary numbers, like 00000001,00000011, etc.

Thanks, sathish

The example given is not a permutation!

A permutation is a reordering of the input.

So if the input is 00000001, 00100000 and 00000010 are permutations, but 00000011 is not.

If this is only for small numbers (probably up to 16 bits), then just iterate over all of them and ignore the mismatches:

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

to find all you aren't going to do better than looping over all numbers e.g. if you want to loop over all 8 bit numbers

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

if you need to output in binary then look at the string formatting options you have in what ever language you are using.

e.g.

printf("%b",i); //not standard in C/C++

for calculation the base should be irrelavent in most languages.

I read your question as: "given some binary number with some bits always set, create the remaining possible binary numbers".

For example, given 1xx1: you want: 1001, 1011, 1101, 1111.

An O(N) algorithm is as follows.

Suppose the bits are defined in mask m. You also have a hash h.

To generate the numbers < n-1, in pseudocode:

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

The idea in the code is to walk through all numbers from 0 to n-1, and set the pre-defined bits to 1. Then memoize the resulting number (iff not already memoized) by mapping the resulting number to the value of a running counter.

The keys of h will be the permutations. As a bonus the h[p] will contain a unique index number for the permutation p, although you did not need it in your original question, it can be useful.

Why are you making it complicated ! It is as simple as the following:

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

There are many permutation generating algorithms you can use, such as this one:

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

source: http://www.bearcave.com/random_hacks/permute.html

Make sure you adapt the relevant constants to your needs (binary number, 7 bits, etc...)

If you are really looking for permutations then the following code should do.

To find all possible permutations of a given binary string(pattern) for example.

The permutations of 1000 are 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(); 
}

If you intend to generate all the string combinations for n bits , then the problem can be solved using backtracking.

Here you go :

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