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