E-99: 21-30
The next installment of the 99 Lisp problems. 27 and 28 are incomplete as I have not sat down to actually work through them yet. More research is needed to do multinomial coefficients. This batch of problems posed some challenge and required a bit of research and dusting off math skills, as well as getting familiar with Erlang's List Comprehension syntax. For your viewing pleasure:
%% Insert an element at a given position into a list.
%% Example: (insert-at 'alfa '(a b c d) 2) -> (A ALFA B C D)
p21(Elem, L, Pos) ->
p21insert(Elem, L, Pos, []).
p21insert(Elem, L, 1, NewL) ->
lists:reverse([Elem | NewL]) ++ L;
p21insert(Elem, [H | L], Pos, NewL) ->
p21insert(Elem, L, Pos-1, [H | NewL]).
%% Create a list containing all integers within a given range.
%% If first argument is smaller than second, produce a list in decreasing order.
%% Example: (range 4 9) -> (4 5 6 7 8 9)
p22(Start, End) when Start < End ->
p22range_asc(End-Start, [Start]);
p22(Start, End) ->
p22range_desc(Start-End, [Start]).
p22range_asc(0, L) ->
lists:reverse(L);
p22range_asc(Count, [H | L]) ->
p22range_asc(Count-1, [H+1, H | L]).
p22range_desc(0, L) ->
lists:reverse(L);
p22range_desc(Count, [H | L]) ->
p22range_desc(Count-1, [H-1, H | L]).
%% Extract a given number of randomly selected elements from a list.
%% The selected items shall bereturned in a list.
%% Example: (rnd-select '(a b c d e f g h) 3) -> (E D A)
%% Hint: Use the built-in random number generator and the result of
%% problem P20.
p23(L, Count) when length(L) < Count ->
p23rnd_select(L, length(L), []);
p23(L, Count) ->
p23rnd_select(L, Count, []).
p23rnd_select(_L, 0, RandL) -> RandL;
p23rnd_select(L, Count, RandL) ->
Rnd = random:uniform(length(L)),
V = lists:nth(Rnd, L),
p23rnd_select(p20(L, Rnd), Count-1, [V | RandL]).
%% Lotto: Draw N different random numbers from the set 1..M.
%% The selected numbers shall be returned in a list.
%% Example: (lotto-select 6 49) -> (23 1 17 33 21 37)
%% Hint: Combine the solutions of problems P22 and P23.
p24(Num, High) -> p23(p22(1, High), Num).
%% Generate a random permutation of the elements of a list.
%% Example: (rnd-permu '(a b c d e f)) -> (B A D C E F)
%% Hint: Use the solution of problem P23.
p25(L) -> p23(L, length(L)).
%% Generate the combinations of K distinct objects chosen from the N elements of a list
%% In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficients).
%% For pure mathematicians, this result may be great. But we want to really generate all the possibilities in a list.
%% Example: (combination 3 '(a b c d e f)) -> ((A B C) (A B D) (A B E) ... ) % Not the most efficient way, but generate the power set for the list and remove all but the sub-lists of length K
powerset([]) -> [[]];
powerset([H | T]) ->
SubPS = powerset(T),
lists:append(SubPS, lists:map(fun(E) -> [H | E] end, SubPS)).
p26(K, L) -> [X || X < - powerset(L), length(X) == K].
%% Group the elements of a set into disjoint subsets.
%% a) In how many ways can a group of 9 people work in 3 disjoint
%% subgroups of 2, 3 and 4 persons? Write a function that generates
%% all the possibilities and returns them in a list.
%% Example: (group3 '(aldo beat carla david evi flip gary hugo ida))
%% -> ( ( (ALDO BEAT) (CARLA DAVID EVI) (FLIP GARY HUGO IDA) ) ... )
p27([]) -> [].
%% b) Generalize the above predicate in a way that we can specify a
%% list of group sizes and the predicate will return a list of groups.
%% Example: (group '(aldo beat carla david evi flip gary hugo ida) '(2
%% 2 5)) -> ( ( (ALDO BEAT) (CARLA DAVID) (EVI FLIP GARY HUGO IDA) )
%% ... )
%% Note that we do not want permutations of the group members;
%% i.e. ((ALDO BEAT) ...) is the same solution as ((BEAT ALDO) ...).
%% However, we make a difference between ((ALDO BEAT) (CARLA DAVID)
%% ...) and ((CARLA DAVID) (ALDO BEAT) ...).
%% You may find more about this combinatorial problem in a good book
%% on discrete mathematics under the term "multinomial coefficients".
p28() -> [].
%% Sorting a list of lists according to length of sublists
%% a) We suppose that a list contains elements that are lists
%% themselves. The objective is to sort the elements of this list
%% according to their length. E.g. short lists first, longer lists
%% later, or vice versa.
%% Example: (lsort '((a b c) (d e) (f g h) (d e) (i j k l) (m n) (o)))
%% -> ((O) (D E) (D E) (M N) (A B C) (F G H) (I J K L))
p29(L) -> p29lsort(L).
%% code taken from Erlang Programming Examples -> List Comprehensions
%% -> QuickSort and adapted
p29lsort([]) -> [];
p29lsort([Pivot | L]) ->
p29lsort([ X || X < - L,
length(X) < length(Pivot)
])
++ [Pivot | p29lsort([ X || X = length(Pivot)])].
%% b) Again, we suppose that a list contains elements that are lists
%% themselves. But this time the objective is to sort the elements of
%% this list according to their length frequency;
%% i.e., in the default, where sorting is done ascendingly, lists with
%% rare lengths are placed first, others with a more frequent length
%% come later.
%% Example: (lfsort '((a b c) (d e) (f g h) (d e) (i j k l) (m n)
%% (o))) -> ((i j k l) (o) (a b c) (f g h) (d e) (d e) (m n))
%% Note that in the above example, the first two lists in the result
%% have length 4 and 1, both lengths appear just once. The third and
%% forth list have length 3 which appears twice (there are two list of
%% this length).
%% And finally, the last three lists have length 2. This is the most
%% frequent length.
p30(L) -> p30lfsort(L).
p30lfsort([]) -> [];
p30lfsort([H | L]) ->
Grouped = p30group(L, [[H]]),
Sorted = p29(Grouped),
p30ungroup(Sorted, []).
p30group([], Grouped) -> Grouped;
p30group([H | L], Grouped) -> p30group(L, p30insert(H, Grouped, [])).
%% insert Elem in to a group with the same length, or create a new
%% group for the length of Elem
p30insert(Elem, [], PrevGroups) ->
lists:reverse([[Elem] | PrevGroups]);
p30insert(Elem, [ [GroupH | GroupT] | RestGrouped], PrevGroups)
when length(GroupH) == length(Elem) ->
PrevGroups ++ [ [GroupH, Elem | GroupT] | RestGrouped];
p30insert(Elem, [ [GroupH | GroupT] | RestGrouped], PrevGroups) ->
p30insert(Elem, RestGrouped, [[GroupH | GroupT] | PrevGroups]).
%% remove length-specific groupings
p30ungroup([], Ungrouped) -> lists:reverse(Ungrouped);
p30ungroup([H | L], Ungrouped) when not is_list(H) ->
[[H | L] | Ungrouped];
p30ungroup([Group | L], Ungrouped) ->
p30ungroup(Group, []) ++ p30ungroup(L, Ungrouped).