Best algorithm to find all possible permutation of given binary bits

Question

Hi,

I am looking for an optimal algorithm to find out remaining all possible permutation of a give binary number.

For ex:

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

Thanks, sathish

Answer 1

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%5Fhacks/permute.html

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

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

If I understand you question you have n bits form which some are 1 some are 0. Model this as an array of boolean and put all the '1' in the first positions. Like 010101 will be stored as 000111. Then move the 'highest' bit one position by one to the left 001011 then 010011 then 100011, then do the same with the next highest bit 100101 then 101001 then 110001 and so on...

Answer 6

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.