Opened by ariser at 2013-10-05 21:31
User since
2012-08-17
44 Artikel
BenutzerIn
![[default_avatar]](/battie/theme/default/default_avatar.gif)
2012-08-17
44 Artikel
BenutzerIn
Hi,
ich benötige sowas ähnliches, wie ein multiset aus einer gegebenen Menge.
Leider bin ich kein Mathematiker, deswegen kenne ich schon den Namen des Problems nicht
Eine Menge M mit k Elementen soll mit n verschiedenen Elementen besetzt werden. Dabei muss in der Menge k jedes Element von n mindestens einmal vorkommen, woraus folgt, dass n<=k sein muss.
Es sollen nun für geg. k u. n alle möglichen M berechnet werden. Dabei spielt die Reihenfolge in M keine Rolle, also alle Permutationen einer M werden vernachlässigt.
Oder anders formuliert, die Mengen M sollen nach ihren Elementen sortiert sein.
Ich erklärs noch mal praktisch. Der Disponent (oder wie man das nennt) am Münchner Hauptbahnhof muss jeden Tag einen Autoreisezug mit 10 Wagen zusammenstellen, der nach Rom fährt. Er kann Personenwagen, KFZ-träger, LKW-Träger einstellen, und Güterwagen. Nach der Lok kommen diese Wagen aus Sicherheitsgründen in genau der Reihenfolge. Weil nie alle Buchungen sicher sind, muss er mindestens einen Wagen jeder Art einstellen, in Summe aber 10 erreichen. Also z.B. PPKKKKLLGG. Oder PKLGGGGGGG.
Ich hätte gerne einen Algorithmus, der die Zahl k und die n verschiedenen Elemente, z.b. Strings als Array bekommt und dann alle Kombinationen als AoA zurückgibt. Ok, das AoA wird noch nicht erzeugt, aber das ist ja kein Problem.
Der Witz ist, ich habs schon geschrieben, rekursiv, funktioniert auch. Hier:
Hier fehlt noch die Ausgabe in ein AoA, aber das kann man sich dazudenken.
Fällt jemand spontan ein, wie man das nicht-rekursiv machen kann ohne sich die Finger zu brechen? Ich mein, rekursiver Code ist fast immer unperformant, man macht den Stack voll usw.
ich benötige sowas ähnliches, wie ein multiset aus einer gegebenen Menge.
Leider bin ich kein Mathematiker, deswegen kenne ich schon den Namen des Problems nicht
Eine Menge M mit k Elementen soll mit n verschiedenen Elementen besetzt werden. Dabei muss in der Menge k jedes Element von n mindestens einmal vorkommen, woraus folgt, dass n<=k sein muss.
Es sollen nun für geg. k u. n alle möglichen M berechnet werden. Dabei spielt die Reihenfolge in M keine Rolle, also alle Permutationen einer M werden vernachlässigt.
Oder anders formuliert, die Mengen M sollen nach ihren Elementen sortiert sein.
Ich erklärs noch mal praktisch. Der Disponent (oder wie man das nennt) am Münchner Hauptbahnhof muss jeden Tag einen Autoreisezug mit 10 Wagen zusammenstellen, der nach Rom fährt. Er kann Personenwagen, KFZ-träger, LKW-Träger einstellen, und Güterwagen. Nach der Lok kommen diese Wagen aus Sicherheitsgründen in genau der Reihenfolge. Weil nie alle Buchungen sicher sind, muss er mindestens einen Wagen jeder Art einstellen, in Summe aber 10 erreichen. Also z.B. PPKKKKLLGG. Oder PKLGGGGGGG.
Ich hätte gerne einen Algorithmus, der die Zahl k und die n verschiedenen Elemente, z.b. Strings als Array bekommt und dann alle Kombinationen als AoA zurückgibt. Ok, das AoA wird noch nicht erzeugt, aber das ist ja kein Problem.
Der Witz ist, ich habs schon geschrieben, rekursiv, funktioniert auch. Hier:
Code: (dl
)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
my @typeset = ('P', 'K', 'L', 'G');
my $length = 10;
my @lchain = ();
strangemultiset($length, \@typeset, \@lchain);
exit 0;
sub strangemultiset
{
my $len=$_[0];
my @types=@{$_[1]};
my @chain=@{$_[2]};
my $ltype=shift(@types);
my $var=$len - scalar(@chain) - scalar(@types);
for(my $iter=1; $iter<=$var; ++$iter)
{
push(@chain, $ltype);
if (scalar(@types) == 0)
{
if (scalar(@chain) == $len)
{ # we have a valid set, print it.
print join('.', @chain), "\n";
}
}
else
{
strangemultiset($len, \@types, \@chain);
}
}
}Hier fehlt noch die Ausgabe in ein AoA, aber das kann man sich dazudenken.
Fällt jemand spontan ein, wie man das nicht-rekursiv machen kann ohne sich die Finger zu brechen? Ich mein, rekursiver Code ist fast immer unperformant, man macht den Stack voll usw.