Dear all,
I realise that this is a rather strange thing to ask for, but anyway...
I'm working on an algorithm to enumerate some strange objects, and I'm pretty
sure that my idea is good. What I'd love to have is a footnote in the paper I'm
about to write saying
"a CL implementation of the algorithm can be downloaded at
http://www.mat.univie.ac.at/~rubey/cantor.lisp "
maybe you, Erann :-)
I have a running version, but there are some parts I need which should be
implemented in a better way.
I hacked along for a week (I'm a mathematician, not a programmer), day and
night (fortunately my wife and my kid are on holidays) and I'm *really* tired
now... I can't continue like this.
So, here we go (this is one ingredient of my algorithm which should be fast):
First challenge:
; Call fun for each subsets of 0, 2, ..., n-1 of length k with the following
; constraint: let p be an "ordered" partition of n, eg. (3,2,4,1) |- 10. If x
; is a chosen number, then it is required that all numbers in the same part of
; the partition smaller than x are chosen, too.
; it may be easier to think of p as a vector where all elements within one
; "part" given by the partition are the same.
; eg: for n=10, k=4, p=(3,2,4,1)==(0,0,0,1,1,2,2,2,2,3)
; (0,1,2,3), (0,1,3,5), (3,5,6,7) are all allowed (there are a lot more...)
; (1,2,3,4), (0,1,4,5) are forbidden
(defun strange-combinations (n k p fun)
I think that it would be best to adapt one of the algorithms from Knuth's
pre-fascicle 2c: Generating all combinations
http://www-cs-faculty.stanford.edu/~knuth/fasc2c.ps.gz
Note that the order of generation is not important for my application. It needs
to be fast, that's all.
Here is my code (and alas, it's no good: I thought that I'd needed vectors of
ones and zeros, not subsets of 1, 2, ...,n, and found out better when it was
too late... well, it's not so bad either. Maybe I'd need to redo only my swap
routine? I'm too tired to see clearly...)
; erzeuge Vektoren der L�nge n mit k Einsern und n-k Nullern. l ist eine
; Partition von l die "gleiche" Kasterl bestimmt. vec ist der Vector, fun eine
; Funktion die f�r jede M�glichkeit aufgerufen wird.
(defun strange-combinations (n k l fun vec &optional debug)
(and debug (print (list 'strange-combinations n k l vec)))
(let ((level -1))
(labels ((swap (i j)
(and debug (format T "~%swapping ~A and ~A: " i j))
(rotatef (aref vec (1- i)) (aref vec (1- j)))
(funcall fun))
(init (n k)
(and debug (format T "~%initialise ~A, ~A: " n k))
(fill vec 1 :start 0 :end k)
(fill vec 0 :start k :end n))
(gen (n k l)
; (1 . . . . 1 0 . . 0 | 0 . . . . . . 0)
; bzw. (1 . . . . . . . . 1 | 1 . . 1 0 . . 0)
;
; -> (1 . . 1 0 . . . . 0 | 1 . . . . . . 1)
; bzw. (0 . . . . . . . . 0 | 1 . . 1 0 . . 0)
(incf level)
(and debug (print (list (make-string level) 'gen n k l)))
(when (and (< 0 k n) (< (car l) n))
(let* ((n-rec (- n (car l)))
(0-aft (if (< k n-rec) (car l) (- n k)))
(1-bef (min k n-rec))
(first-0-aft (1+ (max k n-rec))))
(dotimes (i (min 0-aft 1-bef))
(cond ((evenp i)
(gen n-rec (- 1-bef i) (cdr l))
(swap (+ first-0-aft i)
(if (plusp (- 1-bef (cadr l) i))
; (1 . . 1 0 . . 0 | 1 . . . . . . 1 | ...)
(- 1-bef (cadr l) i)
; (0 . . . . . . 0 | 1 . . 1 0 . . 0 | ...)
(+ (- n-rec (cadr l) i) 1-bef))))
(T
(neg n-rec (- 1-bef i) (cdr l))
(swap (+ first-0-aft i)
; (1 . . 1 0 . . . . . . . . . . . 0 | ...)
(- 1-bef i)))))
(if (evenp (min 0-aft 1-bef))
(progn (gen n-rec (max 0 (- k (car l))) (cdr l))
(init n-rec (max 0 (- k (car l)))))
(neg n-rec (max 0 (- k (car l))) (cdr l)))))
(decf level))
(neg (n k l)
; (1 . . 1 0 . . . . 0 | 1 . . . . . . 1)
; bzw. (0 . . . . . . . . 0 | 1 . . 1 0 . . 0)
; -> (1 . . . . 1 0 . . 0 | 0 . . . . . . 0)
; bzw. (1 . . . . . . . . 1 | 1 . . 1 0 . . 0)
(incf level)
(and debug (print (list (make-string level) 'neg n k l)))
(when (and (< 0 k n) (< (car l) n))
(let* ((n-rec (- n (car l)))
(1-aft (min k (car l)))
(0-bef (if (< k (car l)) n-rec (- n k)))
; = n-rec - 1-bef
(1-bef (if (< k (car l)) 0 (- k (car l))))
; = n-rec - 0-bef
(last-1-aft (if (< k (car l)) (+ n-rec k) n)))
(dotimes (i (min 1-aft 0-bef))
(cond ((evenp i)
(gen n-rec (+ 1-bef i) (cdr l))
(swap (- last-1-aft i)
(if (plusp (- (cadr l) 1-bef i))
; 0 . . . . . . 0 | 1 . . 1 0 . . 0 | 1
(- (+ n-rec 1-bef i 1) (cadr l))
; 1 . . 1 0 . . 0 | 1 . . . . . . 1 | 1
(+ (- 1-bef (cadr l)) i 1))))
(T
(neg n-rec (+ 1-bef i) (cdr l))
(swap (- last-1-aft i)
; (1 . . 1 0 . . . . . . . . . . . 0 | 1
(+ 1-bef i 1)))))
(if (evenp (min 1-aft 0-bef))
(progn (gen n-rec (min k n-rec) (cdr l))
(init n-rec (min k n-rec)))
(neg n-rec (min k n-rec) (cdr l)))))
(decf level)))
(init n k)
(funcall fun)
(gen n k l))))
; rufe fun f�r alle erlaubten Combinationen auf
(defun strange-comb-list (n k l fun &optional debug)
(let ((vec (make-array n)))
(strange-combinations n k l
#'(lambda ()
(and debug (print vec))
(let (pos)
(dotimes (i n)
(or (zerop (aref vec i))
(push i pos)))
(funcall fun pos)))
vec debug)))
In article <···············@invite02.labri.fr>, Martin Rubey
<········@yahoo.de> wrote:
> Dear all,
>
> I realise that this is a rather strange thing to ask for, but anyway...
>
> I'm working on an algorithm to enumerate some strange objects, and I'm pretty
> sure that my idea is good. What I'd love to have is a footnote in the
paper I'm
> about to write saying
>
> "a CL implementation of the algorithm can be downloaded at
> http://www.mat.univie.ac.at/~rubey/cantor.lisp "
>
> maybe you, Erann :-)
Huh?
E.
From: Joe Marshall
Subject: Re: please implement this in a better way...
Date:
Message-ID: <k7bspt7k.fsf@ccs.neu.edu>
Martin Rubey <········@yahoo.de> writes:
> First challenge:
> ; Call fun for each subsets of 0, 2, ..., n-1 of length k with the following
> ; constraint: let p be an "ordered" partition of n, eg. (3,2,4,1) |- 10. If x
> ; is a chosen number, then it is required that all numbers in the same part of
> ; the partition smaller than x are chosen, too.
>
> ; it may be easier to think of p as a vector where all elements within one
> ; "part" given by the partition are the same.
>
> ; eg: for n=10, k=4, p=(3,2,4,1)==(0,0,0,1,1,2,2,2,2,3)
> ; (0,1,2,3), (0,1,3,5), (3,5,6,7) are all allowed (there are a lot more...)
> ; (1,2,3,4), (0,1,4,5) are forbidden
Let me see if I understand this. We have some sequence that contains
runs of elements like (m m m m n n n n n n o p p p p p q q). You want
to find sets of indexes where an index is permitted only if
a) it is the index of the first element in a run,
or
b) the element to the left is indexed as well.
So in the sequence (m m m m n n n n n n o p p p p p q q), indexes
0, 4, 10, 11, 16 are at the beginning of each run, so we can choose to
include them or not in the answer. But index 6, for example, could
only be included if we include 5 and 4 as well.
From: Joe Marshall
Subject: Re: please implement this in a better way...
Date:
Message-ID: <3cigpri4.fsf@ccs.neu.edu>
Joe Marshall <···@ccs.neu.edu> writes:
> Martin Rubey <········@yahoo.de> writes:
>
> > First challenge:
> > ; Call fun for each subsets of 0, 2, ..., n-1 of length k with the following
> > ; constraint: let p be an "ordered" partition of n, eg. (3,2,4,1) |- 10. If x
> > ; is a chosen number, then it is required that all numbers in the same part of
> > ; the partition smaller than x are chosen, too.
> >
> > ; it may be easier to think of p as a vector where all elements within one
> > ; "part" given by the partition are the same.
> >
> > ; eg: for n=10, k=4, p=(3,2,4,1)==(0,0,0,1,1,2,2,2,2,3)
> > ; (0,1,2,3), (0,1,3,5), (3,5,6,7) are all allowed (there are a lot more...)
> > ; (1,2,3,4), (0,1,4,5) are forbidden
>
> Let me see if I understand this. We have some sequence that contains
> runs of elements like (m m m m n n n n n n o p p p p p q q). You want
> to find sets of indexes where an index is permitted only if
>
> a) it is the index of the first element in a run,
> or
> b) the element to the left is indexed as well.
>
>
> So in the sequence (m m m m n n n n n n o p p p p p q q), indexes
> 0, 4, 10, 11, 16 are at the beginning of each run, so we can choose to
> include them or not in the answer. But index 6, for example, could
> only be included if we include 5 and 4 as well.
(defun perms (list)
(perms1 nil nil 0 list))
(defun perms1 (previous-element previous-tagged index remaining-elements)
(if (null remaining-elements)
(list '())
(let ((this-element (car remaining-elements)))
(nconc (perms1 this-element nil (1+ index) (cdr remaining-elements))
(and (or previous-tagged
(not (eq this-element previous-element)))
(map 'list (lambda (perm)
(cons index perm))
(perms1 this-element t (1+ index) (cdr remaining-elements))))))))
Joe Marshall <···@ccs.neu.edu> writes:
> Joe Marshall <···@ccs.neu.edu> writes:
> >
> > Let me see if I understand this. We have some sequence that contains
> > runs of elements like (m m m m n n n n n n o p p p p p q q). You want
> > to find sets of indexes where an index is permitted only if
> >
> > a) it is the index of the first element in a run,
> > or
> > b) the element to the left is indexed as well.
> >
> >
> > So in the sequence (m m m m n n n n n n o p p p p p q q), indexes
> > 0, 4, 10, 11, 16 are at the beginning of each run, so we can choose to
> > include them or not in the answer. But index 6, for example, could
> > only be included if we include 5 and 4 as well.
Well, nearly: I only want to generate sequences of a given length k, otherwise
its correct. However, I don't see how I would achieve this with your
algorithm, I really need to have the next element generated in O(1) time! (My
algorithm does this nearly, I think. But I'm not sure...)
Thanks a lot anyway,
Martin
> (defun perms (list)
> (perms1 nil nil 0 list))
>
> (defun perms1 (previous-element previous-tagged index remaining-elements)
> (if (null remaining-elements)
> (list '())
> (let ((this-element (car remaining-elements)))
> (nconc (perms1 this-element nil (1+ index) (cdr remaining-elements))
> (and (or previous-tagged
> (not (eq this-element previous-element)))
> (map 'list (lambda (perm)
> (cons index perm))
> (perms1 this-element t (1+ index)
> (cdr remaining-elements))))))))
From: Joe Marshall
Subject: Re: please implement this in a better way...
Date:
Message-ID: <r860o7hy.fsf@ccs.neu.edu>
Martin Rubey <········@unet.univie.ac.at> writes:
> Joe Marshall <···@ccs.neu.edu> writes:
>
> > Joe Marshall <···@ccs.neu.edu> writes:
> > >
> > > Let me see if I understand this. We have some sequence that contains
> > > runs of elements like (m m m m n n n n n n o p p p p p q q). You want
> > > to find sets of indexes where an index is permitted only if
> > >
> > > a) it is the index of the first element in a run,
> > > or
> > > b) the element to the left is indexed as well.
> > >
> > >
> > > So in the sequence (m m m m n n n n n n o p p p p p q q), indexes
> > > 0, 4, 10, 11, 16 are at the beginning of each run, so we can choose to
> > > include them or not in the answer. But index 6, for example, could
> > > only be included if we include 5 and 4 as well.
>
> Well, nearly: I only want to generate sequences of a given length k, otherwise
> its correct. However, I don't see how I would achieve this with your
> algorithm, I really need to have the next element generated in O(1) time! (My
> algorithm does this nearly, I think. But I'm not sure...)
Ah, I missed the part of a given length. (Shouldn't be too hard...)
When you say O(1), what is that in reference to? The length of the
original sequence? I don't think that's possible because the number
of subsequences is 2^n.
Joe Marshall <···@ccs.neu.edu> writes:
> Ah, I missed the part of a given length. (Shouldn't be too hard...)
>
> When you say O(1), what is that in reference to? The length of the
> original sequence? I don't think that's possible because the number
> of subsequences is 2^n.
no, its the time to generate the next subsequence. What I want, at least sort
of, is a Gray code, if this is clearer. Otherwise said: If I need 5 instants to
generate the 5 allowed combinations for given n, p and k, I hope that I will
need 500 instants to generate the 500 allowed combinations for given n2, p2 and
k. (I think it will depend on k, but I'm nut sure about this) Hope I got this
right...
More clarification in Knuths fascicle...
(BTW, I'm considering "only" binomial(n,k) subsequences - in fact less than
that, due the the special constraints)
Thanks for your help,
Martin
From: Joe Marshall
Subject: Re: please implement this in a better way...
Date:
Message-ID: <4r2wo5hw.fsf@ccs.neu.edu>
Martin Rubey <········@unet.univie.ac.at> writes:
> Joe Marshall <···@ccs.neu.edu> writes:
>
> > Ah, I missed the part of a given length. (Shouldn't be too hard...)
> >
> > When you say O(1), what is that in reference to? The length of the
> > original sequence? I don't think that's possible because the number
> > of subsequences is 2^n.
>
> no, its the time to generate the next subsequence. What I want, at least sort
> of, is a Gray code, if this is clearer. Otherwise said: If I need 5 instants to
> generate the 5 allowed combinations for given n, p and k, I hope that I will
> need 500 instants to generate the 500 allowed combinations for given n2, p2 and
> k. (I think it will depend on k, but I'm nut sure about this) Hope I got this
> right...
Well, this does it incrementally (i.e., you pass it a function and it
is called on the subsequences as they are found.) The call to REVERSE
is used to pass the arguments in order to F, but you could reverse the
original sequence and play with the indexes if you'd rather.
I'll have to think a bit to determine the time complexity, though.
(defun perms1 (previous-element previous-tagged index remaining-elements k f result)
(if (zerop k)
(funcall f (reverse result))
(and remaining-elements
(let ((this-element (car remaining-elements)))
(perms1 this-element nil (1+ index) (cdr remaining-elements) k f result)
(and (or previous-tagged
(not (eq this-element previous-element)))
(perms1 this-element t (1+ index) (cdr remaining-elements)
(1- k) f (cons index result)))))))
(defun perms (list k f)
(perms1 nil nil 0 list k f '()))
"Joe Marshall" <···@ccs.neu.edu> wrote in message ·················@ccs.neu.edu...
>
> I'll have to think a bit to determine the time complexity, though.
>
If we dispense with the list of elements, we can generate
the indexes directly given the run-lengths.
(defun strange1 (prefix k p0 pn i f)
(declare (type fixnum p0 k i))
(if (zerop k)
(funcall f prefix)
(unless (minusp p0)
(strange1 prefix k (or (car pn) -1) (cdr pn) (+ i p0) f)
(when (> p0 0)
(strange1 (cons i prefix) (1- k) (1- p0) pn (1+ i) f)))))
(defun strange (k p f)
(strange1 '() k (car p) (cdr p) 0 f))
This generates the same sequence as your original `strange combinations',
but the P argument (which you called L), is in forward order rather than
in reverse. It doesn't need the N argument (which is implied by the
sum of P).
It seems to run faster than what you originally posted.
"Joe Marshall" <·············@attbi.com> writes:
> "Joe Marshall" <···@ccs.neu.edu> wrote in message ·················@ccs.neu.edu...
> >
> > I'll have to think a bit to determine the time complexity, though.
> >
>
> If we dispense with the list of elements, we can generate
> the indexes directly given the run-lengths.
>
> (defun strange1 (prefix k p0 pn i f)
> (declare (type fixnum p0 k i))
> (if (zerop k)
> (funcall f prefix)
> (unless (minusp p0)
> (strange1 prefix k (or (car pn) -1) (cdr pn) (+ i p0) f)
> (when (> p0 0)
> (strange1 (cons i prefix) (1- k) (1- p0) pn (1+ i) f)))))
>
> (defun strange (k p f)
> (strange1 '() k (car p) (cdr p) 0 f))
>
> This generates the same sequence as your original `strange combinations',
> but the P argument (which you called L), is in forward order rather than
> in reverse. It doesn't need the N argument (which is implied by the
> sum of P).
>
> It seems to run faster than what you originally posted.
Well, I couldn't test speed yet, because your version revealed a bug in my
program... Thanks a lot :-)
(BTW, it seems that your version needs a leeding 0 for p)
Martin
From: Joe Marshall
Subject: Re: please implement this in a better way...
Date:
Message-ID: <he6vm81i.fsf@ccs.neu.edu>
Martin Rubey <········@yahoo.de> writes:
> "Joe Marshall" <·············@attbi.com> writes:
>
> > "Joe Marshall" <···@ccs.neu.edu> wrote in message ·················@ccs.neu.edu...
> > >
> > > I'll have to think a bit to determine the time complexity, though.
> > >
> >
> > If we dispense with the list of elements, we can generate
> > the indexes directly given the run-lengths.
> >
> > (defun strange1 (prefix k p0 pn i f)
> > (declare (type fixnum p0 k i))
> > (if (zerop k)
> > (funcall f prefix)
> > (unless (minusp p0)
> > (strange1 prefix k (or (car pn) -1) (cdr pn) (+ i p0) f)
> > (when (> p0 0)
> > (strange1 (cons i prefix) (1- k) (1- p0) pn (1+ i) f)))))
> >
> > (defun strange (k p f)
> > (strange1 '() k (car p) (cdr p) 0 f))
> >
> > This generates the same sequence as your original `strange combinations',
> > but the P argument (which you called L), is in forward order rather than
> > in reverse. It doesn't need the N argument (which is implied by the
> > sum of P).
> >
> > It seems to run faster than what you originally posted.
>
> Well, I couldn't test speed yet, because your version revealed a bug in my
> program... Thanks a lot :-)
>
> (BTW, it seems that your version needs a leeding 0 for p)
It shouldn't.
If p starts with a zero, then p0 is zero on the first call.
Since p0 is not negative, the first recursive call is taken
where the prefix is not modified, p0 is discarded and the next
element of P is used, and i is added to p0 (which leaves i
unmodified). So if p starts with a zero, the first recursive call
discards it immediately. Since P is not greater than zero, the
second recursive call is not taken.
So having a leading zero should have no effect on the result, and
in testing it, I can't find any difference.
Do you have a test case that shows otherwise?
Joe Marshall <···@ccs.neu.edu> writes:
> It shouldn't.
Sorry, it was my fault:
* (strange 3 '(3 3) #'(lambda (x) (print x)))
(5 4 3)
(4 3 0)
(3 1 0)
(2 1 0)
(2 1 0)
*
I confused the last line for output, but it's the return value of course. Silly
me. When you prepend 0, you get nil as return value, so I thought it was a
bug... Sorry again, and thank you *very* much for your help. I'll be back when
I repaired the implementation of my algorithm :-)
Martin
From: Joe Marshall
Subject: Re: please implement this in a better way...
Date:
Message-ID: <adcoo6dr.fsf@ccs.neu.edu>
Martin Rubey <········@unet.univie.ac.at> writes:
> Joe Marshall <···@ccs.neu.edu> writes:
>
> > Joe Marshall <···@ccs.neu.edu> writes:
> > >
> > > Let me see if I understand this. We have some sequence that contains
> > > runs of elements like (m m m m n n n n n n o p p p p p q q). You want
> > > to find sets of indexes where an index is permitted only if
> > >
> > > a) it is the index of the first element in a run,
> > > or
> > > b) the element to the left is indexed as well.
> > >
> > >
> > > So in the sequence (m m m m n n n n n n o p p p p p q q), indexes
> > > 0, 4, 10, 11, 16 are at the beginning of each run, so we can choose to
> > > include them or not in the answer. But index 6, for example, could
> > > only be included if we include 5 and 4 as well.
>
> Well, nearly: I only want to generate sequences of a given length k, otherwise
> its correct. However, I don't see how I would achieve this with your
> algorithm, I really need to have the next element generated in O(1) time! (My
> algorithm does this nearly, I think. But I'm not sure...)
This does lists of a given length.
I should be able to make it incremental.
(defun perms1 (previous-element previous-tagged index remaining-elements k)
(if (null remaining-elements)
(when (zerop k)
(list '()))
(let ((this-element (car remaining-elements)))
(nconc (perms1 this-element nil (1+ index) (cdr remaining-elements) k)
(and (or previous-tagged
(not (eq this-element previous-element)))
(map 'list (lambda (perm)
(cons index perm))
(perms1 this-element t (1+ index) (cdr remaining-elements) (1- k))))))))
(defun perms (list k)
(perms1 nil nil 0 list k))