[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

power set (Re: Modified keypad keys)

From: Stephen Berman
Subject: power set (Re: Modified keypad keys)
Date: Mon, 01 Oct 2012 10:02:31 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2.50 (gnu/linux)

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

(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)))

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]