数组Java：写出所有包含K1的Nbit序列

Question

我应该写一个程序，用k1s打印出所有可能的N位序列，其余的（N-K）是0。还应该有一个计数器，指示最后有多少个序列

在我的例子中，N=9和K=3，因此程序应该写出如下内容：

111000000
110100000
...
101100000
101010000
...
000000111
Total: 84

到目前为止，我的代码如下所示

// N bits and K 1s
import java.util.ArrayList;
import java.util.Arrays;

public class Sequence {

    public static void main(String[] args) {

        ArrayList<int[]> all = new ArrayList<>();
        int counter = 0;
        int first = 0;
        int second;
        int third;

        for (int i = first; i < 9; i++) {
            int[] sequence = {0, 0, 0, 0, 0, 0, 0, 0, 0};
            // the 1st "1"
            sequence[i] = 1;

            second = i + 1;

            for (int j = second; j < 9; j++) {
                int[] seq2 = sequence;
                // the 2nd "1"
                seq2[j] = 1;

                third = j + 1;
                for (int l = third; l < 9; l++) {
                    int[] seq3 = seq2;
                    // the 3rd "1"
                    seq3[l] = 1;
                    all.add(seq3); 
                    counter++;

                    seq3[l] = 0;
                    third++;
                }

                second++;
            }   

            first++;
        }

        for (int[] sequences : all) {
            System.out.println(Arrays.toString(sequences));
        }
        System.out.println("Total: " + counter);
    }   
}

但它似乎不起作用，我也不明白为什么。代码是用java编写的，我对9位序列使用了一个由9个整数组成的数组列表

Answer 1

你几乎把它做好了

你的问题是：

int[] seq2 = sequence;

在这里：

int[] seq3 = seq2;

这些分配意味着您只有一个不断更改并添加到输出列表中的数组

将其更改为：

int[] seq2 = Arrays.copyOf(sequence, sequence.length);

以及：

int[] seq3 = Arrays.copyOf(seq2, seq2.length);

还要删除这一行（因为在每次迭代中都会创建一个新数组，所以不需要清除第l个元素）：

seq3[l] = 0;

您将获得以下输出：

