生成长度为n的所有二进制字符串到布尔数组中的最快方法是什么？

Question

生成长度为n的所有二进制字符串到布尔数组中的最快方法是什么？

9

例如，如果我想要长度为3的所有二进制字符串，我可以简单地这样声明它们：

boolean[] str1 = {0,0,0};
boolean[] str2 = {0,0,1};
boolean[] str3 = {0,1,0};
boolean[] str4 = {0,1,1};
boolean[] str5 = {1,0,0};
boolean[] str6 = {1,0,1};
boolean[] str7 = {1,1,0};
boolean[] str8 = {1,1,1};

什么是生成所有长度为N的二进制字符串到布尔数组中最有效的方法？

我不一定需要最有效的方法，只需要一个相当有效且容易多线程处理的方法。

注：如果需要，我会将它们全部存储在ArrayList中。

- snotyak

7个回答

4

例子：如果你需要长度为4的数组，那么你必须要有16个不同的数组，用数学计算2^4=16。

你可以使用这段简单的Java代码来生成所有的数组：

for (int i=0; i < (Math.pow(2,4)); i++) {
        System.out.println(Integer.toBinaryString(i));
}

这个的输出结果是：

0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111

这段文字是关于二进制数的输出结果。

- xsiraul

3

如果你不需要同时拥有所有排列，一个聪明的做法是 事先不分配内存 ，只需编写一个算法来 即时计算 想要的strX。

这样做的优点是:

可以处理 任意大的排列，而无需分配所有排列的内存
由于算法不存储任何内容，它是 线程友好 的
你只需要为你想要的行付费。例如，如果n=1,000，但你只需要一些排列，这将会更快，并且只需要很少的内存（仅相当于一行）

为了方便您开始，算法的接口可能看起来像这样：

boolean[] getRow( int rowNumber, int nItems )

因此，你可以调用getRow(5,3)来从函数中返回str5。我把实现的细节留给你（这不难）。

- kfmfe04

1

将其实现在一个函数中 -

static public ArrayList<boolean[]> getBoolArr(int length) {
        int numOptions = 1 << length;
        ArrayList<boolean[]> finalArray = new ArrayList<boolean[]>();
        for(int o=0;o<numOptions;o++) {
            boolean[] newArr = new boolean[length];
            for(int l=0;l<length;l++) {
                int val = ( 1<<l ) & o;
                newArr[l] = val>0;
            }
            finalArray.add(newArr);
        }
        return finalArray;
    }

使用示例：

ArrayList<boolean[]> res = getBoolArr(2); //2 is your length, change it however you want.

- Alon Amir

对我没用。如果我使用较小的数字作为长度，我会得到越界异常。如果我使用大数字，我会得到一位数字的输出。我不理解所有的<<和其他符号。能否解释一下？ - snotyak

再试一次，它可以运行。我把代码放进一个函数里，所以不会出错（见更新）。如果您有任何问题，请告诉我。'<<'和'&'是位操作符。请参考http://www.fredosaurus.com/notes-cpp/expressions/bitops.html的解释（它适用于Java）。 - Alon Amir

1

这是我在Java中的实现方式

public class NbitsStrings {
    int[] arrA;
    public static void main(String[] args) throws java.lang.Exception {
        Scanner input = new Scanner(System.in); //Input the Number Of bits you want.
        int n = input.nextInt();
        NbitsStrings i = new NbitsStrings(n);
        i.nBits(n);
    }
    public NbitsStrings(int n) {
        arrA = new int[n];
    }
    public void nBits(int n) {
        if (n <= 0) {
            StringBuilder builder = new StringBuilder();
            for (int value : arrA) {
                builder.append(value);
            }
            String text = builder.toString();
            System.out.println(text);
        } else {
            arrA[n - 1] = 0;
            nBits(n - 1);
            arrA[n - 1] = 1;
            nBits(n - 1);
        }
    }
}

- devDeejay

0

javascript 实现与重复问题相关 https://stackoverflow.com/questions/42591231/calculate-all-possible-combinations-of-n-off-on-elements。

与所有数字一样，存在一种数字集之间的关系，一旦识别出模式，就可以使用加法来推导数组集合中特定索引处数字集之间的关系。

let [N, n1, n2, n3] = [0, 1, 9, 89];

let [res, max] = [Array(Array(3).fill(N)), Math.pow(2, 3)];

for (let i = 1, curr; i < max; i++) {

  if ([1, 3, 5, 7].some(n => n === i)) {
    N += n1;
  }

  if ([2, 6].some(n => n === i)) {
    N += n2;
  }

  if (i === max / 2) {
    N += n3;
  }

  curr = Array.from(String(N), n => +n);

  if (N < 100) {
    while (curr.length < 3) {
      curr.unshift(n1 - 1);
    }
  }

  res.push(curr);

}

console.log(res);

- guest271314

0

这是我在Scala中实现的方式

def combinations(n: Int): List[List[Int]] = {
 val numbers = scala.math.pow(2, n).toInt 
 //Convert each to binary equivalent 
 def toBinary(decimal: Int, binary: List[Int]): List[Int] = {
  if (decimal <= 0)
    return le(binary)
  toBinary(decimal / 2, (decimal % 2) :: binary)
 }
 // Size alignment 
 def le(binary: List[Int]):List[Int]=
  {
    if(binary.length!=n) le(0::binary) else binary
  }
 def getCombinations(n: Int, list: List[List[Int]]): List[List[Int]] = {
  if (n < 0)
    return list
  getCombinations(n - 1, toBinary(n, Nil) :: list)
 }
 getCombinations(numbers - 1, Nil)
}

示例输出：

combinations(2) //List(List(0, 0), List(0, 1), List(1, 0), List(1, 1))
combinations(3) //List(List(0, 0, 0), List(0, 0, 1), List(0, 1, 0), List(0, 1, 1), List(1, 0, 0), List(1, 0, 1), List(1, 1, 0), List(1, 1, 1))

感谢我的朋友詹姆斯·A。

- Jemal Ahmed

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- LazyCubicleMonkey · Accepted Answer

以下是生成真值表的代码...（由于数组大小限制，该代码仅适用于32位（如果需要，您可以更改大小变量并将布尔值存储为1/0）:

int size = 3;
    int numRows = (int)Math.pow(2, size);
    boolean[][] bools = new boolean[numRows][size];
    for(int i = 0;i<bools.length;i++)
    {
        for(int j = 0; j < bools[i].length; j++)
        {
            int val = bools.length * j + i;
            int ret = (1 & (val >>> j));
            bools[i][j] = ret != 0;
            System.out.print(bools[i][j] + "\t");
        }
        System.out.println();
    }