Let again be the total. Reject unless is divisible by three, and put . Define to mean that the first occurrences can be assigned to three groups so that the first two groups have sums and . Their third sum is already determined by the processed list prefix sum minus , so it need not be stored as another coordinate.
Initialize true and all other states false. For each reachable state, assign the next occurrence to exactly one group:The three transitions put the occurrence in the third, first or second group, respectively. Using a fresh layer prevents reusing it. Conversely, deleting the last occurrence from any valid list prefix assignment leaves exactly one predecessor state, so induction proves completeness as well as soundness. At the final state , the third sum is , giving precisely the required disjoint partition.
threeEqualParts(A):
S = sum of A
if S mod 3 != 0: return false
h = S/3
D[0..h,0..h] = false
D[0,0] = true
for each indexed entry a in A:
Next[0..h,0..h] = false
for x from 0 to h:
for y from 0 to h:
if D[x,y]:
Next[x,y] = true
if x+a <= h: Next[x+a,y] = true
if y+a <= h: Next[x,y+a] = true
D = Next
return D[h,h]There are states per layer and a constant number of transitions per state. Thus the time is , and rolling layers use space for nonempty inputs. The source mentions an additional integer in this part, but it does not occur in the stated equal-partition condition; the required target is determined by . Empty groups are allowed by the stated subset formulation.
Treat array entries as indexed occurrences, so equal numerical values may be selected independently. Put . Reject or . Define to mean that some subset of the first indices sums to . The base is and all other base entries are false. Considering whether index is selected givesOnly is needed, because all entries are positive. A one-dimensional implementation isDescending updates make both right-hand-side values belong to the previous list prefix: when updating , the smaller location has not yet been updated for this entry. This prevents using the same occurrence repeatedly. Induction on the list prefix proves the recurrence and the returned answer.
subsetSum(A, s):
S = sum of A
if s < 0 or s > S: return false
D[0..s] = false
D[0] = true
for each indexed entry a in A:
for t from s down to a:
D[t] = D[t] or D[t-a]
return D[s]The time is for nonempty input with , and space is . More generally one may fill through and answer every target from the same table. For a two-way equal partition, reject odd ; otherwise ask for target . A selected subset with that sum leaves its complement with the same sum. These are bounds polynomial in the numerical bound ; without that bound the method is pseudopolynomial in a binary-encoded unrestricted target.[ref]
Dynamic programming by Jeff Erickson. Chapter 3, §3.8, Subset Sum: include/exclude states and memoization
A strict majority element in the whole array must be a strict majority element in at least one half: otherwise summing the two non-majority element frequency bounds would give at most half of all entries. This observation supplies at most two candidates, but they must still be verified in the whole subarray.
majority(A, left, right):
if left == right: return NoMajority
if right - left == 1: return Candidate(A[left])
middle = floor((left + right)/2)
first = majority(A, left, middle)
second = majority(A, middle, right)
for candidate in the two returned tagged results:
if candidate is Candidate(x):
count = 0
for i from left to right-1:
if A[i] == x: count = count + 1
if 2*count > right-left: return Candidate(x)
return NoMajorityNoMajority is a separate result tag, not a possible input element. The two-candidate loop does not require ordering, hashing or conversion of arbitrary elements to a set. It may count the same candidate twice without changing correctness or the bound.Induction proves the recursive candidates correct. If the whole subarray has a majority element, the observation ensures it reaches the verification step; if a candidate passes the strict frequency test, it really is a majority element. The worst-case recurrence has two balanced recursive calls and linear combination work, so the running time is , with auxiliary recursion depth when the array is passed by index ranges. A different cancellation-based method can achieve linear time, but is not needed for this divide-and-conquer construction.
Sequential accumulation writes merged outputs of lengths . Its total work isThe growing list prefix is repeatedly copied, even though its internal order is already known.
Instead, divide the family of arrays into two nearly equal halves, recursively merge each half, and merge the two resulting sorted arrays. A balanced merge tree has levels; at each level at most entries are read or written in merges. Thus the bound is for , including the output work. Equivalently the recurrence in the number of arrays is . The one-array case simply returns it, or costs if a fresh output array is required.
There are three unnumbered cases inside this leaf.
For the nine-child recurrence, a recursion tree has subproblems of size about . There are constant-size leaves, and the total unit work over earlier levels is a geometric sum of the same order. Hence . This is also the first case of the master theorem, since and the additive work is constant.
For the decrementing recurrence, summing from the supplied base at three givesso here as well. Values at the smaller base indices remain one as specified.
For the recurrence that squares its recursive result, set . Then above the base range. LetAfter expansions, , giving the exact answerFor powers of two this is . For arbitrary positive integer , the exact values form plateaux: , while . In general . It is not uniformly over integer : near the top of a plateau the exponent is closer to . Keeping the integer halving is essential; the ordinary linear master theorem does not apply to squaring .
Merge by comparing the present heads and consuming just the chosen one. The implementation uses only the functional representation:The two recursive inputs are the disjoint initial and final portions of the represented sequence; they preserve every occurrence and have smaller lengths when . In
merge' :: Ord a => List a -> List a -> List a
merge' left right
| null' left = right
| null' right = left
| head' left <= head' right =
cons' (head' left) (merge' (tail' left) right)
| otherwise =
cons' (head' right) (merge' left (tail' right))
mergeSort' :: Ord a => List a -> List a
mergeSort' input =
let n = length' input
middle = n `div` 2
in if n <= 1 then input
else merge' (mergeSort' (take' middle input))
(mergeSort' (drop' middle input))merge', the smaller current head can precede every remaining value in both sorted inputs. Selecting the left head on equality preserves stability. Each merge step reduces the total number of remaining elements, and induction proves a sorted permutation of the original sequence.This establishes algorithm termination and correctness on total finite representations, not an unconditional implementation bound. Nested index functions can make queries costly, and repeatedly finding lengths or heads may revisit them. The familiar merge-sort bound assumes suitable constant-time access or consumption primitives; the source's function-only representation supplies no such cost guarantee.
Clamp a nonpositive count to zero. Taking restricts the domain of present indices; dropping translates that domain:For finite length , the first two operations give lengths and , respectively. The length loop reaches the first absent index, namely , so it terminates for a total finite representation. It does not terminate on an infinite represented sequence. There is no assumption that an arbitrary stored query function takes constant time.
take' :: Int -> List a -> List a
take' count (List f) = List query
where
k = max 0 count
query i
| i < 0 || i >= k = Nothing
| otherwise = f i
drop' :: Int -> List a -> List a
drop' count (List f) = List query
where
k = max 0 count
query i
| i < 0 || i > maxBound - k = Nothing
| otherwise = f (i+k)
length' :: List a -> Int
length' (List f) = countFrom 0
where
countFrom i = case f i of
Nothing -> i
Just _ -> countFrom (i+1)Preserve absence and transform only a present value:Every query keeps its presence status, so the represented length and the no-holes invariant are unchanged. The transformed element is computed only when demanded.
map' :: (a -> b) -> List a -> List b
map' g (List f) = List (\i -> case f i of
Nothing -> Nothing
Just x -> Just (g x))Inspect index zero for emptiness and the head; removing the head shifts the query in the other direction:The no-holes invariant makes the zero-index test sufficient for emptiness. Both
null' :: List a -> Bool
null' (List f) = case f 0 of
Nothing -> True
Just _ -> False
head' :: List a -> a
head' (List f) = case f 0 of
Nothing -> error "head of empty representation"
Just x -> x
tail' :: List a -> List a
tail' input@(List f)
| null' input = error "tail of empty representation"
| otherwise = List query
where
query i
| i < 0 || i == maxBound = Nothing
| otherwise = f (i+1)head' and tail' have the precondition that the representation is nonempty and signal an error when it is violated. On a nonempty representation, tail' removes exactly one position. The overflow guard is consistent with finite lengths at most maxBound.The embedding is a right fold interpreting each source constructor by its new counterpart:Induction on the finite source list proves that querying index returns its th element exactly when lies in range. The empty case is
list' :: [a] -> List a
list' = foldr cons' nil'nil'; the cons case shifts every tail index as established in part (b). This is the only part of Question 4 whose implementation uses the conventional list type.The empty representation is nowhere present; prepending shifts all old positions by one:For a represented length ,
nil' :: List a
nil' = List (\_ -> Nothing)
cons' :: a -> List a -> List a
cons' x (List f) = List query
where
query i
| i < 0 = Nothing
| i == 0 = Just x
| otherwise = f (i-1)cons' represents length , provided that length is representable. Index zero is the new head and each later valid index asks for the preceding old position. The no-holes invariant is preserved. No conventional list is built by either constructor.A function returning an optional value supplies the representation:For a finite represented list, require a length such that every index returns
newtype List a = List (Int -> Maybe a)Just its element and every other index returns Nothing. Thus there are no holes: absence at a nonnegative index implies absence at every later index. The type alone does not enforce this invariant, or algorithm termination of a query. An infinite represented sequence may instead have a present value at every nonnegative index; operations requiring its length will not terminate.The implementations below return
Nothing at negative indices. Finite lengths, requested counts and intermediate indices are assumed to fit Int; explicit guards on index shifts also prevent arithmetic wraparound from exposing an invalid element.Generate a row while respecting the forbidden symbols in each column. Selection returns an element together with the still-available elements:The invariant of
select :: [a] -> [(a,[a])]
select [] = []
select (x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- select xs]
row :: [Int] -> [[Int]] -> [[Int]]
row [] [] = [[]]
row remaining (used:otherColumns) =
[x:rest | (x,available) <- select remaining,
x `notElem` used,
rest <- row available otherColumns]
row _ _ = []
latinPruned :: Int -> [[[Int]]]
latinPruned n
| n < 0 = error "negative order"
| otherwise = build n (replicate n [])
where
build 0 usedColumns = [[]]
build remainingRows usedColumns =
[r:rest | r <- row [1..n] usedColumns,
rest <- build (remainingRows-1)
(zipWith (:) r usedColumns)]row is that remaining contains exactly the unused symbols of this row, while each member of the column list records symbols used by earlier rows. Selecting removes a symbol, so it cannot repeat in the current row; the membership test prevents a column repetition. A complete row uses every symbol once. Updating the column histories preserves the invariant for the next recursive call.Every complete generated square is therefore valid without a final filter. Conversely, take any valid target square: its next row passes every selection and column test, so induction keeps a branch constructing that target. Distinct choices from the initially distinct symbols cannot generate the same square twice. Dead-end partial squares may still be explored; the method promises to avoid constructing complete invalid squares, not to foresee every future dead end. Independent enumeration gives 1, 2, 12 and 576 squares at orders one through four.
Choose each row from the permutations of the symbols:Every Latin square remains a candidate, because each of its rows is one of those permutations. Conversely every candidate has valid rows, so only its columns still need checking. There are candidates instead of : at order four, rather than more than four billion. The improvement is substantial but does not make exhaustive generation practical at arbitrary orders. One can replace
squaresRows :: Int -> [[[Int]]]
squaresRows n
| n < 0 = error "negative order"
| otherwise = cp (replicate n (perms [1..n]))
latinRows :: Int -> [[[Int]]]
latinRows = filter valid . squaresRowsvalid by a column-only test here, since row validity is guaranteed by construction.The generation count, before any validity test, is . It is at order three, at order four, and approximately at order five. Even an illustrative rate of one million complete candidates per second would require about 72 minutes at order four and about 9,444 years at order five, before accounting for the actual validity-checking cost. Thus order four is already expensive and order five is plainly impractical for this strategy; the exact threshold depends on the implementation and hardware, not just the mathematical count.
Candidate growth before filtering in two Latin-square generation strategies
. Original exact candidate counts, plotted on a base-ten logarithmic vertical axis. These are mathematical counts, not measured running times; pruning can avoid many invalid partial extensions as well. Details.The following predicate also checks the square's shape; The row tests guarantee that each row has length and contains each allowed symbol once. Because
sort is the three-way sorting function from Question 2:valid :: [[Int]] -> Bool
valid rows =
let n = length rows
symbols = [1..n]
goodRows = all (\r -> sort r == symbols) rows
goodColumns = all (\j -> sort [r !! j | r <- rows] == symbols)
[0..n-1]
in goodRows && goodColumns
latin :: Int -> [[[Int]]]
latin = filter valid . squares&& tests this condition first, the later column indexing is safe for a finite total input. The column tests establish the remaining Latin-square condition. Filtering therefore retains precisely the valid squares; it does not remove any different ordering of rows, columns or symbols as an alleged symmetry duplicate.For a nonnegative order, first enumerate every possible row and then every possible ordered selection of rows:Every one of the positions chooses one of symbols independently. Consequently the enumeration contains candidate squares for , each exactly once. The conventional order-zero extension produces one empty square. This is generation only; repeated symbols have not yet been rejected.
squares :: Int -> [[[Int]]]
squares n
| n < 0 = error "negative order"
| otherwise = cp (replicate n (cp (replicate n [1..n])))The empty family has one choice, the empty selection:A selection from the whole family consists uniquely of a choice from its first member and a selection from the remaining family. This bijection proves the combining equation and completeness by induction. If a member family is empty, there are no selections. The base is
cp :: [[a]] -> [[a]]
cp = foldr extend [[]]
where
extend choices suffixes = [x:ys | x <- choices, ys <- suffixes][[]], not []: otherwise every Cartesian product would incorrectly be empty.An unfold expands a seed into either no node or a bucket and two new seeds:The seed is the remaining list. Expanding a nonempty seed partitions it exactly as
unfoldTree :: (s -> Maybe (s,[a],s)) -> s -> Tree a
unfoldTree split seed =
case split seed of
Nothing -> Empty
Just (left,equal,right) ->
Node (unfoldTree split left) equal (unfoldTree split right)
toTreeUnfold :: Ord a => [a] -> Tree a
toTreeUnfold = unfoldTree split
where
split [] = Nothing
split (pivot:xs) =
let (lo,eq,hi) = partition3 pivot xs
in Just (lo,pivot:eq,hi)toTree does, and both child seeds are shorter. Induction establishes toTreeUnfold = toTree and algorithm termination on finite inputs. The unfold separates the local decomposition rule from the recursive construction of the tree.A tree fold replaces each constructor by its interpretation:Induction on the finite tree shows equality with
foldTree :: (b -> [a] -> b -> b) -> b -> Tree a -> b
foldTree combine zero Empty = zero
foldTree combine zero (Node left equal right) =
combine (foldTree combine zero left)
equal
(foldTree combine zero right)
fromTreeFold :: Tree a -> [a]
fromTreeFold = foldTree (\left equal right -> left ++ equal ++ right) []fromTree: the empty tree produces the empty output, and the combining function concatenates the two correctly flattened children around the node's bucket. The result type is independent of the key type; other choices can compute a size or another summary using the same structural recursion. There are unlisted articles, also show them or only show them.