[1, 1, 1, 0, 0, 0, 0, 0, 0]
[1, 1, 0, 1, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 1, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 1, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 1, 0, 0]
[1, 1, 0, 0, 0, 0, 0, 1, 0]
[1, 1, 0, 0, 0, 0, 0, 0, 1]
[1, 0, 1, 1, 0, 0, 0, 0, 0]
[1, 0, 1, 0, 1, 0, 0, 0, 0]
[1, 0, 1, 0, 0, 1, 0, 0, 0]
[1, 0, 1, 0, 0, 0, 1, 0, 0]
[1, 0, 1, 0, 0, 0, 0, 1, 0]
[1, 0, 1, 0, 0, 0, 0, 0, 1]
[1, 0, 0, 1, 1, 0, 0, 0, 0]
[1, 0, 0, 1, 0, 1, 0, 0, 0]
[1, 0, 0, 1, 0, 0, 1, 0, 0]
[1, 0, 0, 1, 0, 0, 0, 1, 0]
[1, 0, 0, 1, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 1, 1, 0, 0, 0]
[1, 0, 0, 0, 1, 0, 1, 0, 0]
[1, 0, 0, 0, 1, 0, 0, 1, 0]
[1, 0, 0, 0, 1, 0, 0, 0, 1]
[1, 0, 0, 0, 0, 1, 1, 0, 0]
[1, 0, 0, 0, 0, 1, 0, 1, 0]
[1, 0, 0, 0, 0, 1, 0, 0, 1]
[1, 0, 0, 0, 0, 0, 1, 1, 0]
[1, 0, 0, 0, 0, 0, 1, 0, 1]
[1, 0, 0, 0, 0, 0, 0, 1, 1]
[0, 1, 1, 1, 0, 0, 0, 0, 0]
[0, 1, 1, 0, 1, 0, 0, 0, 0]
[0, 1, 1, 0, 0, 1, 0, 0, 0]
[0, 1, 1, 0, 0, 0, 1, 0, 0]
[0, 1, 1, 0, 0, 0, 0, 1, 0]
[0, 1, 1, 0, 0, 0, 0, 0, 1]
[0, 1, 0, 1, 1, 0, 0, 0, 0]
[0, 1, 0, 1, 0, 1, 0, 0, 0]
[0, 1, 0, 1, 0, 0, 1, 0, 0]
[0, 1, 0, 1, 0, 0, 0, 1, 0]
[0, 1, 0, 1, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 1, 1, 0, 0, 0]
[0, 1, 0, 0, 1, 0, 1, 0, 0]
[0, 1, 0, 0, 1, 0, 0, 1, 0]
[0, 1, 0, 0, 1, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 1, 1, 0, 0]
[0, 1, 0, 0, 0, 1, 0, 1, 0]
[0, 1, 0, 0, 0, 1, 0, 0, 1]
[0, 1, 0, 0, 0, 0, 1, 1, 0]
[0, 1, 0, 0, 0, 0, 1, 0, 1]
[0, 1, 0, 0, 0, 0, 0, 1, 1]
[0, 0, 1, 1, 1, 0, 0, 0, 0]
[0, 0, 1, 1, 0, 1, 0, 0, 0]
[0, 0, 1, 1, 0, 0, 1, 0, 0]
[0, 0, 1, 1, 0, 0, 0, 1, 0]
[0, 0, 1, 1, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 1, 1, 0, 0, 0]
[0, 0, 1, 0, 1, 0, 1, 0, 0]
[0, 0, 1, 0, 1, 0, 0, 1, 0]
[0, 0, 1, 0, 1, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 1, 1, 0, 0]
[0, 0, 1, 0, 0, 1, 0, 1, 0]
[0, 0, 1, 0, 0, 1, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 1, 1, 0]
[0, 0, 1, 0, 0, 0, 1, 0, 1]
[0, 0, 1, 0, 0, 0, 0, 1, 1]
[0, 0, 0, 1, 1, 1, 0, 0, 0]
[0, 0, 0, 1, 1, 0, 1, 0, 0]
[0, 0, 0, 1, 1, 0, 0, 1, 0]
[0, 0, 0, 1, 1, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 1, 1, 0, 0]
[0, 0, 0, 1, 0, 1, 0, 1, 0]
[0, 0, 0, 1, 0, 1, 0, 0, 1]
[0, 0, 0, 1, 0, 0, 1, 1, 0]
[0, 0, 0, 1, 0, 0, 1, 0, 1]
[0, 0, 0, 1, 0, 0, 0, 1, 1]
[0, 0, 0, 0, 1, 1, 1, 0, 0]
[0, 0, 0, 0, 1, 1, 0, 1, 0]
[0, 0, 0, 0, 1, 1, 0, 0, 1]
[0, 0, 0, 0, 1, 0, 1, 1, 0]
[0, 0, 0, 0, 1, 0, 1, 0, 1]
[0, 0, 0, 0, 1, 0, 0, 1, 1]
[0, 0, 0, 0, 0, 1, 1, 1, 0]
[0, 0, 0, 0, 0, 1, 1, 0, 1]
[0, 0, 0, 0, 0, 1, 0, 1, 1]
[0, 0, 0, 0, 0, 0, 1, 1, 1]
Total: 84

Answer 2

一个简单的方法是使用基于字符串的方法。以下是一个完整的工作解决方案：

int k = 3, n = 9, count = 0;
for (int i = 1 << n; i < 2 << n; i++) {
    if (Long.toString(i, 2).replace("0", "").length() == k + 1) {
        System.out.println(Long.toString(i, 2).substring(1));
        count++;
    }
}
System.out.println("Total: " +count);

我测试了这段代码，它产生了正确的输出。这会在一个数字范围内使用一个额外的前导值进行迭代，从而巧妙地避开截断前导零的问题

请注意，此实现最多只能处理62个。对于大于62的n，将循环类型更改为BigInteger：

int k = 3, n = 9, count = 0;
BigInteger end = new BigInteger("2").pow(n + 1);
for (BigInteger i = new BigInteger("2").pow(n); i.compareTo(end) < 0; i = i.add(BigInteger.ONE)) {
    if (i.toString( 2).replace("0", "").length() == k + 1) {
        System.out.println(i.toString( 2).substring(1));
        count++;
    }
}
System.out.println(count);

此实现适用于任意大的n值

---

如果您看到这段代码并想到“哦，性能！？”，在我的普通硬件上，第1个版本的代码执行时间约为20ms，第2个版本的代码执行时间约为40ms，速度足够快

---

顺便说一句，如果您绝对必须按照原来的顺序输出，请将循环更改为倒计时，而不是倒计时