Browse Prior Art Database

A METHOD FOR GENERATING COMBINATIONS IN A CHANGING ENVIRONMENT WITHOUT REPEATING ALREADY GENERATED COMBINATIONS

IP.com Disclosure Number: IPCOM000020390D
Original Publication Date: 2003-Nov-19
Included in the Prior Art Database: 2003-Nov-19
Document File: 7 page(s) / 80K

Publishing Venue

IBM

Abstract

There are applications that require to select k out of n elements such that the selected elements satisfy some function. For example consider the problem of selecting k out of n courses such that no two courses' schedule overlap. Assume there is no preference of any course above any other courses . This invention offers a method to find the first combination and then the next combination from the last combination that has been computed.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 17% of the total text.

Page 1 of 7

A METHOD FOR GENERATING COMBINATIONS IN A CHANGING ENVIRONMENT WITHOUT REPEATING ALREADY GENERATED COMBINATIONS

There are applications that require to select k out of n elements such that the selected elements satisfy some function. For example consider the problem of selecting k out of n courses such that no two courses' schedule overlap. Assume there is no preference of any course above any other courses . A simple solution would be to start enumerating all possible k selections and choose the first one with no overlaps. Assume now that a selected course was cancelled and two new courses were added so a new selection is required. A simple solution would be to start the selection process again from the new group of n+1 courses. But some of selections were already invalidated during the first pass so there is no need to check them again.

    This invention offers a method to find the first combination and then the next combination from the last combination that has been computed. Once the function is true for a particular combination we will not have to continue checking the remaining combinations. However we might have to find a new combination if an element in that particular combination is removed from the group.It might also be the case that the computation of all possible combinations did not satisfy the function and we will want to compute new combinations as new elements are added to the group.

    In both cases we want to avoid computing the function for any combination of elements already computed. Thus we want to find an order and an algorithm for one diemnsion and for higher dimensions such that:

One dimension

Given a group G of elements, a combination length m and a function F, find the first combination of m elements to evaluate the function F. Given a combination C, find the next combination C' such that C' was never computed before even if new elements were added or deleted from the group G since C was computed.

Two dimensions

Given a collection H of m groups G1,...,Gm , and a function F, find the first multicombination (C1,...,Cm) such that each Ci (1<= i <= m) is a selection of the first combination from group Gi to evaluate the function F. Given a multi combination MC=(C1,...,Cm), find the next multicombination MC'=(C1',...,Cm') such that MC' was never computed before even if new elements were added or deleted from any of the groups Gi since MC was computed.

Three dimensions

  Given n collections H1,...,Hn, Hi={Gi1,...,Gi,ni) and a function F, find the first multicombination (h1,...,hn) such that each hi is a multicombination (Ci1,...,Ci,ki) where Cij is the first combination of group Gij. Given a multicombination (h1,...,hn) find the next multicombination. Can be extended to any dimension

    The invention is useful in situations where a selection of k elements is required from a group of elements where the group of elements may change and an old computed combination may be no longer valid and another one is required. The


1.

...