power set (Re: Modified keypad keys)

[Stephen Berman]

On Sat, 29 Sep 2012 22:19:35 +0300 Juri Linkov <address@hidden> wrote:

>>> +(defun powerset (list)
>>> +  (if (null list)
>>> +      '(nil)
>>> +    (let ((ps (powerset (cdr list))))
>>> +      (append ps (mapcar (lambda (e) (cons (car list) e)) ps)))))
>>
>> I'm not sure I want `powerset' without some "<prefix>-".
>
> Maybe `cl-powerset', to be added to cl-seq.el.

I would like to have a power set function in Emacs. But why do you use
'(nil) for the empty set instead of '() or nil?  I use nil in a variant
of the above in a program I'm working on.  As an alternative to the
recursive definition, I've also been using this iterative bitwise
version (which I translated into Elisp from the C program at
http://rosettacode.org/wiki/Power_set#C):

(defun powerset-bitwise (l)
  (let ((binnum (lsh 1 (length l)))
         pset elt)
    (dotimes (i binnum)
      (let ((bits i)
            (ll l))
        (while (not (zerop bits))
          (let ((arg (pop ll)))
            (unless (zerop (logand bits 1))
              (setq elt (append elt (list arg))))
            (setq bits (lsh bits -1))))
        (setq pset (append pset (list elt)))
        (setq elt nil)))
    pset))

In my use case the cardinality of the power set is small and there's no
noticeable difference in speed between the recursive and the iterative
versions, but maybe it makes a difference for large sets.

Steve Berman