Package COM.INFORMATIMAGO.COMMON-LISP.CESARUM.COMBINATION


This package exports three classes to generate lazily combinations,
and arrangements with and without repeatition (permutations).

See also: <http://fr.wikipedia.org/wiki/Combinatoire>

License:

    AGPL3

    Copyright Pascal J. Bourguignon 2003 - 2012

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU Affero General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Affero General Public License for more details.

    You should have received a copy of the GNU Affero General Public License
    along with this program.
    If not, see <http://www.gnu.org/licenses/>

(arrangement k n)

function

RETURN: The number of arrangement of k elements (without repeat) taken amongst n.

arrangement-sans-repeat

class

We choose k objects in order without repeating the same object, amongst n objects.

Class precedence list: ARRANGEMENT-SANS-REPEAT SET-FUNCTOR STANDARD-OBJECT T

arrangement-with-repeat

class

We choose k objects in order possibly repeating the same object, amongst n objects.

Class precedence list: ARRANGEMENT-WITH-REPEAT SET-FUNCTOR STANDARD-OBJECT T

(at-beginning-p self)

generic-function

RETURN:     whether the reset() method has been called and
            getNextElement() (or getCurrentElement()) has not
            already been called.

(base-cardinal functor)

generic-function

RETURN: The cardinal n of the base set.

(cardinal self)

generic-function

PRE:        !atBegining()..
RETURN:     the number of elements enumerated by this object.

combination

class

We choose k distinct objects,  without taking into account the order, amongst n objects.

Class precedence list: COMBINATION SET-FUNCTOR STANDARD-OBJECT T

(combination k n)

function

RETURN: The number of combinations of k elements taken amongst n.

(combinations list n)

function

RETURN: a list of all the combinations of N elements from the LIST.

(done-p self)

generic-function

RETURN:     !atBegining()
            && ((cardinal()=0) || (index()=cardinal())).

(element-size self)

generic-function

RETURN:     the size of each element returned by getCurrentElement
            and getNextElement in the choice arrays.

(get-current-element self)

generic-function

PRE:        cardinal()>0.
POST:       !atBegining(),
RETURN:     A vector of cardinal: choice.
DO:         Sets the choice array to the current enumerated
            element. (ie. the last element retrived with the
            getNextElement method). The choice array must contain
            at least elementSize() integers.

(get-next-element self)

generic-function

PRE:        cardinal()>0, !done-p(), atBegining()=b,
            (!b => index()=a).
POST:       !atBegining(), (!b => index()=a+1),
RETURN:     A vector of cardinal: choice; done-p.
DO:         Computes the next element to be enumerated and sets the
            choice array to it. It returns TRUE when the last
            element is retrived, ie. all elements have been
            enumerated. The choice array must contain at least
            elementSize() integers.

(index self)

generic-function

PRE:        !atBegining()..
RETURN:     the index of the current element enumerated by
            this object.

(reset self)

generic-function

POST:       atBegining().
DO:         resets the enumeration.