如何为阵列中的某个重复数字获取一组频率？

Question

所以,假设我有一个零数组,偶尔会出现数字1.

例如,假设我有以下数组:

0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 1 0 0 1 0

我想要获得的输出是关于数字1的位置的以下描述:

每5个开始2个
每11个开始3个
每7个开始0

我们可以看到,如果我们从一个零数组开始:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

然后我们从2开始每5个数字加1:

0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0

然后我们从3开始每11个数字添加一个1:

0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0

然后我们从0开始每7个数字加1:

0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 1 0 0 1 0

我们得到了我们开始使用的数组.
一个显而易见的事情是,有一组指令导致这个数组.例如,代替第三指令Every 7th starting with 0,我们可以说的指令Every 21st starting with 0,或Every 1000000th starting with 21.因此,这个问题的一个明显的解决方案是找到每个位置1,并做出每条指令Every [large number]th starting with [a certain position of 1].

但是,我正在寻找一种能够找到最佳或接近最佳指令集的算法,该指令集给出了数组中1的位置.

基于其应用和输入,离散傅立叶变换看起来很有前景; 但是,因为它为数组中的每个值提供了一对数字,所以这看起来效率不高.

那么,有没有任何算法(也许在傅立叶家族？)可以帮助我做到这一点？

谢谢!

---

编辑 - 为了澄清,我不关心数组的长度.随意用零填充到最近的2的幂,或其他任何东西.

编辑2 - 如果需要,随意制定删除规则1.例如,Remove every 6th starting with 4也可以工作.

Answer 1

以下程序使用具有开始和结束的规则。规则允许重叠，以便 a1可以在 2 个或更多规则中使用。如果这不是您想要的，那么修改代码将非常容易。

如果 s 的数量1很小，它应该会非常快，但它不会很好地扩展。

这不是很“聪明”。它所做的一切都是为了在每个阶段淘汰尽可能多的人。这种方法不是最佳的，但在大多数情况下应该非常好。例如，如果您从

1 1 1 1 1 0 1 1 1 1 1 

找到的第一条规则是

Every 2th, starting at 1, ending at 11.

因为它使用了六个。然而，最好的解决方案显然只需要两条涉及五个 1 的规则。我认为找到一种总能找到最佳答案的有效算法是非常困难的。

public static void main(String[] args) {
    rulesFor(0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0);
}

public static void rulesFor(int... arr) {
    Set<Integer> allOnes = new HashSet<>();
    for (int i = 0; i < arr.length; i++)
        if (arr[i] == 1)
            allOnes.add(i);
    // Size 1 has to be done separately as the below code wouldn't work.
    if (allOnes.size() == 1) {
        int a = allOnes.iterator().next();
        System.out.println("Every 1st, starting at " + (a + 1) + ", ending at " + (a + 1) + ".");
        return;
    }
    Set<Integer> leftToRemove = new HashSet<>(allOnes);
    while (!leftToRemove.isEmpty()) {
        int low = -1;
        int high = -1;
        int d = -1;
        int removeTotal = -1;
        for (int a : leftToRemove) {
            for (int b : allOnes) {
                if (b == a)
                    continue;
                int d2 = Math.abs(b - a);
                int low2 = a;
                int high2 = a;
                int removeTotal2 = 1;
                while (true) {
                    if (!allOnes.contains(low2 - d2))
                        break;
                    low2 -= d2;
                    if (leftToRemove.contains(low2))
                        removeTotal2++;
                }
                while (true) {
                    if (!allOnes.contains(high2 + d2))
                        break;
                    high2 += d2;
                    if (leftToRemove.contains(high2))
                        removeTotal2++;
                }
                if (removeTotal2 > removeTotal) {
                    low = low2;
                    high = high2;
                    removeTotal = removeTotal2;
                    d = d2;
                }
            }
        }
        System.out.println("Every " + d + "th, starting at " + (low + 1) + ", ending at " + (high + 1) + ".");
        for (int i = low; i <= high; i += d)
            leftToRemove.remove(i);
    }
}