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

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

你为什么要复杂！它很简单，如下所示：

// 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 5

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

例如，给定 1xx1：您想要：1001、1011、1101、1111。

O(N) 算法如下。

假设这些位在掩码 m 中定义。你也有一个哈希h。

要生成数字 < n-1，请使用伪代码：

计数器 = 0
对于 0..n-1 中的 x：
  x' = x | 〜米
  如果未设置 h[x']：
     h[x'] = 计数器
     计数器 += 1

代码中的想法是遍历从 0 到 n-1 的所有数字，并将预定义的位设置为 1。然后通过将结果数字映射到运行的值来记住结果数字（如果尚未记住）柜台。

h 的键将是排列。作为奖励， h[p] 将包含排列 p 的唯一索引号，尽管您在原始问题中不需要它，但它可能很有用。

Answer 6

如果您真的在寻找排列，那么应该使用以下代码。

例如，查找给定二进制字符串（模式）的所有可能排列。

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 7

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

#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 8

如果您打算为 n bits 生成所有字符串组合，则可以使用回溯解决该问题。

干得好 ：

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