Courses/CS 460/Fall 2005/Homework/Brian Smith/Oct 15

From CSWiki

[edit] Permute and Permute K

Permute returns all permutations without repetition that are the same length as the original input. PermuteK allows you to specify the length of the permutations returned. I thought about trying Combine but had to abandon it for other homework.

Perms and Combs

%%% Pre-defined from class notes %%%

declare
proc {Delete X In ?Out}
   H T in
   In = H | T
   choice
      H = X
      Out = T
   [] NewT in
      Out = H | NewT
      {Delete X T NewT}
   end
end 

%%% PERMUTE %%%
% permutations using all elements

proc {Permute In ?Out}
   choice
      In = nil
      Out = nil
   [] X Xr in
      {Delete X In Xr}
      Out = X | {Permute Xr}
   end
end
%{Browse {SearchAll fun {$} {Permute [a b c d]} end} }

%%% PERMUTE K %%%  (presented)
% permutations of length K

declare
proc {PermuteK In K ?Out}
   choice
      In = nil
      Out = nil
   [] X Xr in
      (K == 1) = true
      {Delete X In Xr}
      Out = X | nil
   [] X Xr in
      (K > 1) = true
      {Delete X In Xr}
      Out = X | {PermuteK Xr K-1}
   end
end
{Browse {SearchAll fun {$} {PermuteK [a b c d] 4} end} }  % 24
{Browse {SearchAll fun {$} {PermuteK [a b c d] 3} end} }  % 24
{Browse {SearchAll fun {$} {PermuteK [a b c d] 2} end} }  % 12
{Browse {SearchAll fun {$} {PermuteK [a b c d] 1} end} }  % 4

[edit] New PermuteK

We cleaned up my PermuteK in class.

declare
proc {PermuteK In K ?Out}
   choice
      ((In == nil) orelse (K == 0)) = true
      Out = nil
   [] X Xr in
      (K >= 1) = true
      {Delete X In Xr}
      Out = X | {PermuteK Xr K-1}
   end
end
{Browse {SearchAll fun {$} {PermuteK [a b c d] 4} end} }  % 24
{Browse {SearchAll fun {$} {PermuteK [a b c d] 3} end} }  % 24
{Browse {SearchAll fun {$} {PermuteK [a b c d] 2} end} }  % 12
{Browse {SearchAll fun {$} {PermuteK [a b c d] 1} end} }  % 4
{Browse {SearchAll fun {$} {PermuteK [a b c d] 0} end} }  % nil

[edit] Other List Functions

These are less interesting because there's only one valid answer, despite the fact that more than one thread from SearchAll succeeds. Using SearchOne returns the first (and correct) answer, but I don't think this is the intended use of choice and concurrent programming.

%%% LAST %%%

declare
proc {Last Li ?X}
   choice H in
      Li = H | nil
      X = H
   [] T in
      Li = _ | T
      X = {Last T}
   []
      X = Li
   end
end
{Browse {SearchOne fun {$} {Last [1 2 3 4 5]} end} }

%%% REVERSE %%%

declare
proc {Append Xs Ys Zs}
   choice
      Xs = nil Ys = Zs
   [] X Xr in
      Xs = X | Xr
      Zs = X | {Append Xr Ys}
   end
end
proc {Reverse Li ?Lo}
   choice H T in
      Li = H | T
      Lo = {Append {Reverse T} [H]}
   []
      Li = nil
      Lo = nil
   end
end
{Browse {SearchAll fun {$} {Reverse [dog cat bowl food]} end} }

%%% MAP %%%

declare
proc {Map Li P ?Lo}
   choice H T in
      Li = H | T
      Lo = {P H} | {Map T P}
   []
      Lo = nil
   end
end
{Browse {SearchOne fun {$} {Map [1 2 3 4] IntToFloat} end} }

%%% ZIP %%%

declare
proc {Zip L1 L2 P ?Lo}
   choice H1 T1 H2 T2 in
      ({Length L1} == {Length L2}) = true
      L1#L2 = (H1|T1)#(H2|T2)
      Lo = {P H1 H2} | {Zip T1 T2 P}
   []
      Lo = nil
   end
end
{Browse {SearchOne fun {$} {Zip [1 6 3] [4 5 6] Max} end} }
{Browse {SearchOne fun {$} {Zip [b r] [o k e n] Max} end} }