如何在 JAVA 中获得 0 和 1 位的所有可能排列

Question

我需要长度为 3 的位的排列输出（顺序无关紧要，因为 0 和 1 的初始组合是随机生成的）：

[0,0,0]

[0,0,1]

[0,1,0]

[0,1,1]

[1,0,0]

[1,0,1]

[1,1,0]

[1,1,1]

我已经完成了，但似乎有重复，并且没有显示一些可能的排列，我不知道为什么。这是我的代码：

'

  ArrayList<Item> itemsAvailable = new ArrayList<Item>();
  ArrayList<Integer>bits = new ArrayList<Integer>();
  ArrayList<ArrayList<Integer>> tried = new ArrayList<ArrayList<Integer>>();

    itemsAvailable.add(new Item(5,4));
    itemsAvailable.add(new Item(12,10));
    itemsAvailable.add(new Item(8,5));

    System.out.println("itemsAvailable: " + itemsAvailable);

    Random r = new Random();

    //permutations
    for(int i = 0; i < Math.pow(2,itemsAvailable.size()); i++){
        //Generate random bits

        for(int j = 0; j < itemsAvailable.size(); j++){
            int x = 0;

            if (r.nextBoolean())
                x = 1;

            bits.add(x);

        }


        System.out.println("Added to bits #" + (i+1) + ": " + bits);

        bits = new ArrayList<Integer>();
    }

'

我获得的输出是：

添加到位 #1：[0, 0, 1]

添加到位 #2：[1, 1, 0] - 重复

添加到位 #3：[1, 0, 1]

添加到位 #4：[0, 0, 1]

添加到位 #5：[0, 0, 0] - 重复

添加到位 #6：[1, 1, 0] - 重复

添加到位 #7：[1, 1, 1]

添加到位 #8：[0, 0, 0] - 重复

因此，由于位是随机生成的，我如何获得 8 种不同的排列？请帮忙。

谢谢你。

Answer 1

有一个更简单的方法来解决这个问题。想想这些位在二进制中代表什么，在无符号二进制补码中：

• [0,0,0] -> 0
• [0,0,1] -> 1
• [0,1,0] -> 2
• ...
• [1,1,1] -> 7

因此，获得所有这些排列的简单方法是：

for (int i = 0; i < 8; ++i) {
    bits.add(i);
}

这是8从哪里来的？它只是 2^3，因为你想要长度 3。

这种技术最多适用于 31 位，因为 Java 的 int 类型是有符号的（而上述基本上将其视为无符号，它适用于那些较低的数字）。

您可以通过使用 long 而不是 int 将其提高到 2^63，并且您可以通过枚举所有long来获得 64-length 。除此之外，您将需要一种不同的方法；但是 2^64 长，每长 8 个字节，大约是 1.5e11 GB——所以在你需要更复杂的算法之前，你已经用完了 RAM。