Am 09.06.2013 22:07, schrieb Udo und Susanne Krause:
> Hallo allerseits,
>
>> Mit anderen Worten, wenn der Sysadmin O. R. Dentlich Z > 0 Rechner
>> hat, von denen jeder S = 2 (Z - 1) Jobsauszuführen hat, die 1, 2, 3,
>> ..., S Zeiteinheiten dauern und er möchte, dass alle Rechner
>> gleichzeitig beginnen
>> und dass zu jeder Zeiteinheit x (0 < x < S (S + 1)/2) genau ein Job
>> endet, dann muss er die Jobs gemäss der Matrix
>> mit der Zeilenzahl Z starten.
>
> Hier ist ein Ergebnis für Z = 13:
>
> {{1, 24, 22, 20, 18, 19, 10, 6, 12, 4, 9, 5, 8, 7, 3, 11, 2, 14, 13,
> 15, 16, 17, 21, 23},
> {2, 18, 23, 21, 17, 16, 20, 4, 10, 6, 3, 8, 5, 7, 9, 11, 12, 13, 14,
> 15, 19, 22, 24, 1},
> {3, 2, 24, 17, 11, 15, 7, 16, 6, 18, 14, 1, 20, 19, 21, 12, 22, 5,
> 13, 8, 10, 9, 23, 4},
> {4, 3, 2, 24, 8, 7, 23, 17, 15, 21, 20, 19, 22, 1, 16, 13, 11, 12, 5,
> 14, 6, 18, 9, 10},
> {6, 5, 23, 18, 7, 17, 15, 8, 19, 21, 12, 20, 1, 16, 13, 11, 10, 14,
> 9, 22, 3, 24, 4, 2},
> {8, 7, 6, 5, 4, 23, 20, 19, 18, 17, 15, 1, 21, 11, 12, 13, 14, 16,
> 10, 9, 22, 24, 2, 3},
> {10, 9, 8, 24, 12, 3, 11, 17, 21, 1, 22, 19, 2, 18, 13, 14, 16, 15,
> 20, 23, 4, 5, 6, 7},
> {12, 10, 9, 23, 2, 5, 21, 4, 20, 3, 16, 22, 19, 1, 17, 15, 14, 18,
> 13, 6, 24, 11, 7, 8},
> {13, 10, 9, 7, 6, 5, 24, 22, 16, 14, 15, 20, 17, 18, 1, 19, 21, 23,
> 2, 3, 4, 11, 8, 12},
> {14, 10, 13, 12, 6, 5, 23, 4, 3, 21, 2, 22, 20, 1, 18, 19, 16, 15,
> 17, 11, 24, 7, 8, 9},
> {16, 12, 14, 20, 7, 6, 5, 18, 4, 3, 2, 21, 1, 23, 24, 22, 19, 8, 17,
> 9, 15, 13, 10, 11},
> {17, 19, 2, 20, 7, 13, 6, 5, 11, 22, 1, 23, 24, 21, 16, 4, 10, 8, 3,
> 15, 12, 9, 18, 14},
> {18, 17, 5, 4, 24, 2, 23, 15, 22, 19, 13, 20, 1, 6, 14, 7, 8, 9, 21,
> 10, 3, 11, 12, 16}}
>
> die Berechnung geht wesentlich schneller als diejenige für Z = 11 vom
> Anfang diesen Jahres.
> Z = 11 ist natürlich entsprechend schneller. Doch noch immer rennt der
> Labyrinthalgorithmus
> mit nur einem Ziel vor Augen herum. Angemessener wäre eine
> Vektorsteuerung, dass er mehrere Ziele
> miteinander vereint.
> ----------------------------------------------------------------------------------------
>
> Als Zeitfresser erweist sich folgendes Problem: Gegeben sei eine
> endliche Menge M paarweise
> verschiedener ganzer Zahlen. Gesucht ist die Liste
>
> LS = DeleteDuplicates[Plus @@@ Rest[Subsets[M]]]
>
> also die Liste aller Summen, die sich mit den Zahlen aus M bilden
> lassen, einschliesslich M selber,
> wo bei keine Zahl mehrfach in derselben Summe auftritt.
>
> Zeit wird gefressen, weil Subsets[M] wesentlich länger sein kann als
> das gesuchte Ergebnis.
> Ab einer bestimmten Zeilenzahl wird Subsets[M] von Mma nicht mehr
> berechnet, etwa
>
> In[2]:= Subsets[Range[35]];
>
> During evaluation of In[2]:= General::nomem: The current computation
> was aborted because there was insufficient memory available to
> complete the computation.
>
> Out[2]= SystemException["MemoryAllocationFailure", {Subsets[Range[35]];,
> Subsets[{1, 2, 3, 4, ..., 34, 35}]}]
>
>
> Für vielen Mengen M ist das Ergebnis LS klar, z.B. für M = Range[S]
> ist LS = Range[S (S + 1)/2].
>
> Ist eine Lösung für dieses Problem bekannt?
> ----------------------------------------------------------------------------------------
>
> Gruss
> Udo.
Hallo Udo,
bekannt ist sie mir zwar nicht, aber recht fix rekursiv gebastelt:
Clear[moeglicheSummen];
moeglicheSummen[{}] = {0};
moeglicheSummen[{x_}] = Union[{0, x}];
moeglicheSummen[lst_List] := Module[{n = Length[lst], x, y},
{x, y} = moeglicheSummen /@ Through[{Take, Drop}[lst, Floor[n/2]]];
DeleteDuplicates@Flatten@Outer[Plus, {0}, x, y]
]
Gruß zurück ;)
Peter
moeglicheSummen.nb
Description: application/vnd.wolfram.mathematica
