Array sortieren mit Permutationen..

[Ducksoul]

Hi,

der Topicname ist mal wieder äußerst nichtsaussagend, daher mal eine kurze Erläuterung:

Ich habe ein Array mit folgendem Aufbau:

Delphi-Quellcode:

  jobArray: Array of TJob; 

// wobei:
  TJob = record
          j_id: integer;              // Job-ID --> Prozessintern
          j_prio: integer;            // Priorität
          j_color: string;            // Farbe
          j_name: string;             // Name
          j_proc: Array of integer;   // Prozesszeit pro Maschine

Nach dem Füllen dieses Arrays, sollen die TJob's nach ihrer Prioriät (TJob.j_prio) absteigend sortiert werden. Dies habe ich über folgenden Quicksort Algorithmus gelöst:

Delphi-Quellcode:

procedure QuickSort(var A: array of TJob; iLo, iHi: Integer) ;
var
  Lo, Hi, Pivot: Integer;
  T: TJob;
begin
  Lo := iLo;
  Hi := iHi;
  Pivot := A[(Lo + Hi) div 2].j_prio;
  repeat
    while A[Lo].j_prio > Pivot do Inc(Lo) ;
    while A[Hi].j_prio < Pivot do Dec(Hi) ;
    if Lo <= Hi then
    begin
      T := A[Hi];
      A[Hi] := A[Lo];
      A[Lo] := T;
      Inc(Lo) ;
      Dec(Hi) ;
    end;
  until Lo > Hi;
  if Hi > iLo then QuickSort(A, iLo, Hi) ;
  if Lo < iHi then QuickSort(A, Lo, iHi) ;
end;  // Quicksort

Mein Problem: Ich brauche alle möglichen Permutationen, wenn Jobs mit gleichen Prioritäten vorhanden sind. Hab mir nun so gedacht, dass ich nich das Array an sich speicher, sondern ein neues Array anlege mit den ID's der Jobs in jeweils sortierter Reihenfolge.

Aber wie bekomme ich alle möglichen Permutationen raus? Mit dem rekursiven Quicksort wird das schlecht gehen.


Gruß

[Codewalker]

Permutationen über was? Du kannst (wenn du alle haben willst) nur über einer endlichen Menge die Permutationen bilden. Wenn du also Job + Prio nimmst, müsstest du noch sagen, auf welcher Skala die Zahlen sich bewegen. Und dann heißt es, alle Möglichkeiten auflisten.
Und das werden sehr schnell sehr viele. Die Anzahl der k-stelligen Permutationen über einer n-elementigen Menge sind: n! / (n-k)! .

[Khabarakh]

Funktionen, um gesamte Listen zu permutieren, sollten sich zur Genüge finden lassen, also würde ich erst einmal Jobs mit gleicher Priorität zusammenfassen. Danach setzt du die einzelnen Permutationen wieder zu den ganzen Listen zusammen.

[Ducksoul]

Vielen Dank für den Hinweis.

In Java habe ich das gelöste Problem bereits. Aber da mir in Delphi keine ArrayList zur Verfügung steht fiel mir die Portierung nicht ganz so einfach :)

[Khabarakh]

Na dann solltest du doch über T(Object)List<T> schnell zum Ziel kommen :) .

[Ducksoul]

Ich bin jetzt über mehrdimensionale Arrays gegangen. Ich weiß nun aber nicht wie ich weitermachen soll, bzw. wie ich die Permutationen erzeugen und in das Array schreiben soll.

Bis jetzt erstelle ich ein array EqualPrios (zweidimensional), bei welchem zu jeder Priorität (erste Dimension) die entsprechenden Jobs zu finden sind. Nun möchte ich ja die einzelnen Jobs (vom Typ TJob) untereinander kombinieren.
Dazu habe ich jetzt ein dreidimensionales Array angelegt: 1. Dimension entspricht Prioritär, 2. Dimension sind die Anzahl der möglichen Kombinationen (also Anzahl der Jobs Fakultät) und in der dritten Dimension sollen dann die Jobs immer rein in der jeweiligen Reihenfolge.

Ich bin inzwischen soweit:

