William James
11/17/2015 7:41:00 AM
WJ wrote:
> Geoffrey Summerhayes wrote:
>
> > > There was an interesting discussion in de.comp.lang.java how to implement a
> > > powerset. In Haskell it is a 2 liner:
> > >
> > > powerset [] = [[]]
> > > powerset (x:xs) = let p = powerset xs in p ++ map (x:) p
> > >
> > > Usage:
> > >
> > > powerset [1,2,3]
> > > [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
> > >
> > > Another version in Prolog:
> > >
> > > combination([], []).
> > > combination([H|T], P) :- combination(T,P).
> > > combination([H|T], [H|P]) :- combination(T,P).
> > >
> > > Usage:
> > >
> > > ?- combination([1,2,3], R).
> > >
> > > R=[]
> > > R=[3]
> > > R=[2]
> > > R=[2,3]
> > > ...
> > >
> > > I don't post the more than 30 lines Java solutions now. How would it look
> > > like in Common Lisp? One intersting fact: for my Java translation of the
> > > Haskell solution I needed half an hour, for the Lisp solution I needed only
> > > some minutes:
> > >
> > > (defun powerset (list)
> > > (let ((x (car list)))
> > > (if x
> > > (let ((p (powerset (cdr list))))
> > > (append p (mapcar (lambda (list) (cons x list)) p)))
> > > '(()))))
> > >
> > > How would a more Lisp-like solution look like? And I'm sure an OCaml
> > > solution would be better than every any solution in any other language :-)
> >
> > Don't know about more 'Lisp-like' but here's two alternates:
> >
> > Tail-recursive:
> >
> > (defun powerset(list &optional (partial '(())))
> > (if (null list)
> > partial
> > (powerset (cdr list)
> > (append partial
> > (loop :for set
> > :in partial
> > :collect (cons (car list) set))))))
> >
> > Collection loop:
> >
> > (defun powerset(list)
> > (let ((result '(())))
> > (loop :for x :in list
> > :do (setf result
> > (loop :for set :in result
> > :appending (list set (cons x set)))))
> > result))
>
>
> MatzLisp (Ruby):
>
> def powerset((x,*xs))
> x ? (p = powerset xs; p + p.map{|y| [x] + y}) : [[]]
> end
>
> powerset [2,3,4]
> ==>[[], [4], [3], [3, 4], [2], [2, 4], [2, 3], [2, 3, 4]]
Another way:
def powerset xs
(0..xs.size).flat_map{|i| xs.combination(i).to_a}
end
powerset [2,3,4]
==>[[], [2], [3], [4], [2, 3], [2, 4], [3, 4], [2, 3, 4]]
--
Africans gang-rape and clitorectomize Finnish girl; government arrests Finn
whom they accuse of complaining:
conservative-headlines.com/2009/03/another-european-awaits-extradition-for-hate-speech