Method for assigning random pairings to data entries

• US 8,051,184 B2
• Filed: 12/14/2004
• Issued: 11/01/2011
• Est. Priority Date: 03/27/2000
• Status: Active Grant

• Current Assignee: David R. Roberts
• Original Assignee: David R. Roberts
• Inventors: Roberts, David R.
• Primary Examiner(s): Coulter; Kenneth R
• Application Number:
  US11/011,551
• Publication Number:
  US 20050108182A1
• Time in Patent Office: 2,513 Days
• Field of Search: 709/223, 709/227, 709/228, 705/319, 705/7.11, 705/7.12, 705/7.13, 707/775, 707/769, 707/706, 434/322
• US Class Current: 709/228
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

A method for pairing elements of a first set of elements {x(i)} with elements from a second set of elements {y(j)} subject to a plurality of pairing restrictions. In accordance with one embodiment of the method, for each of a plurality of iterations of the method, or until a set of pairings is found that satisfies the plurality of pairing restrictions, a random set of pairings between elements of the second set of elements and elements of the second set of elements is selected. The set of mismatched pairings is identified and, if the number of pairings in the set of mismatched pairings is not greater than a maximum number, pairings in the set of mismatched pairings are interchanged. If the number of pairings in the set of mismatched pairings is greater than one, each mismatched pairing is swapped with another pairing if the resulting pairings satisfy the plurality of pairing restrictions.

Claims

1. A computer method performed by a programmed processor for pairing elements of a first set of elements {x(i)} with elements from a second set of elements {y(j)}, where i and j are indices and where the first set of elements and the second set of elements have the same number of elements, subject to a plurality of pairing restrictions, the method comprising:

a user defining the first set of elements and the second set of elements;

the user defining the plurality of pairing restrictions via a user interface of the programmed processor, wherein each pairing restriction of the plurality of pairing restrictions defines a specified pairing of an element of the first set of elements and an element of the second set of elements as prohibited;

for each of a plurality of iterations or until a set of pairings is found that satisfies the plurality of pairing restrictions;

selecting a random set of pairings between elements of the first set of elements and elements of the second set of elements, wherein each element of the first set of elements is paired with exactly one element of the second set of elements;

identifying a set of mismatched pairings, from the random set of pairings, that do not satisfy the plurality of pairing restrictions;

if the number of pairings in the set of mismatched pairings is greater than or equal to one and not greater than a defined maximum number of mismatched pairings;

interchanging pairings in the set of mismatched pairings;

if the number of pairings in the set of mismatched pairings is greater than or equal to one and greater than the defined maximum number of mismatched pairings;

swapping each mismatched pairing with another pairing if the resulting pairings satisfy the plurality of pairing restrictions, wherein the another pairing is selected from one or more of the set of mismatched pairings and the random set of pairings exclusive of the set of mismatched pairings and wherein selecting the another pairing from the random set of pairings exclusive of the set of mismatched pairings breaks the another pairing prior to being swapped with the mismatched pairing; and

if there are no mismatched pairings;

providing a list of randomly paired elements to the user via the user interface, wherein the list of randomly paired elements are randomly assigned pairings between the first set of elements and the second set of elements that solve an assignment problem.

2. A method in accordance with claim 1, wherein interchanging pairings in the set of mismatched pairings comprises:

interchanging pairings in the set of mismatched pairings if the resulting pairings satisfy the plurality of pairing restrictions.

3. A method in accordance with claim 1, wherein interchanging pairings in the set of mismatched pairings comprises:

interchanging pairings in the set of mismatched pairings if the resulting pairings reduce the number of pairings that do not satisfy the plurality of pairing restrictions.

4. A method in accordance with claim 1, wherein swapping each mismatched pairing with another pairing comprises:

selecting a mismatched pairing [x(i),y(j)];

selecting a second pairing [x(k),y(l)]; and

replacing the pairings [x(i),y(j)] and [x(k),y(l)] with the pairings [x(i),y(l)] and [x(k),y(j)] if the pairings [x(i),y(l)] and [x(k),y(j)] satisfy the plurality of restriction requirements.

5. A method in accordance with claim 1, wherein swapping each mismatched pairing with another pairing comprises:

selecting a mismatched pairing [x(i),y(j)];

selecting a second pairing [x(k),y(l)];

selecting a third pairing [x(m),y(n)]; and

if the pairings [x(i),y(l)], [x(k),y(n)] and [x(m),y(j)] satisfy the plurality of restriction requirements;

replacing the pairings [x(i),y(j)], [x(k),y(l)] and [x(m),y(n)] with the pairings [x(i),y(l)], [x(k),y(n)] and [x(m),y(j)];

else, if the pairings [x(i),y(n)], [x(k),y(j)] and [x(m),y(l)] satisfy the plurality of restriction requirements;

replacing the pairings [x(i),y(j)], [x(k),y(l)] and [x(m),y(n)] with the pairings [x(i),y(n)], [x(k),y(j)] and [x(m),y(l)].

6. A method in accordance with claim 1, wherein the first set of elements is the same as the second set of elements.

7. A method in accordance with claim 1, wherein the first set of elements comprises a list of names of gift givers, the second set of elements comprises a list of names of gift receivers and the plurality of pairings restrictions comprises a table indicating which giver/receiver pairings are prohibited.