Delphi-Quellcode:

    // Anzahl möglicher Kombinationen finden
  SetLength(arr_Kombis, Length(arr_EqualPrios));
  for i := 0 to Length(arr_Kombis) - 1 do
  begin
    SetLength(arr_Kombis[i], getFactorial(Length(arr_EqualPrios[i])));
    CreatePerms(arr_EqualPrios[i], arr_Kombis[i]);
    {for j := 0 to Length(arr_Kombis[i]) - 1 do
    begin
      SetLength(arr_Kombis[i,j], Length(arr_EqualPrios[i]));

    end;}
  end;

Um das ganze n bissl übersichtlicher zu gestalten wollte ich die Elemente und die 2.Dimension des Kombi Arrays in eine Prozedur übergeben, dort in dieses Teilarray die möglichen Kombinationen reinschreiben und fertig.
Aber erstens geht es wohl nicht so wie ich mir das gedacht habe (Übergabe 2-dimensionales Array) und zweitens habe ich zwar nen Algorithmus gefunden, welcher Zahlen permutieren kann (siehe hier), jedoch weiß ich nicht wie ich ihn auf mein Problem anpassen kann.

Über konstruktive Vorschläge wäre ich sehr dankbar.

Gruß

[Khabarakh]

Ich habe gedacht, du hättest das Problem in Java bereits gelöst :?: Dann solltest du es doch 1:1 übernehmen können, wahrscheinlich mit einer TList<TList<TJob>>.

PS: Zur Versicherung, dass ich das Problem überhaupt richtig verstehe - aus einer Liste wie

Code:

(A,3);(B,3);(C,2);(D,1);(E,1) // jeweils (ID,Prio)

willst du die Kombinationen

Code:

ABCDE
BACDE
ABCED
BACED

haben?

[Ducksoul]

Ja, in Java sieht das ganze so aus:

Delphi-Quellcode:

// 5. Generiere Permutationen einer jeden neuen ArrayList
      List<List<List<TJob>>> prio_list = new ArrayList<List<List<TJob>>>();
      for (int i = 0; i < equalPrio_list.size(); i++) {
         int[] indices;
         List<TJob> elements = equalPrio_list.get(i);
         List<List<TJob>> li = new ArrayList<List<TJob>>();
         PermutationGenerator x = new PermutationGenerator(elements.size());
         while (x.hasMore()) {
            indices = x.getNext();
            List<TJob> tj_list = new ArrayList<TJob>(10);
            for (int j = 0; j < indices.length; j++)
               tj_list.add(elements.get(indices[j]));
            li.add(tj_list);
         }
         prio_list.add(li);
      }

Und die Klasse zum Generieren von Permutationen:

Delphi-Quellcode:

//--------------------------------------
// Systematically generate permutations. 
// [url]http://www.merriampark.com/perm.htm[/url]
//--------------------------------------

import java.math.BigInteger;

public class PermutationGenerator {

  private int[] a;
  private BigInteger numLeft;
  private BigInteger total;

  //-----------------------------------------------------------
  // Constructor. WARNING: Don't make n too large.
  // Recall that the number of permutations is n!
  // which can be very large, even when n is as small as 20 --
  // 20! = 2,432,902,008,176,640,000 and
  // 21! is too big to fit into a Java long, which is
  // why we use BigInteger instead.
  //----------------------------------------------------------

  public PermutationGenerator (int n) {
    if (n < 1) {
      throw new IllegalArgumentException ("Min 1");
    }
    a = new int[n];
    total = getFactorial (n);
    reset ();
  }

  //------
  // Reset
  //------

  public void reset () {
    for (int i = 0; i < a.length; i++) {
      a[i] = i;
    }
    numLeft = new BigInteger (total.toString ());
  }

  //------------------------------------------------
  // Return number of permutations not yet generated
  //------------------------------------------------

  public BigInteger getNumLeft () {
    return numLeft;
  }

  //------------------------------------
  // Return total number of permutations
  //------------------------------------

  public BigInteger getTotal () {
    return total;
  }

  //-----------------------------
  // Are there more permutations?
  //-----------------------------

  public boolean hasMore () {
    return numLeft.compareTo (BigInteger.ZERO) == 1;
  }

