Common Lisp 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/>

README:

FUNCTION

Public

ARRANGEMENT (K N)

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

COMBINATION (K N)

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

COMBINATIONS (LIST N)

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

Private

Undocumented

COPY-VECTOR (VECTOR &KEY (START 0) (END (LENGTH VECTOR)) (ELEMENT-TYPE NIL))

NEXT-STEP (CHOICE LIMIT I)

TEST

GENERIC-FUNCTION

Public

DONE-P (SELF)

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

GET-CURRENT-ELEMENT (SELF)

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)

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.

RESET (SELF)

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

Private

COMPUTE-CARDINAL (SELF)

NOTE: It must be overriden by subclasses to compute the _cardinal from the _baseCardinal and the _elementSize attributes.

INITIALIZE (SELF)

NOTE: It must be overriden by subclasses to initialize the enumeration. It must compute the _cardinal, and set the_index either to 0 or to _cardinal. If _index != _cardinal then the choice array must be set to the first enumerated element.

NEXT (SELF)

NOTE: It must be overriden by subclasses to step to the next element of the enumeration. If _index<_cardinal, then it must increment _index ; if _index┬╣_cardinal then the choice array must be set to the first enumerated element.

Undocumented

SET-BASE-CARDINAL (FUNCTOR CARDINAL)

SET-ELEMENT-SIZE (FUNCTOR SIZE)

STEP (FUNCTOR INDEX)

SLOT-ACCESSOR

Public

AT-BEGINNING-P (SELF)

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

BASE-CARDINAL (FUNCTOR)

The RETURN: The cardinal n of the base set.

CARDINAL (SELF)

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

ELEMENT-SIZE (SELF)

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

INDEX (SELF)

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

CLASS

Public

ARRANGEMENT-SANS-REPEAT

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

ARRANGEMENT-WITH-REPEAT

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

COMBINATION (K N)

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

Private

SET-FUNCTOR

Representation of an enumerable set.