Let be the two input lengths and suppose numeric comparisons cost constant time. The list-based set representation determines which representation invariant each answer must preserve.
For unsorted lists allowing repetition, retain every left-hand occurrence whose value appears on the right for set intersection, and use list concatenation for set union:
interR xs ys = [x | x <- xs, x `elem` ys]
unionR xs ys = xs ++ ysThe resulting lists represent exactly the desired sets; repeated entries are permitted. Membership by sequential search makes
interR take time complexity in the worst case. The list concatenation in unionR costs to build its copied left spine and shares ys; fully enumerating the resulting list costs .For unsorted, duplicate-free inputs, the same intersection keeps uniqueness, while the union retains
xs and appends only right-hand elements absent from xs:interU xs ys = [x | x <- xs, x `elem` ys]
unionU xs ys = xs ++ [y | y <- ys, not (y `elem` xs)]Neither filtered list has internal repetitions, and the filter in
unionU also excludes overlap with xs. Both operations have worst-case time complexity, customarily written when both lengths are positive. Using the original xs for each membership test avoids searching an ever-growing output.interS [] ys = []
interS xs [] = []
interS (x:xs) (y:ys)
| x < y = interS xs (y:ys)
| x > y = interS (x:xs) ys
| otherwise = x : interS xs ys
unionS [] ys = ys
unionS xs [] = xs
unionS (x:xs) (y:ys)
| x < y = x : unionS xs (y:ys)
| x > y = y : unionS (x:xs) ys
| otherwise = x : unionS xs ysWhen , sortedness proves that cannot occur anywhere in the right list, so it can be discarded from the set intersection or immediately emitted to the set union. The symmetric argument handles ; equal heads are consumed together. Each step consumes at least one input head, so both have worst-case time complexity. These bounds assume the sorted representation invariant is already established; sorting arbitrary inputs has its own cost.
| Representation | Set intersection | Set union, including output traversal |
|---|---|---|
| Unsorted, repetitions allowed | ||
| Unsorted, unique | ||
| Sorted, unique |
Use permutation generation by insertion: recursively arrange the tail, then insert the removed head in every possible position.
inserts x [] = [[x]]
inserts x (y:ys) = (x:y:ys) : map (y:) (inserts x ys)
perms [] = [[]]
perms (x:xs) = concat (map (inserts x) (perms xs))The map function in
inserts prefixes y to each placement after the first position. For a list of length , the number of results obeys and , so mathematical induction gives . Every result still contains the same old elements and the one inserted element.Let be the length of
perms xs for an input of length . There is exactly one permutation of the empty list, namely the empty list itself: hence perms [] is [[]], with length one. For a nonempty input, each recursively obtained permutation has length and gives placements. ThusLength alone would not exclude repeated answers. Since the input elements are distinct, removing the distinguished element from any result uniquely recovers both its placement and the shorter permutation. Hence different construction choices give different outputs, and every desired permutation is obtained by inserting into its restriction to xs. For [a,b,c], this code yields [a,b,c], [b,a,c], [b,c,a], [a,c,b], [c,a,b], [c,b,a], each exactly once. Articles by others on the same topic
There are currently no matching articles.