  //------------------
  // Compute factorial
  //------------------

  private static BigInteger getFactorial (int n) {
    BigInteger fact = BigInteger.ONE;
    for (int i = n; i > 1; i--) {
      fact = fact.multiply (new BigInteger (Integer.toString (i)));
    }
    return fact;
  }

  //--------------------------------------------------------
  // Generate next permutation (algorithm from Rosen p. 284)
  //--------------------------------------------------------

  public int[] getNext () {

    if (numLeft.equals (total)) {
      numLeft = numLeft.subtract (BigInteger.ONE);
      return a;
    }

    int temp;

    // Find largest index j with a[j] < a[j+1]

    int j = a.length - 2;
    while (a[j] > a[j+1]) {
      j--;
    }

    // Find index k such that a[k] is smallest integer
    // greater than a[j] to the right of a[j]

    int k = a.length - 1;
    while (a[j] > a[k]) {
      k--;
    }

    // Interchange a[j] and a[k]

    temp = a[k];
    a[k] = a[j];
    a[j] = temp;

    // Put tail end of permutation after jth position in increasing order

    int r = a.length - 1;
    int s = j + 1;

    while (r > s) {
      temp = a[s];
      a[s] = a[r];
      a[r] = temp;
      r--;
      s++;
    }

    numLeft = numLeft.subtract (BigInteger.ONE);
    return a;

  }

}

Allerdings weiß ich nich wie ich das auf Delphi portieren soll :(

Ich bin nu auch nich so der dolle Programmierer. Und wenns um OO geht, sieht das ganze noch n bissl düsterer aus.


Edit:
Um auf deine Frage zu antworten:

Ich habe ein Array mit TJobs (was Records, welche verschiedene Daten enthalten, sind). Und ich hätte dann wenn ich ein Array

arr ( job1, job2, job3) habe gerne alle 6 möglichen Kombinationen. :)

Gruß


Edit2: Um nicht die Lorbeeren einzuheimsen: Der Javacode ist nicht von mir. Lediglich der Delphicode den ich bis jetzt habe sind meine Ergüsse *g*

[Ducksoul]

Ich habe, weil mein AdHoc Programmieren nichts gebracht hat, nun nochmal von vorne angenfangen und mich auch ein wenig zur TObjectList belesen.

Mein Plan:
1. Erstelle eine Klasse TPriolist mit prio: integer; arr_jobs: array of TJob
2. Für alle Prioritäten erstelle eine Priolist vom Typ TPriolist, gebe prio die Priorität und füge arr_jobs alle Jobs mit dieser Priorität hinzu.
3. Speichere jede Priolist in ol vom Typ TObjectlist
etc...

Das funktioniert auch ganz gut, bis auf dass er die Jobs nicht speichert. Also nachdem ich fertig bin ist in jeder Priolist die Prio gespeichert, die Länge des arr_jobs richtig, aber im Array sind alle Variablen des Jobs 0.

Was hab ich nu schon wieder falsch?

Delphi-Quellcode:

    // verschiedene Prios in Priolist speichern
  for i := 0 to Length(arr) - 1 do
  begin
    contains := false;
    for j := 0 to ol.Count - 1 do
    begin
      Priolist := ol[j] as TPriolist;
      if arr[i].j_prio = Priolist.prio then
        contains := true;
    end;

    if contains = false then
    begin
      Priolist := TPriolist.Create;
      Priolist.prio := arr[i].j_prio;

      for j := 0 to Length(arr) - 1 do
      begin
        size := Length(Priolist.arr_jobs);
        if arr[j].j_prio = Priolist.prio then
        if not subListsContain(Priolist, arr[j]) then
        begin
          Inc(size);
          SetLength(Priolist.arr_jobs, size);
          Priolist.arr_jobs[size] := arr[j];
        end;
      end;
      ol.Add(Priolist);
    end;
  end;

[daywalker9]

Also aufjedenfall erstmal das rausschmeißen:

Delphi-Quellcode:

  if contains = false then

Und dadurch ersetzten:

Delphi-Quellcode:

  if not contains then

Dazu gab es schon etliche Beiträge hier im Forum