找到给定二进制位的所有可能排列的最佳算法

Question

我正在寻找一种最佳算法来找出剩余的所有可能的排列 给定的二进制数。

例如：

二进制数是：........1。算法应该返回剩余的 2^7 剩余二进制数，如 00000001,00000011 等。

谢谢， 萨蒂什

Answer 1

给出的示例不是排列！

排列是对输入的重新排序。

因此，如果输入是 00000001，则 00100000 和 00000010 是排列，但 00000011 不是。

Answer 2

如果这仅适用于小数字（可能最多 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;
    }
}

Answer 3

要找到所有内容，您不会比循环所有数字更好，例如，如果您想循环所有 8 位数字，

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

如果您需要以二进制输出，那么请查看您使用的语言中的字符串格式选项。

例如

printf("%b",i); //不是 C/C++

计算的标准，基数在大多数语言中应该是无关的。

Answer 4

我将你的问题读为：“给定一些始终设置某些位的二进制数，创建剩余的可能的二进制数”。

例如，给定 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 的唯一索引号，尽管您在原始问题中不需要它，但它可能很有用。

Answer 5

你为什么把事情搞得这么复杂！
它很简单，如下所示：

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

Answer 6

您可以使用许多排列生成算法，例如以下一个：

#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 位等...）

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

Answer 8

如果你打算生成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);
    }
}