Diese Herausforderung ist ein Szenario Social Golfer Problem . Ich habe eine Firma mit 320 Personen. Vor kurzem habe ich ein MBO-Programm (Management By Objectives) eingeführt, bei dem jedem Mitarbeiter Ziele zugewiesen werden, die monatlich zu erfüllen sind. Eines der wiederkehrenden Ziele ist es, pünktlich bei der Arbeit zu erscheinen, um an einem 30-minütigen Kaffee-und-Dounut-Treffen teilzunehmen. Das Treffen findet in unserer Speisesaal mit 50 Tischen statt. Jeder Tisch bietet Platz für maximal 8 Personen. Plus oder minus 80 Plätze sind an jedem Arbeitstag leer, da derzeit maximal 400 Plätze zur Verfügung stehen. Ich möchte eine Round-Robin-Sitzordnung schaffen, so dass jede Person rotierend mit jeder anderen Person zusammentreffen und zusammenarbeiten kann.
(EDIT) REGEL: Für jeden Arbeitstag werden einmalige Mengen von 8 Personen benötigt. Eine Person kann nicht wieder mit anderen Personen zusammensitzen, mit denen sie in der Vergangenheit gesessen haben, bis alle möglichen Permutationen ausgeschöpft sind.
BEARBEITEN: Ein Beispiel für das gewünschte Ergebnis ist:
%Vor%Keine der Arbeiterzahlen (Elemente) kann in jedem Satz (Array) von 8 Arbeitern wiederholt werden, bis alle möglichen einzigartigen Mengen (Permutationen) erschöpft sind. Dann beginnt der Zyklus wieder von vorne und verschiebt vielleicht die Elemente, nur dann würde ein Arbeiter mit einem anderen Arbeiter zusammen sitzen, den sie vorher getroffen haben. Ich möchte dann jedem Arbeiter per E-Mail mitteilen, an welcher Tabelle er am nächsten Arbeitstag sitzen soll. Jeder Arbeiter weiß nicht, wer sonst an seinem zugewiesenen Tisch sitzt, bis er am Tisch ankommt. Nur ich werde die komplette Liste für die Sitzordnung haben. (Es ist eine Art von "Musical Chairs" Spiel)
Dies ist keine Übung oder Schulaufgabe. Ein Freund, der die APL-Programmiersprache verwendet, sagte mir, dass sie mit einer Codezeile die gewünschten Ergebnisse erzeugen könne, aber wir verwenden nur SQL-basierte DBMS (IBM Informix 11.70 und Oracle 11).
Ich habe also eine SQL-Tabelle mit den folgenden Spalten:
%Vor%Die folgende Zeile des APL-Programmiercodes erzeugt Matrixpermutationen:
%Vor%Kann ich in SQL die gewünschten Ergebnisse mit einer SELECT-Anweisung generieren, brauche ich mehrere SELECT INTO TEMP-Anweisungen oder ist eine gespeicherte Prozedur erforderlich, um die gewünschten Ergebnisse zu erhalten?
Wie sollen meine SELECT-Anweisungen / s oder SP aussehen?
BEARBEITEN : Wenn das gewünschte Ergebnis mit SQL nicht möglich ist, könnte es mit einer 3GL wie c # erreicht werden?
Das nennt man das Problem des sozialen Golfspiels , und obwohl es so war erreichen Sie mit APL , nicht mit einer einzigen Zeile. Es ist ein sehr schwieriges Problem, so dass ich mir schwer vorstellen kann, dass dies mit einer Datenbankabfrage möglich ist. Es gibt viel Literatur online über das Thema und einige Online-Rechner.
BEARBEITEN:
Ihr APL-Code erstellt einfach eine Matrix von Permutationen. Wenn Sie beispielsweise Folgendes eingeben:
%Vor%Sie erhalten die folgende Matrix:
%Vor%Laut Wikipedia:
Ein Round-Robin-Turnier (oder All-Play-All-Turnier) ist ein Wettbewerb, bei dem jeder Teilnehmer nacheinander alle anderen Teilnehmer trifft.
Nach Markus Triska in seiner Masterarbeit zum Thema:
Das Social Golfer Problem (SGP) ist ein kombinatorisches Optimierungsproblem. Die Aufgabe ist es, g × p Golfer in g Gruppen von p Spielern für w Wochen so zu planen, dass keine zwei Golfer mehr als einmal in derselben Gruppe spielen.
Mathematisch gibt es einen großen Unterschied. Ein Round-Robin-Turnier besteht aus Zweiergruppen. Wenn Sie 9 Teilnehmer haben, benötigen Sie 36 Matches in 8 Runden. Mit dem sozialen Golfer können Sie sie zu dreien gruppieren, und es würde 12 Spiele in 4 Runden erfordern:
%Vor% Das Problem
Wenn das Problem eine echte Aufgabe ist, Meetings zu planen, dann gibt es einige Fehler beim Stellen einer Frage.
Es ist, weil die Anzahl der Arbeiter und sogar eine Anzahl verfügbarer Tische und Plätze keine grundlegende physikalische Konstante ist:
Das Problem klingt also so: "Wir müssen die nächsten 5-10 Arbeitstage so planen, dass möglichst viele Personen mit Personen zusammentreffen, mit denen sie vorher nicht gesprochen haben und möglichst wenige Menschen sprechen mit anderen Personen zweimal und mehr ".
Daher besteht das Problem nicht darin, einen vollständigen Satz von Permutationen zu erzeugen. Das Problem ist die optimale Planung für die nächsten N Treffen.
Theorie
Das Problem kann als generisches mathematisches Optimierungsproblem klassifiziert werden. Für diese Klasse von Problemen haben wir ein Ziel, eine optimale Lösung zu finden, die als Menge von Argumentwerten für Funktionen dargestellt wird, die einen maximalen oder minimalen Wert für die Zielfunktion (en) liefern.
Um ein Problem zu formulieren, müssen wir die Wurzel der Frage finden:
Jedes dieser Ziele spricht von Gesprächen zwischen einem Paar von Personen, also müssen wir ein Problem in Bezug auf "Treffen" formulieren.
Bezeichnen Sie P als Anzahl der Personen und i in [1..P] und j in [1..P] als Personenindizes.
Bezeichnen Sie M als Anzahl der Besprechungen und m in [1 .. M] als Besprechungsnummer.
Dann stellen wir a(i,j,m) | i < j, i in [1..P], j in [1..P], m in [1..M] als eine Tatsache des Treffens zwischen zwei Personen auf dem konkreten Treffen vor.
Danach ist es möglich, eine objektive Funktion und Randbedingungen für das Problem zu formulieren.
Mathematischer Ansatz
Bitte beachten Sie, dass die genaue Lösung (jemand trifft nur eine Person bis zum Ende des Zyklus) nur in sehr seltenen Fällen möglich ist.
Dies ist ein NP-vollständiges Klassenproblem, und die am besten übereinstimmende Formulierung ist das "Optimierungsproblem der perfekten Übereinstimmung in k-einheitlichen Hypergraphen, die eine 1-Grad-Kograd-Bedingung erfüllen"
Für weitere theoretische Untersuchungen können Sie eine Frage an Mathematik stellen oder neuesten Arbeiten verfügbar für K-Uniform Hypergraph Partitionierung, z "Polynomialzeit-perfekte Anpassung in dichten Hypergraphen"
Lösung muss genau (P-1)/(T-1)=(320-1)/(8-1)=45.5714285714 Treffen haben, weil jedes Mal, wenn die Person 7 andere trifft und die "andere" Zahl 319 ist. Es können also 45 Treffen nach den Bedingungen der Frage sein, bevor sich ein Paar Personen zweimal trifft.
Es gibt eine ähnliche Frage mit guter Antwort bereits auf StackOverflow ( Link ). Beachten Sie, dass dieser Algorithmus leere Plätze frei lässt, da für die vollständige Platzierung aller Personen seats * prime = person_count und 41 als Primzahl gewählt werden müssen.
Unten ist eine Abfrage mit dieser Lösung ( SQLFiddle ).
Praktischer Ansatz
Aus praktischer Sicht brauchen wir keine optimale Lösung mit theoretischem Nachweis. Wenn sich eine Person mehr als einmal trifft, ist das keine große Sache, also ist es möglich, bei einer fast optimalen Lösung zu bleiben.
Solch eine Lösung kann auf der Grundlage empirischer Regeln erzeugt werden, wenn wir beginnen, Personen nacheinander zu Versammlungen und Tabellen zu platzieren, die versuchen, die Anzahl der Überschneidungen für jedes Paar von Personen so niedrig wie möglich zu halten
Es gibt viele mögliche Strategien, und eine davon ist unten abgebildet.
Zu Demonstrationszwecken verwende ich Oracle, da diese Datenbank in Frage-Tags vorhanden ist und auf der SQLFiddle -Stelle verfügbar ist.
Beispiel für die Einrichtung eines Datenbankschemas umfasst drei Tabellen:
person - Tabelle mit der Liste der Arbeiter;
person_pair - Tabelle mit Liste aller eindeutigen Arbeiterpaare und Anzahl der Schnittpunkte für jedes Paar, total floor((P*P)/2) - floor(P/2) rows. Im Fall von P = 320 enthält es 51040 Zeilen.
meeting - Tabelle mit Placement-Informationen für jede Person in jeder Besprechung.
In der Beispielcodenummer von Arbeitern, die auf 20 und die Anzahl von Arbeitsplätzen auf 4 beschränkt sind, weil Ressourcenverbrauchsgrenzen auf der SQLFiddle-Site gelten und Ergebnisdatensätze beobachtbar bleiben.
Nachfolgend finden Sie den Code für die Einrichtung und Füllung des Schemas. Bitte lesen Sie die Kommentare durch, um mehr über Tabellenfelder zu erfahren.
%Vor%Füllen Sie die Anfangsdaten aus ( SQLFiddle ):
%Vor%Erstellen von Besprechungen
Strategie besteht aus 2 Teilen:
1. Wählen Sie Personen in bestimmter Reihenfolge aus;
2. Platzieren Sie Personen aus der Liste nacheinander an der am besten geeigneten Tabelle.
Das Anordnen von Personen in der Auswahlliste ist der Versuch, Personen, die sich zuvor oft getroffen haben, so früh wie möglich zu platzieren und sie an separaten Tischen zu platzieren.
Die Platzierung von Personen ist schwieriger und Hauptzweck in diesem Stadium ist es, die Anzahl der ersten Treffen zu maximieren und die Anzahl der wiederholten Treffen zu minimieren. Es ist also nah am Problem der Konstruktion der richtigen Zielfunktion für das Optimierungsproblem, was in den meisten realen Fällen nicht trivial ist.
Ich wähle dieses Kriterium:
Für jede Tabelle wurden zwei Faktoren gezählt: "attraktiv" ( A ) - warum platzieren Sie die Person an diesem Tisch und "abstoßen" ( R ) - warum kann die Person nicht auf diesem Tisch sitzen.
Dieser Faktor besteht zusammen, um den endgültigen Tabellenanordnungsfaktor zu erhalten:
-A*A - (if A=0 then 0 else R/2) + R
"Attraktiver" Faktor, gezählt als Anzahl der Personen, die bereits am Tisch stehen, mit denen sich die aktuelle Person nicht vorher trifft.
"Repellent" -Faktor gezählt als Summe der Anzahl der Sitzungen der aktuellen Person mit allen bereits am Tisch befindlichen Personen.
Sehr wahrscheinlich ist es nicht so gut, wie es kann, aber genug für Beispielzwecke. Beispielsweise kann die Formel so erweitert werden, dass berücksichtigt wird, wie viel Zeit seit dem letzten Meeting verstrichen ist.
Sie können mit dem Erstellen eines guten Ausdrucks experimentieren, um die Tabelle selbst auszuwählen.
Next ist Code für die Generierung von Meetings.
Code ( SQLFiddle )
%Vor%Ein bisschen mehr Theorie
Die generierte Lösung kann als Ausgangspunkt für einige multikriterielle Optimierungsmethoden verwendet werden, aber um sie zu verwenden, müssen Sie sie haben eine gute formale Formulierung des Problems.
Ich hoffe, dass alle oben genannten Informationen Ihnen helfen, das Problem zu lösen.
Ich weiß nicht, ob das funktioniert, aber du könntest einfach eine Tabelle erstellen und die persönliche Tabelle (nur ID wäre genug) 8 Mal mit einer Kreuzverbindung mit einer WHERE-Klausel einfügen, die in der zweiten Verknüpfung den Mitarbeiter ausschließt .id (zweite Spalte)! = employee.id (erste Spalte). Im dritten cross join müsstest du employee.id (dritte Spalte)! = Employee.id (zweite Spalte) .....
habenIn meinem Kopf würde das alle Kombinationen erzeugen. Dann müssen Sie nur eine zufällig auswählen und speichern, damit Sie sie nicht erneut auswählen.
In SQL ist die Antwort eigentlich ziemlich einfach und erfordert zwei Tabellen, eine Tabelle definiert die Angestellten und die andere die Tabellenplätze. Wie:
Tabelle: Mitarbeiter
Spalten:
EmployeeID - Dies muss eine eindeutige ID sein. Mitarbeitername ActiveEmployee - (J / N) usw.
Tabelle: Sitzplätze
Spalten:
SeatID - Dies muss ein eindeutiger Bezeichner sein. Tisch Nummer TischSitznummer usw.
Definieren Sie nun eine Abfrage, die keine Kriterien erfüllt, die als kartesisches Produkt bekannt sind, in der Regel ein unerwünschtes Ergebnis, jedoch nicht in diesem Fall und bei einigen Data Warehousing-Implementierungen.
%Vor%Dies wird Ihnen ein Ergebnis von jedem Mitarbeiter für jeden Sitzplatz geben. Die Sortierung ergibt unterschiedliche Sitzplätze zuerst an verschiedenen Tischen für die gesamte Bevölkerung. Wenn Ihre Belegschaft viel Umsatz hat, vergleichen Sie die Ergebnisse mit einer Historie und negieren Sie diese Instanz dann aus dem kartesischen Produkt.
Andere Optionen für die Sortierreihenfolge können verwendet werden, z. B. die eindeutigen Felder, wenn Sie die Sitzplätze mehr verwechseln möchten.
Hoffe, das hilft.
Tags und Links sql c# oracle permutation select