8. A method in accordance with claim 1, wherein the first set of elements comprises a list of people, the second set of elements comprises a list of tasks and the plurality of pairings restrictions comprises a table indicating which tasks each person is prohibited from performing.

9. A method in accordance with claim 1, wherein swapping each mismatched pairing with another pairing is performed only after a specified minimum number iterations has failed to find set of pairings that satisfies the plurality of pairing restrictions.

10. A method in accordance with claim 1, further comprising:

presenting the user interface to a user of the programmed processor;

receiving data describing the first set of elements and the plurality of pairing restrictions from the user interface; and

if a set of pairings is found that satisfies the plurality of pairing restrictions;

presenting the set of pairings that satisfies the plurality of pairing restrictions to the user via the user interface.

11. A method in accordance with claim 10, further comprising:

defining the user interface by a web page stored on a network server;

presenting the user interface to the user via the Internet;

receiving data describing the first set of elements and the plurality of pairing restrictions from the user interface via the Internet; and

if a set of pairings is found that satisfies the plurality of pairing restrictions;

presenting the set of pairings that satisfies the plurality of pairing restrictions to the user via the Internet.

12. A non-transitory computer readable electronic storage medium storing a plurality of program instructions, which when executed on a computer, perform a method comprising:

a user defining the first set of elements and the second set of elements;

the user defining a plurality of pairing restrictions via a user interface of the computer, wherein each pairing restriction of the plurality of pairing restrictions defines a specified pairing of an element of a first set of elements and an element of a second set of elements as prohibited;

selecting a random set of pairings between elements of the first set of elements and elements of the second set of elements, wherein the first set of elements and the second set of elements have the same number of elements and wherein each element of the first set of elements is paired with exactly one element of the second set of elements;

identifying a set of mismatched pairings, from the random set of pairings, that do not satisfy a plurality of pairing restrictions;

if the number of pairings in the set of mismatched pairings is greater than or equal to one and not greater than a defined maximum number of mismatched pairings;

interchanging pairings in the set of mismatched pairings; and

if the number of pairings in the set of mismatched pairings is greater than or equal to one and greater than the defined maximum number of mismatched pairings;

swapping each mismatched pairing with another pairing if the resulting pairings satisfy the plurality of pairing restrictions, wherein the another pairing is selected from one or more of the set of mismatched pairings and the random set of pairings exclusive of the set of mismatched pairings and wherein selecting the another pairing from the random set of pairings exclusive of the set of mismatched pairings breaks the another pairing prior to being swapped with the mismatched pairing; and

if there are no mismatched pairings;

providing a list of randomly paired elements to the user via the user interface, wherein the list of randomly paired elements are randomly assigned pairings between the first set of elements and the second set of elements that solve an assignment problem.

13. A computer readable medium in accordance with claim 12, wherein the interchange of pairings in the set of mismatched pairings is performed if the resulting pairings satisfy the plurality of pairing restrictions.

14. A computer readable medium in accordance with claim 12, wherein the interchange of pairings in the set of mismatched pairings is performed if the resulting pairings reduce the number of pairings that do not satisfy the plurality of pairing restrictions.

15. A computer readable medium in accordance with claim 12, wherein the swapping of each mismatched pairing with another pairing if the resulting pairings satisfy the plurality of pairing restrictions comprises:

selecting a mismatched pairing [x(i),y(j)];

selecting a second pairing [x(k),y(l)]; and

replacing the pairings [x(i),y(j)] and [x(k),y(l)] with the pairings [x(i),y(l)] and [x(k),y(j)] if the pairings [x(i),y(l)] and [x(k),y(j)] satisfy the plurality of restriction requirements.

16. A computer readable medium in accordance with claim 12, wherein the swapping of each mismatched pairing with another pairing if the resulting pairings satisfy the plurality of pairing restrictions comprises:

selecting a mismatched pairing [x(i),y(j)];

selecting a second pairing [x(k),y(l)];

selecting a third pairing [x(m),y(n)]; and

if the pairings [x(i),y(l)], [x(k),y(n)] and [x(m),y(j)] satisfy the plurality of restriction requirements;

replacing the pairings [x(i),y(j)], [x(k),y(l)] and [x(m),y(n)] with the pairings [x(i),y(l)], [x(k),y(n)] and [x(m),y(j)];

else, if the pairings [x(i),y(n)], [x(k),y(j)] and [x(m),y(l)] satisfy the plurality of restriction requirements;

replacing the pairings [x(i),y(j)], [x(k),y(l)] and [x(m),y(n)] with the pairings [x(i),y(n)], [x(k),y(j)] and [x(m),y(l)].

17. A computer readable medium in accordance with claim 12, wherein the swapping of each mismatched pairing with another pairing if the resulting pairings satisfy the plurality of pairing restrictions comprises:

interchanging the mismatched pairing and another pairing if the resulting pairings satisfy the plurality of pairing restrictions; and

interchanging the mismatched pairing and two other pairings if the resulting pairings satisfy the plurality of pairing restrictions.

18. A computer readable medium in accordance with claim 12, wherein the first set of elements is the same as the second set of elements.

19. A computer readable medium in accordance with claim 12, wherein the plurality of program instructions are transmitted to a user via the Internet.

20. A computer readable medium in accordance with claim 12, wherein the plurality of program instructions are executed on a network server in response to user instructions transmitted to the server via the Internet.