Sets that contain no subsets that form nontrivial (length 3 or more) arithmetic progressions (sometimes called nonaveraging sets) have an application to a particular problem in communication complexity, which in turn has applications to circuit design. For a given $n$, larger subsets of $\{0, \ldots, n-1\}$ with no arithmetic progressions generally yield better results for that application. For example, $\{0, 2, 3, 10, 12, 15, 16, 19\}$ has no arithmetic progressions, but neither does $\{0, 1, 5, 6, 8, 13, 14, 17, 19\}$ and the latter is likely more useful because it is larger. Note that there is no larger subset of $\{0, \ldots, 19\}$ that is free of arithmetic progressions. For example, no other integers in that range can be added to the second set above (2 because it would result the progression 0, 1, 2; 3 because of 0, 3, 5; 4 because of 4, 5, 6, etc.).
Write a program called NoAP that constructs a set of
unique integers
that is free of nontrivial arithmetic progressions.
The range of integers to use, integers to start with in the set, and
the method by which to construct the set will be given as command-line
arguments as follows.
-greedy,
-backward, -skip, and -opt
where each method is described below; there may be zero or more
such arguments in any order.
-greedy specifies that the set should be constructed
greedily: let $start$ be one more than the largest must-include
integer or zero if there are none; then
each integer in the range $start, \ldots, n-1$ (which may be
empty) should be
checked in increasing order and added to the set exactly when doing
so does not create a nontrivial arithmetic progression with
any pair of integers already added in the set in any order.
-backward is the same as -greedy
except that the integers in $start, \ldots, n-1$ are
considered in decreasing order.
-skip is also like -greedy but
allows more control over the order in which the
integers in the range $start, \ldots, n-1$ are considered:
-skip will be followed by two integers $first$
and $step$ and the integers should be considered in the
order $first$, $first + step$, $first + 2\cdot step, \ldots$,
wrapping around from the end of the range to the beginning as
necessary until no more values will be added
(equivalently, consider the list $start, \ldots, n-1, start, \ldots, n-1, start, \ldots$ and begin at the first ocurrence of $first$, skipping
$step$ items through the list each time).
-opt specifies that the largest possible
set should be constructed. If there are multiple sets of the
largest possible size then the lexicographically first one
must be output (the lexicographic ordering of sets of equal size
considers $A$ to come before $B$ if the smallest element in one
but not the other is in $A$). If you do not implement this option then
ignore it when it is present.
The output of your program must be written to standard output with one
line per method specifed on the command line (assuming no errors),
and the output for
the methods should be given in the order they are listed on the
command line. Methods may be listed more than once and in that case
the output will be repeated for each time they appear after the
first
(again, assuming no errors).
Each line must be terminated by a newline character and
must be in the form
-method: k [x1, x2, x3, ..., xk]
where -method is -greedy, -backward,
-skip first step,
or -opt, where k is the size of
the set constructed, and the xi are the elements of
the constructed set in increasing order.
Your program must perform the following error-checking (where each error message should end with a newline character):
NoAP: n must not be negative; was value where
value is replaced by the value of $n$ (and display this message
for 0 even though it is not entirely appropriate in that case).
NoAP: integer out of range value where value
is the first must-include integer given on the command line
that is outside the valid range.
-skip
method is outside the range $start, \ldots, n-1$ then display the
error message NoAP: invalid first value
where value is replaced by $first$.
-skip
method is outside the range $1, \ldots, n - start$ then display
the error message NoAP: invalid step value where
value is replaced by $step$. (But if the corresponding
$first$ argument was also invalid then only display the error message
for the $first$ argument.)
-skip, and any
subsequent methods are not used. In any case there
should be no additional output beyond the first error message.
Do not treat the case where there is a nontrivial arithmetic progression
among the must-include integers as an error; in that case display
0 [] for the constructed set for each requested method
(as long as there are no other errors).
Aside from -opt, all methods for constructing the sets
must run in $O(n^3)$ time.
Points for the optional -opt method will be added after any
end-of-semester grade scaling. The -opt method
will graded on increasing values of $n$ with
a fixed time limit and the number of bonus points will depend in part
on how many tests complete within the time limit.
If there are any other violations of the specifications for command-line arguments then your program must behave gracefully: it must not crash or go into an infinite loop.
NoAP 15 2 4 8 -greedy -backward -skip 12 2 -opt then the output should
be
-greedy: 5 [2, 4, 8, 9, 11] -backward: 6 [2, 4, 8, 10, 11, 13] -skip 12 2: 4 [2, 4, 8, 10] -opt: 6 [2, 4, 8, 10, 11, 13]because
-greedy selects 9, omits 10 (8 9 10), selects 11, omits 12
(4 8 12), omits 13 (9 11 13), and omits 14 (2 8 14)
-backward omits 14 (2 8 14), selects 13, omits 12 (4 8 12),
selects 11, selects 10, and omits 9 (8 9 10)
-skip 12 2 omits 12 (4 8 12), omits 14 (2 8 14), selects 10,
and can't check the odd possibilities
-opt constructs the same set as -backward
because that is the largest possible set in this case.
You can check that your results for -opt are as large as they can
be by referring to the Online Encylopedia
Of Integer Sequences entry A003002,
which gives the size of the largest set up to $n=77$
and some examples (shifted over
by one since they list subsets of $\{1, \ldots, n\}$ instead of
$\{0, \ldots, n-1\}$);
see Finding large 3-free sets I: the small n case in
JCSS vol 74:4
for the size of the largest possible set up to $n=187$ (without examples
but with descriptions of
some improvements to the standard backtracking algorithm).
You will also have to make sure your output
is the lexicographically first set of the given size (all of the examples
from OIS I checked were the lexicographically first ones).