Array sortieren mit Permutationen..

[Ducksoul]

hm ja, habe ich letzte Woche sogar schon einen von durchgelesen. Aber an meinem Programmierstil gibts eh noch ne Menge macken. Habe ja effektiv erst zu Beginn meines Praktikums angefangen umfangreichere Sachen zu programmieren (und muss mich zügeln nich jeden Tag dumme Fragen hier ins Forum zu hauen *g*).

Hab das jetzt auch brav geändert. War jedoch nicht die Wurzel des Übels.

Gruß

Edit: Oh man.. Ganze Sätze zu schreiben is schon schwierig ^^

[DeddyH]

Zitat:

Delphi-Quellcode:

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;

Auf diese Weise kannst Du Dir die Schleife eigentlich sparen und gleich den letzten Wert nehmen. Du müsstest also nachdem contains ggf. true wird aus der Schleife springen. Das geht entweder mit break oder indem Du statt der for-Schleife eine while-Schleife mit 2 Bedingungen nimmst.

[Ducksoul]

Delphi-Quellcode:

for j :=  0 to ol.Count - 1 do
    begin
      Priolist := ol[j] as TPriolist;
      if Priolist.prio = arr[i].j_prio then
      begin
        contains := true;
        break;
      end;
    end;

So meinst du, oder? Also dass wenn ich merke dass bereits eine Prioliste für eine Priorität besteht die Schleife abgebrochen wird und nicht auch noch die restlichen Listen durchforstet werden.


Edit:

Aber um nochmal auf ein Problem zurückzukommen.

In meiner Testumgebung habe ich 6 Jobs:

Delphi-Quellcode:

Job1: id=0, prio=7
Job2: id=1, prio=7
Job3: id=2, prio=7
Job4: id=3, prio=5
Job5: id=4, prio=3
Job6: id=5, prio=3

Soll-Ergebnis meiner Funktion wäre

Delphi-Quellcode:

ol[0] --> prio7, arr_jobs(Job1, Job2, Job3)
ol[1] --> prio5, arr_jobs(Job4)
ol[2] --> prio3, arr_jobs(Job5, Job6)

Ist-Ergebnis meiner Funktion wäre

Delphi-Quellcode:

ol[0] --> prio7, arr_jobs(leererJob, leererJob, leererJob)
ol[1] --> prio5, arr_jobs(leererJob)
ol[2] --> prio3, arr_jobs(leererJob, leererJob)

Soll heißen: Es werden Jobs in die Liste eingefügt, welche dann aber alle nil sind :-/
Was mach ich hier falsch?

[Khabarakh]

Wir kennen deine Funktion subListsContain nicht, aber ich kann dir auch so sagen, dass du zu kompliziert denkst und vor allem quadratische Laufzeit fabriziert, hast, wo auch O(n) möglich wäre.

Delphi-Quellcode:

// arr : TList<TJob>
ol := TList<TPrioList>.Create;

for Job in arr do
  prioList := bestehende TPrioList aus ol mit Prio = arr.Prio oder TPrioList.Create;
  prioList.Add(Job);

Das ist der ganze Zauber ;) .

(Gut, mit TList ist es immer noch quadratisch...)

[Ducksoul]

Räusper...

Ich habe die Jobs immer außerhalb des Arrays geschrieben:

Ursprünglich:

Delphi-Quellcode:

Priolist.arr_jobs[size] := arr[j];

Richtig:

Delphi-Quellcode:

Priolist.Jobs[size-1] := arr[j];

@Kabarakh:
Irgendwie is dein Code mir zu einfach. Der will sich mir nich erschließen :-D

[Ducksoul]

Hallo, ich hoffe das is nu die letzte Frage zu diesem Thema:

Ich habe jetzt alle Permutationen pro Prio, möchte die nun zusammenführen.

Also angenommen:

Delphi-Quellcode:

Prio1:
Kombi (J1, J2), (J2, J1)

Prio2:
Kombi (J3)

