Pfthb

Self-Aware Arrays.

An integer array int A is self-aware if for each i < A.length, A[i] is the exact number of occurrences of i in A.

For example, [2, 0, 2, 0] is self-aware.

Write an algorithm accepts a positive integer n as input, when executed, prints out a list of all self-aware arrays of that length.

Here are some Self-aware arrays have been found. But I haven't found an algorithm.

N = 4
2, 0, 2, 0
1, 2, 1, 0

N = 5
2, 1, 2, 0, 0

N = 6
None

N = 7
3, 2, 1, 1, 0, 0, 0

N = 8
4, 2, 1, 0, 1, 0, 0, 0 

N = 9
5, 2, 1, 0, 0, 1, 0, 0, 0

N = 10
6, 2, 1, 0, 0, 0, 1, 0, 0, 0

N = 11
7, 2, 1, 0, 0, 0, 0, 1, 0, 0, 0

N = a
 a-4, 2, 1, <a-7 0s>, 1, 0, 0, 0 

Seems we have the properties

sum(A[i]) = n = sum(i * A[i])

A[0] = sum( (i-1) * A[i] ) i>=2

Outer loop: Generate all candidates of length n. This can be done with any convenient set product software; you need n elements in the range 0:n-1. For each candidate, filter and check (below).

Filter:

• The sum of the candidates elements must equal n. Note that if you're writing your own candidate generator, you can use this to greatly reduce the quantity of candidates.


• The first element can never be 0.

Check:
Count the quantity of each number 0:n-1 in order. The resulting list is your check count. If this list is equal to the original candidate, you have a solution: print it.

Shortcuts:
Are you allowed to use known results? It's long proved that for n >= 7, the formula you give is the only solution: you can directly generate the one solution and return. For n < 7, brute force will produce all valid solutions quite quickly.