How can I get a set of frequencies for a certain recurring number in an array?

Question

So let's say that I have an array of zeroes, where the number 1 occasionally occurs.

For example, let's say I have the following array:

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

The output I am trying to get is the following descriptions about the positions of the number 1:

Every 5th starting with 2
Every 11th starting with 3
Every 7th starting with 0

We can see that if we start with an array of zeroes:

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

Then we add a 1 every 5th number starting with 2:

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

Then we add a 1 every 11th number starting with 3:

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

Then we add a 1 every 7th number starting with 0:

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

We get the array that we started out with.
One obvious thing is that there is more than one set of instructions that result in this array. For example, instead of the third instruction Every 7th starting with 0, we could have stated the instruction Every 21st starting with 0, or Every 1000000th starting with 21. Therefore, an obvious solution for this problem is to find each location of 1, and make each instruction Every [large number]th starting with [a certain position of 1].

However, I am looking for an algorithm that can find the most optimal, or close to the most optimal, set of instructions that gives the locations of the 1's in the array.

Based on its applications and input, the discrete Fourier transform looks promising; however, since it gives a pair of numbers for each value in the array, this doesn't seem very efficient.

So, are there any algorithms out there (perhaps in the Fourier family?) that can help me do this?

Thank you!

---

EDIT - for clarification, I don't care about the length of the array. Feel free to pad it with zeroes to the nearest power of two, or anything else.

EDIT 2 - if needed, feel free to make a rule of removing a 1. For instance, Remove every 6th starting with 4 would also work.

Answer 1

The following program uses rules that have a start and an end. The rules are allowed to overlap, so that a 1 could be used in 2 or more rules. It would be very easy to modify the code if that isn't what you want.

If the number of 1s is small it should be very fast, but it won't scale well.

It isn't very "clever". All it does is aim to knock out as many ones at each stage as possible. This approach is not optimal but it should be very good in most cases. For example, if you start with

1 1 1 1 1 0 1 1 1 1 1 

the first rule found is

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

because it uses six ones. However, the best solution clearly needs only two rules involving five 1s. I think it would be very difficult to find an efficient algorithm that always finds the best answer.

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