Prio3:
Kombi (J4, J4, (J5, J4)

--->
resultarray:
J1, J2, J3, J4, J5
J2, J1, J3, J4, J5
J1, J2, J3, J5, J4
J2, J1, J3, J5, J4

Ich habe jetzt probiert das über folgenden Code zu realisieren:

Delphi-Quellcode:

  kz := 0;
  while kz < count do
  begin
    sz := 0;
    for i := 0 to ol.Count - 1 do
    begin
      Priolist := ol[i] as TPriolist;
      for j := 0 to Length(Priolist.Jobs) - 1 do
      begin
        arr_finkombis[kz,sz] := Priolist.Kombis[Priolist.counter, j];
        Inc(sz);
      end;

      Inc(Priolist.counter);
      if Priolist.counter >= Length(Priolist.Kombis) then
        Priolist.counter := 0;
    end;
    Inc(kz);
  end;

kz zählt die Zeile des resultarray
sz zählt die Spalte des resultarray
Jedes mal wenn eine Kombi einer Prio durchgelaufen ist wird ein Zähler hochgezählt, so dass beim nächsten mal die darauffolgende Kombi genommen wird.
Wurden alle Kombis der Prio einmal durchgelaufen, so wird der Zähler wieder null gesetzt und die Kombiliste der Prio wird neu durchlaufen.


Aber das Problem ist, dass ich ja den Counter einer Prioliste erst höher setzen darf, wenn alle kleineren Listen einmal durchgelaufen sind. Ich habe mir gedacht Ne .change Variable in die Klasse Priolist integrieren und wenn ne Liste durchgelaufen is setze ich change auf true.
Und wenn alle kleineren Listen change auf true sind, dann gehe ich erst zur nächsten Kombination.

Ist das ein praktikabler Weg oder gehts evtl. besser?

Gruß

[Khabarakh]

Das dürfte rekursiv leichter zu lösen sein:

Code:

function Kombis(kz, sz, i : Integer) : Integer
  if i = ol.Length then
    Exit(1)

  nPerms := ol[i].Permutationen.Length
  for j = 0 to nPerms - 1 do
    nUnterkombis := Kombis(kz+j, sz + nPerms, i + 1)
    for kz' = kz + j to kz + nUnterkombis - 1 do
      Kopiere permutation nach [kz',sz]

  Exit(nPerms * nUnterkombis)

Keine Ahnung, ob das verständlich ist, also mal ein Beispiel ;) :
Wir haben zwei Priolisten [a,b] und [c,d]. Wir beginnen bei Kombis(0, 0, 0): nPerms von [a,b] ist 2, die erste Permutation der ersten Liste ist [a,b] und wir rufen Kombis(0, 2, 1) auf.
Darin ist nPerms wieder 2, die erste Permutation [c,d]. Für diese rufen wir Kombis(0, 4, 2) = 1 auf, kopieren [c,d] also nur nach [kz+j=0, 2].
Für [d,c] ist kz+j = 1, unterkombis wieder 1, also wird nach [1,2] kopiert.

Code:

- - c d
- - d c
- - - -
- - - -

Wir kehren mit dem Ergebnis 2 * 1 zu i = 0 zurück, [a,b] wird also nach [0+0,0] und [0+1,0] kopiert.

Code:

a b c d
a b d c
- - - -
- - - -

Weiter geht's mit [b,a]...

[Ducksoul]

Huhu,

danke für deinen Tipp, aber das löst mein Problem nicht so recht. Also die Prios in mein Array schreiben und so klappt ja, aber ich muss irgendwie die die Kombinationen tauschen, um alle Möglichkeiten zu erhalten.

In meinem jetzigen Verfahren, bei dem:

Prio1: J1, J2, J3
Prio2: J4,
Prio3: J5, J6

erhalte ich folgendes:

Code:

012345
021354
102345
120354
201345
210354

Und zwar 2x

Fehlen tut:

Code:

012354
021345
102354
120345
201354
210345

Ich weiß aber nichtmal wie die universelle mathematische Lösung dieses Problems wäre. Da macht sich das schlecht diese auch noch in Code umzusetzen *g*

Code bisher:

Delphi-Quellcode:

    // Kombiniere die Kombis der einzelnen Prioritäten
  SetLength(arr_finKombis, count);
  for i := 0 to Length(arr_finKombis) - 1 do
    SetLength(arr_finKombis[i], jobCount);

  for i := 0 to ol.Count - 1 do
  begin
    Priolist := ol[i] as TPriolist;
    kz := 0;
    loops := count div Length(Priolist.Kombis);

    j := 0;
    while j < loops do
    begin
      for k := 0 to Length(Priolist.Kombis) - 1 do
      begin
        sz := 0;
        for l := 0 to ol.Count - 1 do
        begin
          pt := ol[l] as TPriolist;
          if pt.prio = Priolist.prio then
            Break;
          sz := sz + Length(pt.Jobs);
        end;

        for l := 0 to Length(Priolist.Kombis[k]) -1 do
        begin
          arr_finKombis[kz,sz] := Priolist.Kombis[k,l];
          Inc(sz);
        end;
        Inc(kz);
      end;
      Inc(j);
    end;

Is nich so schön kurz und prägnat wie dein Code, aber er macht auch was er soll. :)

[Khabarakh]

Zitat:

Zitat von Ducksoul

danke für deinen Tipp, aber das löst mein Problem nicht so recht.

Ääh, doch? Wenn ich meinen Algorithmus weiterlaufen lasse, ist das Ergebnis

Code:

a b c d
a b d c
b a c d
b a d c

Das ist doch wohl eine Lösung für dein Problem, oder etwa nicht?

[Ducksoul]

Ja bei jeweils 2 Permutationen funktioniert es bei mir auch.

Versuch mal P1(J1, J2, J3) und P2(J4, J5). Da kommen bei mir nach der Hälfte nochmal die gleichen Endkombinationen raus, da ich mit P2 in umgekehrter Reihenfolge beginnen müsste.
Oder hab ich da grad nen ganz argen Denkfehler?

Gruß

EEEDIT: Ne warte mal. Dein Code macht das ja doch anders... Ich editiere dann nochmal, wenn ich deinen Tipp zu Ende durchdacht habe. ^^

Edit 2: Boah ich hab schon keine reine Informatik studiert, weil ich Mathe und so ne Logikprobleme hasse und nu schon wieder sowas... (Offtopic, um meinen Verfassungszustand ma n bissl zu schildern x-p)

Hier mein Zwischenstand:

Delphi-Quellcode:

function KombiGenerator(kz, sz, i: integer) : integer;
var
  nPerms, nUnterkombis, j, kz_, jobs, k: integer;
  Priolist: TPriolist;
begin
  Priolist := ol[i] as TPriolist;

  if i = ol.Count-1 then
    Exit(1);

  jobs := Length(Priolist.Jobs);
  nPerms := Length(Priolist.Kombis);
  for j := 0 to jobs - 1 do
  begin
    nUnterkombis := KombiGenerator(kz+1, sz+jobs, i+1);
    for kz_ := (kz+j) to (kz+nUnterkombis) - 1 do
    begin
      for k := 0 to jobs - 1 do
        resultarray[kz_,sz] := Priolist.Kombis[j,k];
    end;
  end;
  Exit(jobs * nUnterkombis);

end;

Funktioniert so ja natürlich noch nicht. Ich hab nur erstmal deinen Pseudocode umgesetzt. Wenn ich weiter bin geb ich wieder bescheid.