Discussion:
Kombinatorischer Begriff gesucht
Add Reply
Stefan Ram
2018-08-23 18:18:00 UTC
Antworten
Permalink
Raw Message
Gibt es einen Begriff für die folgende Art von "Kombination"?

Gegeben seien n·m unterschiedliche Dinge (z.B. 2×3).

Wie viele unterschiedliche Arten gibt es, sie auf n Mengen
mit jeweils m Elementen aufzuteilen?

z.B.

{ 0, 1, 2, 3 }, n = 2, m = 2

Wie viele Möglichkeiten gibt es die vier Zahlen
0, 1, 2 und 3 auf zwei Mengen L und R mit jeweils
2 Elementen aufzuteilen?

0) L={0, 1), R={2, 3}
1) L={0, 2), R={1, 3}
2) L={0, 3), R={1, 2}
3) L={1, 2), R={0, 3}
4) L={1, 3), R={0, 2}
5) L={2, 3), R={0, 1}

Anscheinend 6.

D.h.

L={0, 1}, R={2, 3};
L={1, 0}, R={2, 3};
L={0, 1}, R={3, 2} und
L={0, 1}, R={2, 3}.

werden /nicht/ unterschieden, da in allen vier Fällen 0 und
1 beide in L und 2 und 3 beide in R sind und es in einer Menge
keine "Reihenfolge" gibt.

Ich suche trotz der obigen Frage /nicht/ die Anzahl, sondern
einen /Namen/ für dieses Art der Bildung unterschiedicher
Situationen. So einen Begriff, wie beispielsweise "Permutation".
Klaus Loeffler
2018-08-23 20:25:10 UTC
Antworten
Permalink
Raw Message
Post by Stefan Ram
Gibt es einen Begriff für die folgende Art von "Kombination"?
Gegeben seien n·m unterschiedliche Dinge (z.B. 2?3).
Wie viele unterschiedliche Arten gibt es, sie auf n Mengen
mit jeweils m Elementen aufzuteilen?
z.B.
{ 0, 1, 2, 3 }, n = 2, m = 2
Wie viele Möglichkeiten gibt es die vier Zahlen
0, 1, 2 und 3 auf zwei Mengen L und R mit jeweils
2 Elementen aufzuteilen?
0) L={0, 1), R={2, 3}
1) L={0, 2), R={1, 3}
2) L={0, 3), R={1, 2}
3) L={1, 2), R={0, 3}
4) L={1, 3), R={0, 2}
5) L={2, 3), R={0, 1}
Anscheinend 6.
D.h.
L={0, 1}, R={2, 3};
L={1, 0}, R={2, 3};
L={0, 1}, R={3, 2} und
L={0, 1}, R={2, 3}.
werden /nicht/ unterschieden, da in allen vier Fällen 0 und
1 beide in L und 2 und 3 beide in R sind und es in einer Menge
keine "Reihenfolge" gibt.
Ich suche trotz der obigen Frage /nicht/ die Anzahl, sondern
einen /Namen/ für dieses Art der Bildung unterschiedicher
Situationen. So einen Begriff, wie beispielsweise "Permutation".
Vermutlich meinst du den Begriff der Partition; das ist eine Zerlegung
einer Menge M in paarweise elementfremde Teilmengen. Wie der Begriff der
Zerlegung schon suggeriert, ergibt die Vereinigung dieser Teilmengen
wieder M.

Klaus-R.
IV
2018-08-23 20:55:00 UTC
Antworten
Permalink
Raw Message
Post by Klaus Loeffler
Post by Stefan Ram
Gibt es einen Begriff für die folgende Art von "Kombination"?
Gegeben seien n·m unterschiedliche Dinge (z.B. 2?3).
Wie viele unterschiedliche Arten gibt es, sie auf n Mengen mit jeweils
m Elementen aufzuteilen?
Vermutlich meinst du den Begriff der Partition; das ist eine Zerlegung
einer Menge M in paarweise elementfremde Teilmengen.
Wohlgemerkt Mengenpartitionen, nicht Zahlpartitionen.
Stephan Gerlach
2018-08-23 23:11:51 UTC
Antworten
Permalink
Raw Message
Post by Stefan Ram
Gibt es einen Begriff für die folgende Art von "Kombination"?
Gegeben seien n·m unterschiedliche Dinge (z.B. 2×3).
Warum hier die Unterscheidung zwischen n und m.
D.h. warum wird die Anzahl der Dinge faktorisiert?
Aber mal abwarten...
Post by Stefan Ram
Wie viele unterschiedliche Arten gibt es, sie auf n Mengen
mit jeweils m Elementen aufzuteilen?
... aha, deswegen. Damit die Anzahl der Dinge durch die Anzahl der
Mengen teilbar ist.

Etwas allgemeiner könntest du fragen:

Wie viele unterschiedliche Arten gibt es, sie auf n Mengen
M_1, M_2,... , M_n
mit jeweils den Element-Anzahlen
m_1, m_2,..., m_n
mit
Summe{k=1 bis n} m_k = n·m
aufzuteilen. Bei dir sind alle m_k=m (konstante Anzahl Elemente in jeder
Menge). IMHO wird das Problem dadurch nur unwesentlich schwerer.
Post by Stefan Ram
z.B.
{ 0, 1, 2, 3 }, n = 2, m = 2
Wie viele Möglichkeiten gibt es die vier Zahlen
0, 1, 2 und 3 auf zwei Mengen L und R mit jeweils
2 Elementen aufzuteilen?
0) L={0, 1), R={2, 3}
1) L={0, 2), R={1, 3}
2) L={0, 3), R={1, 2}
3) L={1, 2), R={0, 3}
4) L={1, 3), R={0, 2}
5) L={2, 3), R={0, 1}
Anscheinend 6.
D.h.
L={0, 1}, R={2, 3};
L={1, 0}, R={2, 3};
L={0, 1}, R={3, 2} und
L={0, 1}, R={2, 3}.
werden /nicht/ unterschieden, da in allen vier Fällen 0 und
1 beide in L und 2 und 3 beide in R sind und es in einer Menge
keine "Reihenfolge" gibt.
Wenn n=2 ist, dann ist das eine der Standard-Aufgaben der Kombinatorik.
Du brauchst hier nur die Elemente für Menge L auszuwählen; die Menge R
ergibt sich automatisch als "Restmenge". Die Standardaufgabe ist "k-mal
'ziehen' aus n Objekten, ohne Wiederholung, Reihenfolge unwichtig".
Das nennt man (glaube ich) "Kombinationen ohne Wiederholung".
Die Formel für die Anzahl ist (für allgemeine m) in diesem Fall
Anzahl = (2·m über 2).
In deinem Fall, da m=2, also
Anzahl = (2·2 über 2) = (4 über 2) = 6.

(Auch, wenn du das nicht wissen wolltest.)
Post by Stefan Ram
Ich suche trotz der obigen Frage /nicht/ die Anzahl, sondern
einen /Namen/ für dieses Art der Bildung unterschiedicher
Situationen. So einen Begriff, wie beispielsweise "Permutation".
Wenn n>2 ist, dann geht der Rechenweg für die Anzahl grob gesagt so, daß
man mehrere verschiedene Binomialkoeffizienten der Form (a über b)
miteinander multiplizieren muß.
Mit jedem dieser Binomialkoeffizienten für sich allein kann man die
Anzahl der Möglichkeiten für einen Fall "Kombinationen ohne
Wiederholung" berechnen.

Ob es nun für deren Produkt einen kombinatorischen Begriff gibt, ist mir
nicht bekannt.
Ohne zu googlen oder die anderen Antworten zu lesen, würde ich es
"Kombination von (Kombinationen ohne Wiederholung)"
nennen.
--
Post by Stefan Ram
Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
Stefan Ram
2018-08-23 22:36:17 UTC
Antworten
Permalink
Raw Message
Post by Stephan Gerlach
Ob es nun für deren Produkt einen kombinatorischen Begriff gibt, ist mir
nicht bekannt.
Ohne zu googlen oder die anderen Antworten zu lesen, würde ich es
"Kombination von (Kombinationen ohne Wiederholung)"
nennen.
Danke für alle Antworten!

Motivation ist die:

Ich will alle Partitionen in Teilmengen der Mächtigkeit m
(im folgenden Beispiel: m=3) aufzählen (durchlaufen).

Dazu kann ich beispielsweise alle Permutationen eines Tupels
der Elemente erzeugen, in Teile der Größe m zerschneiden,
dann alles Tupel wieder als Mengen interpretieren und
schließlich die schon gesehenen Mengen ausfiltern.

In Python:

main.py

import itertools

basis =[ 0, 1, 2, 3, 4, 5 ]
n = 3 # size of the subsets

seen = set()

for p in itertools.permutations( basis ):
partition = frozenset( [ frozenset( p[ i: i + n ]) for i in range( 0, len( p ),n ) ])
if partition not in seen: seen.add( partition ); print( partition )

Protokoll

frozenset({frozenset({0, 1, 2}), frozenset({3, 4, 5})})
frozenset({frozenset({2, 4, 5}), frozenset({0, 1, 3})})
frozenset({frozenset({2, 3, 5}), frozenset({0, 1, 4})})
frozenset({frozenset({0, 1, 5}), frozenset({2, 3, 4})})
frozenset({frozenset({1, 4, 5}), frozenset({0, 2, 3})})
frozenset({frozenset({1, 3, 5}), frozenset({0, 2, 4})})
frozenset({frozenset({1, 3, 4}), frozenset({0, 2, 5})})
frozenset({frozenset({0, 3, 4}), frozenset({1, 2, 5})})
frozenset({frozenset({0, 3, 5}), frozenset({1, 2, 4})})
frozenset({frozenset({1, 2, 3}), frozenset({0, 4, 5})})

Diese Art der Erzeugung ist aber ineffizient, da ich erst 720
Permutationen generiere, um dann nur 10 davon auszuwählen.

Wenn ich wüßte, wie das genau heißt (nicht allgemein "Partition",
sondern speziell für den Fall /gleichgroßer Teilmengen vorgegebener
Größe/), könnte ich gezielter nach einem effizienteren Generator
dafür suchen.

Das ist für mich typisch Kombinatorik: Du willst irgendetwas machen.
Das Hauptproblem besteht darin, herauszufinden, was die Fach-
bezeichnung in der Kombinatorik dafür ist. Wenn Du das
einmal herausgefunden hast, kannst Du viele Quellen finden,
und der Rest ist dann einfach.
Stefan Ram
2018-08-23 23:38:09 UTC
Antworten
Permalink
Raw Message
Post by Stefan Ram
frozenset({frozenset({0, 1, 2}), frozenset({3, 4, 5})})
Hier einmal die Partitionen einer Menge mit 6 Elementen
in Mengen mit 2 beziehungsweise 3 Elementen, von mir sortiert:

{0, 1}{2, 3}{4, 5}
{0, 1}{2, 4}{3, 5}
{0, 1}{2, 5}{3, 4}
{0, 2}{1, 3}{4, 5}
{0, 2}{1, 4}{3, 5}
{0, 2}{1, 5}{3, 4}
{0, 3}{1, 2}{4, 5}
{0, 3}{1, 4}{2, 5}
{0, 3}{1, 5}{2, 4}
{0, 4}{1, 2}{3, 5}
{0, 4}{1, 3}{2, 5}
{0, 4}{1, 5}{2, 3}
{0, 5}{1, 2}{3, 4}
{0, 5}{1, 3}{2, 4}
{0, 5}{1, 4}{2, 3}

{0, 1, 2}{3, 4, 5}
{0, 1, 3}{2, 4, 5}
{0, 1, 4}{2, 3, 5}
{0, 1, 5}{2, 3, 4}
{0, 2, 3}{1, 4, 5}
{0, 2, 4}{1, 3, 5}
{0, 2, 5}{1, 3, 4}
{0, 3, 4}{1, 2, 5}
{0, 3, 5}{1, 2, 4}
{0, 4, 5}{1, 2, 3}

In irgendeiner der Partitionen muß die 0 sein, also können
wir die 0 oBdA immer "ganz links" stehen lassen (wie oben).
Mehr Verallgemeinerungsfähiges sehe ich im Moment nicht.
Stefan Ram
2018-08-24 00:16:30 UTC
Antworten
Permalink
Raw Message
Post by Stefan Ram
Post by Stefan Ram
frozenset({frozenset({0, 1, 2}), frozenset({3, 4, 5})})
Hier einmal die Partitionen einer Menge mit 6 Elementen
{0, 1}{2, 3}{4, 5}
Ich glaube, ich kann jetzt für spezielle Fälle manuell einen
effizienteren Algorithmus als den vorherigen schreiben.
Beispielsweise für 15 Elemente in Teilmengen zu je 3 Elementen.

Ich wähle zunächst alle 3er Kombinationen (wobei das erste
Element der Kombination oBdA immer 0 ist) und dann lösche
ich die bereits verwendeten Elemente und bilde dann alle
3er Kombinationen der verbleibenden Elemente.

Das folgende Programm hat beispielsweise in der Zeit, in der
ich den obersten Absatz schrieb, insgesamt 33633600 Möglichkeiten
gezählt.

from itertools import combinations

basis =[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 ]
m = 3 # size of the subsets

count = 0

del basis[basis.index(0)]
for r0 in combinations( basis, m-1 ):
t0 = ( 0, )+r0
x0,y0=r0
basis0=basis.copy()
del basis0[basis0.index(x0)]
del basis0[basis0.index(y0)]
for t1 in combinations( basis0, m ):
x1,y1,z1=t1
basis1=basis0.copy()
del basis1[basis1.index(x1)]
del basis1[basis1.index(y1)]
del basis1[basis1.index(z1)]
for t2 in combinations( basis1, m ):
x2,y2,z2=t2
basis2=basis1.copy()
del basis2[basis2.index(x2)]
del basis2[basis2.index(y2)]
del basis2[basis2.index(z2)]
for t3 in combinations( basis2, m ):
x3,y3,z3=t3
basis3=basis2.copy()
del basis3[basis3.index(x3)]
del basis3[basis3.index(y3)]
del basis3[basis3.index(z3)]
for t4 in combinations( basis3, m ):
x4,y4,z4=t4
basis4=basis3.copy()
del basis4[basis4.index(x4)]
del basis4[basis4.index(y4)]
del basis4[basis4.index(z4)]
# print( t0, t1, t2, t3, t4 )
count += 1

print( count )

Das ist zwar wirkliche keine schöne Lösung, aber erstmal ein
Ausgangspunkt, vielleicht mit Rekursion verallgemeinerbar.
Stefan Ram
2018-08-24 01:43:18 UTC
Antworten
Permalink
Raw Message
Post by Stefan Ram
Ich glaube, ich kann jetzt für spezielle Fälle manuell einen
Nur ein kurzer Abschlußbericht:

Meine naive Idee, Kirkmans Problem durch einen Algorithmus
lösen zu können, der zunächst alle Partitionen "durchprobiert"
und dann unpassende streicht, ist gescheitert. - Solch ein
Algorithmus findet zwar eine Lösung, welche die Anforderungen
erfüllt, aber im allgemeinen nicht die /umfangreichste/ Lösung.

Aber ich habe eben vielleicht eine Antwort auf meine einleitende
Frage gefunden. Es könnte sein, daß ich nach dem Begriff "design"
gesucht hatte:

|This question, posed by Reverend Kirkman in the middle of the
|previous century, has stimulated mathematics for a long time
|and finally led to the development of the concept of a
|design. In mathematical language, we look for a design on 15
|points with block length 3, such that every pair of points is
|contained in at most one block - in fact, it turns out that
|(15 \choose 2) = 7 · 5 · (3 \choose 2), so every pair of
|points is contained in exactly one block.
www.algorithm.uni-bayreuth.de/en/research/discreta/EXAMPLES/kirkman.html

|A t-(v, k, A) design is a block design on v points with
|blocks of size k such that any set of t points is
|covered by (i.e., is a subset of) precisely A blocks.
Handbook of Combinatorics - R.L. Graham (1995)
IV
2018-08-26 13:48:34 UTC
Antworten
Permalink
Raw Message
Aber ich habe eben vielleicht eine Antwort auf meine einleitende Frage
...
A t-(v, k, A) design is a block design on v points with blocks of size k
such that any set of t points is covered by (i.e., is a subset of)
precisely A blocks.
Handbook of Combinatorics - R.L. Graham (1995)
Geht es bei Dir um 1-(v,k,1)-Designs bzw. 1-(n*m,m,1)-Designs?

Um zu schauen, ob mein Algorithmenansatz richtig ist oder ob mein eigenes
Programm das Richtige berechnet, rechne ich zum Vergleich mit Maple,
Mathematica oder Sage (http://sagecell.sagemath.org/).

Ich nutze aus, daß es für einfache kombinatorische Objekte wie
Mengenpartitionen und Permutationen effiziente Algorithmen gibt.
In Maple berechne ich die Mengenpartitionen, dann die Permutationen jedes
Blocks, und setze die permutierten Blöcke wieder zusammen.
Damit ist die Kombinatorische Explosion verhindert und die umständliche
Suche der Blöcke die keine gemeinsamen Elemente haben und deren Kombination
alle v Objekte enthält umgangen.
Sicher ist es nicht der effektivste Algorithmus. Vielleicht gibt es ja einen
effektiven Algorithmus auf Basis von Gray-Codes.

Interessieren Dich nur die Anzahlen, nur die Objekte selber, oder benötigst
Du eine eigenes Programm dafür?

Gib einfach escheid wenn ich irgendwie helfen kann.
Detlef Müller
2018-08-24 08:31:24 UTC
Antworten
Permalink
Raw Message
Post by Stefan Ram
Post by Stefan Ram
Post by Stefan Ram
frozenset({frozenset({0, 1, 2}), frozenset({3, 4, 5})})
Hier einmal die Partitionen einer Menge mit 6 Elementen
{0, 1}{2, 3}{4, 5}
Ich glaube, ich kann jetzt für spezielle Fälle manuell einen
effizienteren Algorithmus als den vorherigen schreiben.
Beispielsweise für 15 Elemente in Teilmengen zu je 3 Elementen.
Ich wähle zunächst alle 3er Kombinationen (wobei das erste
Element der Kombination oBdA immer 0 ist) und dann lösche
ich die bereits verwendeten Elemente und bilde dann alle
3er Kombinationen der verbleibenden Elemente.
Das ist sicher schneller, als erst blind alle Kombinationen zu
bilden und dann auszudünnen, so schlägt die kombinatorische
Explosion der Möglichkeiten nicht so schnell zu.

[...]

Die Kombinatorische Interpretation ist ja:

Verteile n*m Objekte auf n Schachteln der Größe m.

Die Anzahl der Möglichkeiten wäre, wenn die Reihenfolge der Schachteln
relevant ist, durch den "Multinomialkoeffizienten" gegeben.
Hier ist noch durch m! zu dividieren (Permutationen der Schachteln).

Da hier die Reihenfolge der Schachteln unerheblich ist, können wir
annehmen, daß diese aufsteigend nach dem jeweils kleinsten enthaltenen
Objekt geordnet sein sollen.
Ich würde dann in die erste Schachtel das kleinste Objekt
füllen und dann aufsteigend nach Größe jeweils m-1 weitere
Objekte (also genau Dein Vorschlag).

Mit den restlichen Objekten sind dann noch auf n-1 Schachteln zu
füllen.
Wenn man dabei immer mit dem kleinsten verbliebenen Objekt
anfängt, sind die Schachteln automatisch nach den jeweils
kleinsten enthaltenen Objekten aufsteigend sortiert.

Daraus ergibt sich dann folgender rekursiver Algorithmus:
A(L, n): (L=Liste der Objekte, n=Anzahl der Schachteln)
- L sei die Menge {o_1, ..., o_{n*m}} von zu verteilenden Objekten.
- Das kleinste Objekt o_1 aus L kommt in die Schachtel S.
- Für jede Ergänzung S=[o_1, r_2, ..., r_m] mit verschiedenen weiteren
Objekten aus L (in aufsteigender Reihenfolge):
- Füge S an die Ausgabezeile an.
- Ist L ohne S leer? Dann:
- merke die aktuelle Ausgabezeile (=Lösungskombination).
- entferne S wieder aus der Ausgabezeile.
- return.
- Ist L ohne S nicht leer? Dann:
- Rufe A(L ohne S, n-1) auf.
- entferne S wieder aus der Ausgabezeile.
- return.

Wenn da jetzt kein Denkfehler eingebaut ist, sollten damit
alle Kombinationen systematisch durchlaufen werden.
Wenn man immer schön alle Listen sortiert hält, dürfte es ohne
tiefer liegende Tricks auch nicht schneller gehen.
Da man ja alle Ergebnis-Kombinationen ausgeben will und daher
jede einmal "anfassen" muß sehe ich nur noch die mögliche Idee,
mit irgend einem Zaubertrick die Rekursion zu vermeiden.

Gruß,
Detlef
Post by Stefan Ram
Das folgende Programm hat beispielsweise in der Zeit, in der
ich den obersten Absatz schrieb, insgesamt 33633600 Möglichkeiten
gezählt.
from itertools import combinations
basis =[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 ]
m = 3 # size of the subsets
count = 0
del basis[basis.index(0)]
t0 = ( 0, )+r0
x0,y0=r0
basis0=basis.copy()
del basis0[basis0.index(x0)]
del basis0[basis0.index(y0)]
x1,y1,z1=t1
basis1=basis0.copy()
del basis1[basis1.index(x1)]
del basis1[basis1.index(y1)]
del basis1[basis1.index(z1)]
x2,y2,z2=t2
basis2=basis1.copy()
del basis2[basis2.index(x2)]
del basis2[basis2.index(y2)]
del basis2[basis2.index(z2)]
x3,y3,z3=t3
basis3=basis2.copy()
del basis3[basis3.index(x3)]
del basis3[basis3.index(y3)]
del basis3[basis3.index(z3)]
x4,y4,z4=t4
basis4=basis3.copy()
del basis4[basis4.index(x4)]
del basis4[basis4.index(y4)]
del basis4[basis4.index(z4)]
# print( t0, t1, t2, t3, t4 )
count += 1
print( count )
Das ist zwar wirkliche keine schöne Lösung, aber erstmal ein
Ausgangspunkt, vielleicht mit Rekursion verallgemeinerbar.
--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de
Ralf Goertz
2018-08-24 15:21:50 UTC
Antworten
Permalink
Raw Message
Am Fri, 24 Aug 2018 10:31:24 +0200
Post by Detlef Müller
A(L, n): (L=Liste der Objekte, n=Anzahl der Schachteln)
- L sei die Menge {o_1, ..., o_{n*m}} von zu verteilenden Objekten.
- Das kleinste Objekt o_1 aus L kommt in die Schachtel S.
- Für jede Ergänzung S=[o_1, r_2, ..., r_m] mit verschiedenen weiteren
- Füge S an die Ausgabezeile an.
- merke die aktuelle Ausgabezeile (=Lösungskombination).
- entferne S wieder aus der Ausgabezeile.
- return.
- Rufe A(L ohne S, n-1) auf.
- entferne S wieder aus der Ausgabezeile.
- return.
Wenn da jetzt kein Denkfehler eingebaut ist, sollten damit
alle Kombinationen systematisch durchlaufen werden.
Wenn man immer schön alle Listen sortiert hält, dürfte es ohne
tiefer liegende Tricks auch nicht schneller gehen.
Da man ja alle Ergebnis-Kombinationen ausgeben will und daher
jede einmal "anfassen" muß sehe ich nur noch die mögliche Idee,
mit irgend einem Zaubertrick die Rekursion zu vermeiden.
Ohne jetzt ganz lange darüber nachgedacht zu haben. Wenn ich solche
„Kombinationen“ brauche, benutze ich (unter C++) gewöhnlich
next_permutation(). Da muss ich mir überhaupt keinen Kopf machen, ob ich
irgend etwas schon hatte, weil das durch die Funktion erledigt wird. Ich
baue mir am Anfang einen vector der Form

0 0 1 1 2 2

und lasse alle Permutationen durchlaufen. Da nicht alle Elemente
verschieden sind werden nicht alle 6! Permutationen erzeugt, sondern nur
nur die einzigartigen. Für jede Permutation suche ich zunächst die
Positionen der 0, dann die der 1 etc. Diese Positionen sind die
Teilmengen…

Jetzt habe ich nachgedacht (und programmiert), und auch wenn ich den Weg
nach wie vor elegant finde, werden leider alle Permutationen der Sets
gefunden. Habe das dann mit set repariert, was automatisch die Dubletten
wegwirft. Hier trotzdem das Programm


#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

void list_all(int n, int m) {
vector<int> v(n*m);
auto it=v.begin();
for (int i=0;i<n;++i) {
for (int j=0;j<m;++j)
*it++=i;
}
set<set<vector<int>>> res;
do {
set<vector<int>> s_cand;
for (int i=0;i<n;++i) {
it=v.begin();
vector<int> v_cand(m);
auto it2=v_cand.begin();
while (it!=v.end() && (it=find_if(it,v.end(),[i](int j) {return i==j;}))!=v.end()) {
*it2++=it++-v.begin();
}
s_cand.insert(v_cand);
}
res.insert(s_cand);
} while (next_permutation(v.begin()+1,v.end()));
for (auto i:res) {
for (auto j:i) {
cout<<"(";
for (auto k:j)
cout<<" "<<k;
cout<<" )";
}
cout<<endl;
}
}

int main() {
list_all(3,2);
}


output:

( 0 1 )( 2 3 )( 4 5 )
( 0 1 )( 2 4 )( 3 5 )
( 0 1 )( 2 5 )( 3 4 )
( 0 2 )( 1 3 )( 4 5 )
( 0 2 )( 1 4 )( 3 5 )
( 0 2 )( 1 5 )( 3 4 )
( 0 3 )( 1 2 )( 4 5 )
( 0 3 )( 1 4 )( 2 5 )
( 0 3 )( 1 5 )( 2 4 )
( 0 4 )( 1 2 )( 3 5 )
( 0 4 )( 1 3 )( 2 5 )
( 0 4 )( 1 5 )( 2 3 )
( 0 5 )( 1 2 )( 3 4 )
( 0 5 )( 1 3 )( 2 4 )
( 0 5 )( 1 4 )( 2 3 )
Detlef Müller
2018-08-24 17:53:46 UTC
Antworten
Permalink
Raw Message
Post by Ralf Goertz
Am Fri, 24 Aug 2018 10:31:24 +0200
[...]
Post by Ralf Goertz
Post by Detlef Müller
A(L, n): (L=Liste der Objekte, n=Anzahl der Schachteln)
- L sei die Menge {o_1, ..., o_{n*m}} von zu verteilenden Objekten.
- Das kleinste Objekt o_1 aus L kommt in die Schachtel S.
- Für jede Ergänzung S=[o_1, r_2, ..., r_m] mit verschiedenen weiteren
- Füge S an die Ausgabezeile an.
- merke die aktuelle Ausgabezeile (=Lösungskombination).
- entferne S wieder aus der Ausgabezeile.
- return.
- Rufe A(L ohne S, n-1) auf.
- entferne S wieder aus der Ausgabezeile.
- return.
[...]
Post by Ralf Goertz
Jetzt habe ich nachgedacht (und programmiert), und auch wenn ich den Weg
nach wie vor elegant finde, werden leider alle Permutationen der Sets
gefunden. Habe das dann mit set repariert, was automatisch die Dubletten
wegwirft. Hier trotzdem das Programm
Leider kann ich C++ und die Bibliotheken nicht gut genug, um da
mitreden zu können.
Bordmittel aus Bibliotheken sollten effizient und nach "state of
the art" programmiert sein und gewöhnlich besser als
eigen-gefruckel (von den Grauen Haaren, die einem rekursive
programme bescheren können ganz abzusehen).

Allerdings bei 3 Teilmengen a 5 Elementen sind 126126 Möglichkeiten
durch zu iterieren - wenn man da erst mal alle Permutationen von 15
Elementen durchgeht, sind das 1307674368000 Möglichkeiten, aus denen
dann gesiebt werden muss ... selbst wenn die Bibliotheksfunktion die
in O(1) ausspuckt, wird das kritisch.
Post by Ralf Goertz
#include <iostream>
[... Programm ...]
Post by Ralf Goertz
( 0 1 )( 2 3 )( 4 5 )
( 0 1 )( 2 4 )( 3 5 )
( 0 1 )( 2 5 )( 3 4 )
( 0 2 )( 1 3 )( 4 5 )
( 0 2 )( 1 4 )( 3 5 )
( 0 2 )( 1 5 )( 3 4 )
( 0 3 )( 1 2 )( 4 5 )
( 0 3 )( 1 4 )( 2 5 )
( 0 3 )( 1 5 )( 2 4 )
( 0 4 )( 1 2 )( 3 5 )
( 0 4 )( 1 3 )( 2 5 )
( 0 4 )( 1 5 )( 2 3 )
( 0 5 )( 1 2 )( 3 4 )
( 0 5 )( 1 3 )( 2 4 )
( 0 5 )( 1 4 )( 2 3 )
Scheint ja zu passen - was passiert bei 3*5 Objekten und Drei Teilmengen
(hier gibt man wohl zweckmäßigerweise nur die Anzahl der Lösungen aus)?

Die Diskussion wohl schon bei mäßig großen Objektmengen
akademisch, da die Anzahl kombinatorisch explodiert.

Gruß,
Detlef
--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de
Helmut Richter
2018-08-24 19:35:03 UTC
Antworten
Permalink
Raw Message
Post by Detlef Müller
Allerdings bei 3 Teilmengen a 5 Elementen sind 126126 Möglichkeiten
durch zu iterieren - wenn man da erst mal alle Permutationen von 15
Elementen durchgeht, sind das 1307674368000 Möglichkeiten, aus denen
dann gesiebt werden muss ... selbst wenn die Bibliotheksfunktion die
in O(1) ausspuckt, wird das kritisch.
Ich verstehe das Problem nicht. Kombinationen hat man doch ruckzuck. Also
als erstes die 0 willkürlich auswählen und dann alle Kombinationen von 4 aus
den anderen 14; als Ergebnis ist das die erste Menge von den dreien. Dann
von den übrigen 10 Zahlen die kleinste Zahl willkürlich wählen und wieder 4
von den übrigen; das Ergebnis ist dann die zweite, zur vorher gewählten
ersten Menge passende. Die übrigen 5 Zahlen bilden die dritte dazu. Für den
ersten Schritt gibts also (14 4) = 1001 Möglichkeiten, für jede davon im
zweiten Schritt (9 4) = 126. Alles recht handlich, wenn man es nicht mit
Bleistift und Papier machen muss.

Kombinationen aufzählen macht man am einfachsten, indem man eine Kombination
{a_1, ..., a_n} als Binärzahl Summe(i=1,...,n) 2^a_i schreibt. Man fängt mit
der kleinsten Kombination {0, ..., n-1} an, also der Binärzahl 2^n-1.

Haben wir nun eine Kombination, die durch die Binärzahl x dargestellt wird,
bilden wir die Zahl, die als Menge betrachtet nur aus dem kleinsten Element
besteht, also der letzten Binärziffer von x, die 1 ist:
y = x and (x xor (x-1)). Die addieren wir drauf. Das Ergebins hat vielleicht
weniger als n Einsen, die flicken wir hinten hinein.

Beispiel: Kombinationen von 4 Elementen:

x = letzte Kombi y = x and (x xor (x-1)) addiert nachgeflickt
1111 0001 10000 10111
10111 00001 11000 11011
11011 00001 11100 11101
11101 00001 11110 nicht nötig
11110 00010 100000 100111
...

(Alles nicht nachgerechnet und nicht getestet, aber die Idee stimmt.)

--
Helmut Richter
Ralf Goertz
2018-08-25 09:22:08 UTC
Antworten
Permalink
Raw Message
Am Fri, 24 Aug 2018 19:53:46 +0200
Post by Detlef Müller
Post by Ralf Goertz
Am Fri, 24 Aug 2018 10:31:24 +0200
[...]
Post by Ralf Goertz
Post by Detlef Müller
A(L, n): (L=Liste der Objekte, n=Anzahl der Schachteln)
- L sei die Menge {o_1, ..., o_{n*m}} von zu verteilenden Objekten.
- Das kleinste Objekt o_1 aus L kommt in die Schachtel S.
- Für jede Ergänzung S=[o_1, r_2, ..., r_m] mit verschiedenen
- Füge S an die Ausgabezeile an.
- merke die aktuelle Ausgabezeile (=Lösungskombination).
- entferne S wieder aus der Ausgabezeile.
- return.
- Rufe A(L ohne S, n-1) auf.
- entferne S wieder aus der Ausgabezeile.
- return.
[...]
Post by Ralf Goertz
Jetzt habe ich nachgedacht (und programmiert), und auch wenn ich
den Weg nach wie vor elegant finde, werden leider alle
Permutationen der Sets gefunden. Habe das dann mit set repariert,
was automatisch die Dubletten wegwirft. Hier trotzdem das Programm
Leider kann ich C++ und die Bibliotheken nicht gut genug, um da
mitreden zu können.
Bordmittel aus Bibliotheken sollten effizient und nach "state of the
art" programmiert sein und gewöhnlich besser als eigen-gefruckel (von
den Grauen Haaren, die einem rekursive programme bescheren können ganz
abzusehen).
Das sind in dem Sinne keine Bibliotheken. Das ist Standard C++, das mit
jedem c++ compiler, der den Standard von 2011 beherrscht, übersetzt
werden kann. Es müsste also auch bei online Compilern funktionieren. Ich
glaube, die next_permutation() Funktion beruht auf TAOCP von Knuth, habe
es aber nicht gecheckt.
Post by Detlef Müller
Allerdings bei 3 Teilmengen a 5 Elementen sind 126126 Möglichkeiten
durch zu iterieren - wenn man da erst mal alle Permutationen von 15
Elementen durchgeht, sind das 1307674368000 Möglichkeiten, aus denen
dann gesiebt werden muss ... selbst wenn die Bibliotheksfunktion die
in O(1) ausspuckt, wird das kritisch.
Hier zunächst ein Ausschnitt mit Output:

( 0 4 8 12 14 )( 1 5 6 9 13 )( 2 3 7 10 11 )
( 0 4 8 12 14 )( 1 5 6 10 11 )( 2 3 7 9 13 )
( 0 4 8 12 14 )( 1 5 6 10 13 )( 2 3 7 9 11 )
( 0 4 8 12 14 )( 1 5 6 11 13 )( 2 3 7 9 10 )
( 0 4 8 12 14 )( 1 5 7 9 10 )( 2 3 6 11 13 )
( 0 4 8 12 14 )( 1 5 7 9 11 )( 2 3 6 10 13 )
( 0 4 8 12 14 )( 1 5 7 9 13 )( 2 3 6 10 11 )
( 0 4 8 12 14 )( 1 5 7 10 11 )( 2 3 6 9 13 )
( 0 4 8 12 14 )( 1 5 7 10 13 )( 2 3 6 9 11 )
( 0 4 8 12 14 )( 1 5 7 11 13 )( 2 3 6 9 10 )
( 0 4 8 12 14 )( 1 5 9 10 11 )( 2 3 6 7 13 )
( 0 4 8 12 14 )( 1 5 9 10 13 )( 2 3 6 7 11 )
( 0 4 8 12 14 )( 1 5 9 11 13 )( 2 3 6 7 10 )
( 0 4 8 12 14 )( 1 5 10 11 13 )( 2 3 6 7 9 )
( 0 4 8 12 14 )( 1 6 7 9 10 )( 2 3 5 11 13 )
( 0 4 8 12 14 )( 1 6 7 9 11 )( 2 3 5 10 13 )
( 0 4 8 12 14 )( 1 6 7 9 13 )( ^C

Dann habe ich mir nur die Größe des res Sets anzeigen lassen. Statt der
Schleife ab

for (auto i:res) {

einfach

cout<<"there are "<<res.size()<<" partitions"<<endl;

Hier der Output mit "time":

***@home:~/c> time ./design
there are 126126 partitions

real 0m0.397s
user 0m0.369s
sys 0m0.028s

Also nicht einmal eine halbe Sekunde…
Detlef Müller
2018-08-25 11:23:55 UTC
Antworten
Permalink
Raw Message
Post by Ralf Goertz
Am Fri, 24 Aug 2018 19:53:46 +0200
Post by Detlef Müller
Post by Ralf Goertz
Am Fri, 24 Aug 2018 10:31:24 +0200
[...]
Post by Ralf Goertz
Post by Detlef Müller
Post by Ralf Goertz
Jetzt habe ich nachgedacht (und programmiert),
[...]
Post by Ralf Goertz
Post by Detlef Müller
Leider kann ich C++ und die Bibliotheken nicht gut genug, um da
mitreden zu können.
Bordmittel aus Bibliotheken sollten effizient und nach "state of the
art" programmiert sein
[...]
Post by Ralf Goertz
Das sind in dem Sinne keine Bibliotheken. Das ist Standard C++, das mit
jedem c++ compiler, der den Standard von 2011 beherrscht, übersetzt
werden kann. Es müsste also auch bei online Compilern funktionieren. Ich
glaube, die next_permutation() Funktion beruht auf TAOCP von Knuth, habe
es aber nicht gecheckt.
Da das Programm auch für mein Beispiel so fix war, habe ich mich
doch noch mal darin vertieft (und dabei ein paar Fragmente von
C++ gelernt) ...

Ich denke mal, next_permutation() vermeidet wirklich Dubletten.
Wenn ich das richtig verstanden habe, verteilt Dein Algorithmus
via next_permutation die "Kasten-Nummern" auf die Objekte (was
ich auch elegant finde), also z.B.

0,1,2,3,4,5 <- Objekte
0,2,1,0,1,2 <- Permutation der "Kasten-Nummern"

führt auf (0,3),(2,4) und (1,5) als zugehörige Mengen-Kombination.

Wenn jetzt die Kasten-Nummern permutiert werden, z.B. Kasten 1 und
zwei vertauscht, erhalten wir

0,1,2,3,4,5 <- Objekte
0,1,2,0,2,1 <- Permutation der "Kasten-Nummern"

führt auf die Mengen-Kombinatiton (0,3),(1,5) und (2,4),
also die entsprechende Permutation der ursprünglichen
Mengenkombination, was für die Mehrfach-Findungen
verantwortlich sein dürfte.
Bei drei Kästen ist der "Overhead" dann 3!=6, also noch
nicht dramatisch.

Wenn man nun dafür sorgt, daß nur die lexikografisch sortierten
Permutationen der Kasten-Nummern durchlaufen werden, landen wir
wohl bei Helmuts Vorschlag.

[...]
Post by Ralf Goertz
( 0 4 8 12 14 )( 1 5 6 9 13 )( 2 3 7 10 11 )
( 0 4 8 12 14 )( 1 5 6 10 11 )( 2 3 7 9 13 )
( 0 4 8 12 14 )( 1 5 6 10 13 )( 2 3 7 9 11 )
( 0 4 8 12 14 )( 1 5 6 11 13 )( 2 3 7 9 10 )
( 0 4 8 12 14 )( 1 5 7 9 10 )( 2 3 6 11 13 )
( 0 4 8 12 14 )( 1 5 7 9 11 )( 2 3 6 10 13 )
( 0 4 8 12 14 )( 1 5 7 9 13 )( 2 3 6 10 11 )
( 0 4 8 12 14 )( 1 5 7 10 11 )( 2 3 6 9 13 )
( 0 4 8 12 14 )( 1 5 7 10 13 )( 2 3 6 9 11 )
( 0 4 8 12 14 )( 1 5 7 11 13 )( 2 3 6 9 10 )
( 0 4 8 12 14 )( 1 5 9 10 11 )( 2 3 6 7 13 )
( 0 4 8 12 14 )( 1 5 9 10 13 )( 2 3 6 7 11 )
( 0 4 8 12 14 )( 1 5 9 11 13 )( 2 3 6 7 10 )
( 0 4 8 12 14 )( 1 5 10 11 13 )( 2 3 6 7 9 )
( 0 4 8 12 14 )( 1 6 7 9 10 )( 2 3 5 11 13 )
( 0 4 8 12 14 )( 1 6 7 9 11 )( 2 3 5 10 13 )
( 0 4 8 12 14 )( 1 6 7 9 13 )( ^C
Dann habe ich mir nur die Größe des res Sets anzeigen lassen. Statt der
Schleife ab
for (auto i:res) {
einfach
cout<<"there are "<<res.size()<<" partitions"<<endl;
there are 126126 partitions
real 0m0.397s
user 0m0.369s
sys 0m0.028s
Also nicht einmal eine halbe Sekunde…
In der Tat - wenn Du nicht einen Monster-Rechner hast, dürfte das
zeigen, daß "next_permutation" nicht 15! Möglichkeiten durchläuft.

Gruß,
Detlef
--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de
Ralf Goertz
2018-08-25 12:27:26 UTC
Antworten
Permalink
Raw Message
Am Sat, 25 Aug 2018 13:23:55 +0200
Post by Detlef Müller
[...]
Post by Ralf Goertz
Das sind in dem Sinne keine Bibliotheken. Das ist Standard C++, das
mit jedem c++ compiler, der den Standard von 2011 beherrscht,
übersetzt werden kann. Es müsste also auch bei online Compilern
funktionieren. Ich glaube, die next_permutation() Funktion beruht
auf TAOCP von Knuth, habe es aber nicht gecheckt.
Da das Programm auch für mein Beispiel so fix war, habe ich mich
doch noch mal darin vertieft (und dabei ein paar Fragmente von
C++ gelernt) ...
Das lohnt sich auch. Man mit dem, was der Standard bietet, schon
unheimlich viel anfangen.
Post by Detlef Müller
Ich denke mal, next_permutation() vermeidet wirklich Dubletten.
Oh, das auf jeden Fall:


#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
vector<int> v={{0,0,1,1}};
do {
for (auto i:v) cout<<i<<" ";
cout<<endl;
} while (next_permutation(v.begin(),v.end()));
}


output:

0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
Post by Detlef Müller
Wenn ich das richtig verstanden habe, verteilt Dein Algorithmus via
next_permutation die "Kasten-Nummern" auf die Objekte (was ich auch
elegant finde), also z.B.
0,1,2,3,4,5 <- Objekte
0,2,1,0,1,2 <- Permutation der "Kasten-Nummern"
führt auf (0,3),(2,4) und (1,5) als zugehörige Mengen-Kombination.
Wenn jetzt die Kasten-Nummern permutiert werden, z.B. Kasten 1 und
zwei vertauscht, erhalten wir
0,1,2,3,4,5 <- Objekte
0,1,2,0,2,1 <- Permutation der "Kasten-Nummern"
führt auf die Mengen-Kombinatiton (0,3),(1,5) und (2,4),
also die entsprechende Permutation der ursprünglichen
Mengenkombination, was für die Mehrfach-Findungen
verantwortlich sein dürfte.
Bei drei Kästen ist der "Overhead" dann 3!=6, also noch nicht
dramatisch.
Korrekt, so läuft das. Wobei ich nur (n-1) Permutationen der
Kastennummern durchlaufe, weil ich next_permutation() von begin()+1 habe
loslaufen lassen, so dass die 0 immer im ersten Kasten bleibt. Deshalb
habe ich im ersten Moment, als ich mit 2*3 das Programm gecheckt hatte,
gedacht, es würde ohne Dubletten laufen.
Post by Detlef Müller
Wenn man nun dafür sorgt, daß nur die lexikografisch sortierten
Permutationen der Kasten-Nummern durchlaufen werden, landen wir
wohl bei Helmuts Vorschlag.
Das ist aber leider nicht mehr so einfach möglich mit meinem Ansatz,
fürchte ich…
Post by Detlef Müller
Post by Ralf Goertz
there are 126126 partitions
real 0m0.397s
user 0m0.369s
sys 0m0.028s
Also nicht einmal eine halbe Sekunde…
In der Tat - wenn Du nicht einen Monster-Rechner hast, dürfte das
zeigen, daß "next_permutation" nicht 15! Möglichkeiten durchläuft.
Nein, mein Rechner ist ein 3 oder vier Jahre alter Laptop der (damals)
mittleren Preisklasse.

Ralf
Ralf Goertz
2018-08-26 09:03:22 UTC
Antworten
Permalink
Raw Message
Am Sat, 25 Aug 2018 14:27:26 +0200
Post by Ralf Goertz
Am Sat, 25 Aug 2018 13:23:55 +0200
Post by Detlef Müller
Wenn ich das richtig verstanden habe, verteilt Dein Algorithmus via
next_permutation die "Kasten-Nummern" auf die Objekte (was ich auch
elegant finde), also z.B.
0,1,2,3,4,5 <- Objekte
0,2,1,0,1,2 <- Permutation der "Kasten-Nummern"
führt auf (0,3),(2,4) und (1,5) als zugehörige Mengen-Kombination.
Wenn jetzt die Kasten-Nummern permutiert werden, z.B. Kasten 1 und
zwei vertauscht, erhalten wir
0,1,2,3,4,5 <- Objekte
0,1,2,0,2,1 <- Permutation der "Kasten-Nummern"
führt auf die Mengen-Kombinatiton (0,3),(1,5) und (2,4),
also die entsprechende Permutation der ursprünglichen
Mengenkombination, was für die Mehrfach-Findungen
verantwortlich sein dürfte.
Bei drei Kästen ist der "Overhead" dann 3!=6, also noch nicht
dramatisch.
Korrekt, so läuft das. Wobei ich nur (n-1) Permutationen der
Kastennummern durchlaufe, weil ich next_permutation() von begin()+1
habe loslaufen lassen, so dass die 0 immer im ersten Kasten bleibt.
Deshalb habe ich im ersten Moment, als ich mit 2*3 das Programm
gecheckt hatte, gedacht, es würde ohne Dubletten laufen.
Post by Detlef Müller
Wenn man nun dafür sorgt, daß nur die lexikografisch sortierten
Permutationen der Kasten-Nummern durchlaufen werden, landen wir
wohl bei Helmuts Vorschlag.
Das ist aber leider nicht mehr so einfach möglich mit meinem Ansatz,
fürchte ich…
Da ja bekannt ist, wie viele Partitionen es insgesamt gibt (nämlich
(n*m)!/(n!*m!^n)), ist es kein Problem (außer vielleicht die Berechnung,
weil die Zwischenergebnisse einen Overflow erzeugen könnten)
mitzuzählen, wie viele man schon hat und bei Erreichen dieser Zahl
abzubrechen. Bei meinem Programm bin ich mit 3*5 so noch eine Zehntel
Sekunde (also etwa 25%) schneller. Dabei habe ich 36036 Dubletten
erzeugt (res.insert() gibt mir zurück, ob das entsprechende Element
schon enthalten war). Das sind etwa 5% Prozent der 630630 insgesamt
vorhandenen.

Interessanter wird es bei 5*3, da dann wesentlich mehr Dubletten zu
erwarten sind. Anzahl Partitionen: 1401400, Dubletten bei Erreichen
dieser Zahl: 6868400, Dubletten insgesamt: 166766600. Also sogar nur
etwas mehr als 4% Dubletten bei vorzeitigem Abbruch. Das schlägt sich
sogar noch dramtischer in der Laufzeit nieder: mit Abbruch 16 Sekunden,
ohne 307 Sekunden.

Aber man sieht, dass bei vielen Teilmengen mit wenig Elementen mein
Programm die meiste Zeit Dubletten erzeugt. :-(

Ralf
Detlef Müller
2018-08-26 11:07:15 UTC
Antworten
Permalink
Raw Message
Post by Ralf Goertz
Am Sat, 25 Aug 2018 14:27:26 +0200
[...]
Post by Ralf Goertz
Post by Ralf Goertz
Post by Detlef Müller
Wenn man nun dafür sorgt, daß nur die lexikografisch sortierten
Permutationen der Kasten-Nummern durchlaufen werden, landen wir
wohl bei Helmuts Vorschlag.
Das ist aber leider nicht mehr so einfach möglich mit meinem Ansatz,
fürchte ich…
Da ja bekannt ist, wie viele Partitionen es insgesamt gibt (nämlich
(n*m)!/(n!*m!^n)), ist es kein Problem (außer vielleicht die Berechnung,
weil die Zwischenergebnisse einen Overflow erzeugen könnten)
mitzuzählen, wie viele man schon hat und bei Erreichen dieser Zahl
abzubrechen. Bei meinem Programm bin ich mit 3*5 so noch eine Zehntel
Sekunde (also etwa 25%) schneller. Dabei habe ich 36036 Dubletten
erzeugt (res.insert() gibt mir zurück, ob das entsprechende Element
schon enthalten war). Das sind etwa 5% Prozent der 630630 insgesamt
vorhandenen.
Nur 5%, das hat mich erst gewundert - aber klar: Die
Permutationen werden ja lexikographisch durchwandert ...
da fragt man sich eher wo die "Ausreißer" her kommen, ich hatte
ja ganz kühn behauptet, wenn die "Permutationen" von 000111222
lexikografisch sortiert wären, würde das nicht passieren
und dafür sollte next_permutation ja eigentlich sorgen.

Gruß,
Detlef
Post by Ralf Goertz
Ralf
--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de
Ralf Goertz
2018-08-26 12:31:05 UTC
Antworten
Permalink
Raw Message
Am Sun, 26 Aug 2018 13:07:15 +0200
Post by Detlef Müller
Post by Ralf Goertz
Am Sat, 25 Aug 2018 14:27:26 +0200
[...]
Post by Ralf Goertz
Da ja bekannt ist, wie viele Partitionen es insgesamt gibt (nämlich
(n*m)!/(n!*m!^n)), ist es kein Problem (außer vielleicht die
Berechnung, weil die Zwischenergebnisse einen Overflow erzeugen
könnten) mitzuzählen, wie viele man schon hat und bei Erreichen
dieser Zahl abzubrechen. Bei meinem Programm bin ich mit 3*5 so
noch eine Zehntel Sekunde (also etwa 25%) schneller. Dabei habe ich
36036 Dubletten erzeugt (res.insert() gibt mir zurück, ob das
entsprechende Element schon enthalten war). Das sind etwa 5%
Prozent der 630630 insgesamt vorhandenen.
Nur 5%, das hat mich erst gewundert - aber klar: Die
Permutationen werden ja lexikographisch durchwandert ...
da fragt man sich eher wo die "Ausreißer" her kommen, ich hatte
ja ganz kühn behauptet, wenn die "Permutationen" von 000111222
lexikografisch sortiert wären, würde das nicht passieren
und dafür sollte next_permutation ja eigentlich sorgen.
Ja, ich hatte eigentlich gehofft, dass überhaupt keine Dubletten
auftauchen würden bis zum vollen Satz. Aber die erste Dublette (bei 3*5)
ist

( 0 1 2 3 4 )( 6 7 8 9 10 )( 5 11 12 13 14 )

Die kommt lexikografisch natürlich nach

( 0 1 2 3 4 )( 5 11 12 13 14 )( 6 7 8 9 10 )

Es ist aber noch keine Partition mit 7 als kleinstem Element in der
zweiten Teilmenge gekommen (glaube ich jetzt mal).

Allerdings kann man meine Idee vielleicht doch dublettenfrei ausbauen.
Und zwar indem man für jede Teilmenge eine eigene Permutationsrunde
einbaut (jetzt wieder am Beispiel 2*3):

Für die erste Menge lassen wir (-1 -1 0 0 0 0) durch next_permutation
wandern. Die -1 zeigt an, dass die entsprechende Position in der Menge
ist. (-1, weil das kleiner als 0 ist, man könnte auch mit 1 und
prev_permutation arbeiten.) Für die zweite Menge nehmen wir (-1 -1 0 0).
Dabei sind die beiden Elemente aus der ersten Teilmenge nicht mehr
enthalten. Wir müssen bei der Positionsbestimmung die aber natürlich
berücksichten. next_permutation läuft aber immer von begin()+1 los, so
dass die -1 jeweils immer an der ersten Position bleibt. Damit stellen
wir sicher, dass die Mengen der Größe nach geordnet sind. Haben wir also
zum Beispiel

(-1 0 -1 0 0 0) und (-1 0 0 -1)

dann bedeutet das

(0 2) und (1 5)

Die dritte Menge ist dann schon das Komplement der Vereinigung der
ersten beiden. Die erste Runde next_permutation wird fünfmal
durchlaufen, die zweite, darin geschachtelt, dreimal. Damit hätte man
die 15 Partitionen. Der Vorteil ist nicht nur die Vermeidung von
Dubletten sondern auch die Speichererparnis. Mein Rechner hätte nämlich
von der Zeit her locker auch größere m und n zugelassen, allerdings
kostet das Speichern im set<set<vector<int>>> dann sehr schnell sehr
viel Platz und zwingt den Computer in die Knie. Und der Algorithmus
lässt sich leicht nichtrekursiv programmieren, denke ich. Vielleicht
probiere ich es nachher mal.
Ralf Goertz
2018-08-28 10:11:10 UTC
Antworten
Permalink
Raw Message
Am Sun, 26 Aug 2018 14:31:05 +0200
Post by Ralf Goertz
Allerdings kann man meine Idee vielleicht doch dublettenfrei ausbauen.
Und zwar indem man für jede Teilmenge eine eigene Permutationsrunde
Korrektur 3*2
Post by Ralf Goertz
Für die erste Menge lassen wir (-1 -1 0 0 0 0) durch next_permutation
wandern. Die -1 zeigt an, dass die entsprechende Position in der Menge
ist. (-1, weil das kleiner als 0 ist, man könnte auch mit 1 und
prev_permutation arbeiten.) Für die zweite Menge nehmen wir (-1 -1 0
0). Dabei sind die beiden Elemente aus der ersten Teilmenge nicht mehr
enthalten. Wir müssen bei der Positionsbestimmung die aber natürlich
berücksichten. next_permutation läuft aber immer von begin()+1 los, so
dass die -1 jeweils immer an der ersten Position bleibt. Damit stellen
wir sicher, dass die Mengen der Größe nach geordnet sind. Haben wir
also zum Beispiel
(-1 0 -1 0 0 0) und (-1 0 0 -1)
dann bedeutet das
(0 2) und (1 5)
Die dritte Menge ist dann schon das Komplement der Vereinigung der
ersten beiden. Die erste Runde next_permutation wird fünfmal
durchlaufen, die zweite, darin geschachtelt, dreimal. Damit hätte man
die 15 Partitionen. Der Vorteil ist nicht nur die Vermeidung von
Dubletten sondern auch die Speichererparnis. Mein Rechner hätte
nämlich von der Zeit her locker auch größere m und n zugelassen,
allerdings kostet das Speichern im set<set<vector<int>>> dann sehr
schnell sehr viel Platz und zwingt den Computer in die Knie. Und der
Algorithmus lässt sich leicht nichtrekursiv programmieren, denke ich.
Vielleicht probiere ich es nachher mal.
Ich habe das jetzt gemacht. Alllerdings doch rekursiv. Bin aber um
Größenordnungen schneller als mit der vorherigen Variante (3*5):

***@home:~/c> time ./design1
There are 126126 partitions

real 0m0.044s
user 0m0.043s
sys 0m0.001s

(Natürlich ohne output). Für 4*5 erhalte ich

There are 488864376 partitions

real 1m25.758s
user 1m25.373s
sys 0m0.033s

Der Output von 3*2 ist folgender. Es kommt immer zuerst der
partitioner, das sind die Vektoren, die prev_permution durchlaufen und
danach das Ergebnis (partionee):

(1 1 0 0 0 0)(1 1 0 0)(1 1)
(0 1)(2 3)(4 5)
(1 1 0 0 0 0)(1 0 1 0)(1 1)
(0 1)(2 4)(3 5)
(1 1 0 0 0 0)(1 0 0 1)(1 1)
(0 1)(2 5)(3 4)
(1 0 1 0 0 0)(1 1 0 0)(1 1)
(0 2)(1 3)(4 5)
(1 0 1 0 0 0)(1 0 1 0)(1 1)
(0 2)(1 4)(3 5)
(1 0 1 0 0 0)(1 0 0 1)(1 1)
(0 2)(1 5)(3 4)
(1 0 0 1 0 0)(1 1 0 0)(1 1)
(0 3)(1 2)(4 5)
(1 0 0 1 0 0)(1 0 1 0)(1 1)
(0 3)(1 4)(2 5)
(1 0 0 1 0 0)(1 0 0 1)(1 1)
(0 3)(1 5)(2 4)
(1 0 0 0 1 0)(1 1 0 0)(1 1)
(0 4)(1 2)(3 5)
(1 0 0 0 1 0)(1 0 1 0)(1 1)
(0 4)(1 3)(2 5)
(1 0 0 0 1 0)(1 0 0 1)(1 1)
(0 4)(1 5)(2 3)
(1 0 0 0 0 1)(1 1 0 0)(1 1)
(0 5)(1 2)(3 4)
(1 0 0 0 0 1)(1 0 1 0)(1 1)
(0 5)(1 3)(2 4)
(1 0 0 0 0 1)(1 0 0 1)(1 1)
(0 5)(1 4)(2 3)


Keine Ahnung, ob das jetzt äquivalent zu Helmuts Vorgehen ist. Das ist
zwar auch elegant, aber für mich nicht so intuitiv.

Hier das Programm:


#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

ostream & operator<<(ostream & os,vector<int> &v) { //für leichte Ausgabe
for (auto i=0;i<v.size();++i)
cout<<(i ? " ":"(")<<v[i];
cout<<")";
return os;
}

ostream & operator<<(ostream & os,vector<vector<int>> &v) { //dito
for (auto i=0;i<v.size();++i)
cout<<v[i];
cout<<"\n";
return os;
}

struct list_all {
const int n,m;
vector<vector<int>> p; //the partitioner
vector<vector<int>> part; //the partitionee
vector<int> pos;
int res;
void do_it(int level) { //die Rekursion
if (level<n) {
do {
do_it(level+1);
} while (prev_permutation(p[level].begin()+1,p[level].end()));
} else {
fill(pos.begin(),pos.end(),0);
for(int i=0;i<n;++i) {
int j=0;
auto it=part[i].begin();
for (int k=0;k<p[i].size();++k) {
while (pos[j]) ++j;
if (p[i][k]) {
*it++=j;
pos[j]=1;
}
++j;
}
}
cout<<p;
cout<<part;
++res;
}
}
list_all(int n_, int m_) : n(n_),m(m_),p(n),part(n,vector<int>(m)),pos(n_*m_),res(0){
if (n<2 || m<2) {
cerr<<"m and n should both be at least 2\n";
return;
}
auto s(m*n); //size of vector<vector<int>>[i]
for (int i=0;i<n;++i) {
p[i]=vector<int>(s);
fill_n(p[i].begin(),m,1);
s-=m;
}
do_it(0);
cout<<"There are "<<res<<" partitions\n";
}
};

int main() {
list_all(3,2);
}
IV
2018-08-29 16:20:06 UTC
Antworten
Permalink
Raw Message
Post by Ralf Goertz
Ich habe das jetzt gemacht. Alllerdings doch rekursiv. Bin aber um
Größenordnungen schneller als mit der vorherigen Variante (3*5)
Kannst Du mir Bescheid geben, wenn Dein Programm fertig und korrekt ist?
Dann könnten wir, nach Überprüfung durch Andere vielleicht Anzahlfolgen für
einige Typen von Designs an OEIS (oeis.org) melden, die fehlen da nämlich.
Ralf Goertz
2018-08-30 07:57:56 UTC
Antworten
Permalink
Raw Message
Am Wed, 29 Aug 2018 18:20:06 +0200
Post by IV
Post by Ralf Goertz
Ich habe das jetzt gemacht. Alllerdings doch rekursiv. Bin aber um
Größenordnungen schneller als mit der vorherigen Variante (3*5)
Kannst Du mir Bescheid geben, wenn Dein Programm fertig und korrekt
ist? Dann könnten wir, nach Überprüfung durch Andere vielleicht
Anzahlfolgen für einige Typen von Designs an OEIS (oeis.org) melden,
die fehlen da nämlich.
Das Programm ist doch fertig und abgedruckt. Aber für die Anzahlen
braucht man es nicht, den Funktionsterm (sic!) dafür habe ich doch schon
angegeben: (n*m)!/(n!*m!^n). Der erklärt sich folgendermaßen. Es gibt
insgesamt (n*m)! Permutationen von n*m Elementen. Diese werden in n
Teilmengen der Größe m zusammengefasst. Da die Reihenfolge der
Teilmengen irrelevant ist, muss durch die Zahl n! der Permutation dieser
Teilmengen dividiert werden. Zusätzlich können innerhalb jeder Teilmenge
die jeweils m Elemente permutiert werden (also m!), ohne dass sich
dadurch etwas ändert und zwar in allen n Teilmengen unabhängig
voneinander, daher der Exponent n.

PS OT: Könntest du bitte deine Antworten auf Zitate durch eine Leerzeile
trennen. Das erleichert das Lesen ungemein, besonders, wenn man keinen
Programm benutzt, dass die verschiedenen Zitatebenen unterschiedlich
einfärbt. Mein Programm kann das zwar, aber bei manchen Schreibern
kommen die Ebenen durcheinander, was sich dann leicht identifizieren
lässt, weil eben keine Leerzeile dazwischen ist. Ich meine sogar bemerkt
zu haben, dass du in Zitaten die Leerzeilen weggelöscht hast. Das ist
kein guter Stil, weil die wie gesagt meistens absichtlich gesetzt
wurden.
IV
2018-09-02 19:55:38 UTC
Antworten
Permalink
Raw Message
Post by Ralf Goertz
(n*m)!/(n!*m!^n).
Dieser Term gibt die Anzahl der Partitionen einer n*m-Menge in m-Mengen an
(Mengenpartitionen).
Demnach kannst Du auch nach veröffentlichten effektiven Algrithmen für
diese Art kombinatorische Objekte suchen.
Ralf Goertz
2018-09-04 07:11:34 UTC
Antworten
Permalink
Raw Message
Am Sun, 2 Sep 2018 21:55:38 +0200
Post by IV
Post by Ralf Goertz
(n*m)!/(n!*m!^n).
Dieser Term gibt die Anzahl der Partitionen einer n*m-Menge in
m-Mengen an (Mengenpartitionen).
Das weiß ich, habe ich ja schließlich selbst erklärt.
Post by IV
Demnach kannst Du auch nach veröffentlichten effektiven Algrithmen
für diese Art kombinatorische Objekte suchen.
Warum sollte ich? Ich brauche diese Objekte nicht sondern Stefan, der
damit etwas über Designs machen will. Mein Interesse war, einen Hinweis
auf einen Trick zu geben, den ich oft benutze, wenn ich selbst alle auf
bestimmte Art definierte Teilmengen einer Menge zu durchlaufen habe.

PS: Du entfernst immer noch Leerzeilen in Zitaten
Helmut Richter
2018-09-02 07:54:38 UTC
Antworten
Permalink
Raw Message
Post by Ralf Goertz
Post by Ralf Goertz
Die dritte Menge ist dann schon das Komplement der Vereinigung der
ersten beiden. Die erste Runde next_permutation wird fünfmal
durchlaufen, die zweite, darin geschachtelt, dreimal. Damit hätte man
die 15 Partitionen. Der Vorteil ist nicht nur die Vermeidung von
Dubletten sondern auch die Speichererparnis. Mein Rechner hätte
nämlich von der Zeit her locker auch größere m und n zugelassen,
allerdings kostet das Speichern im set<set<vector<int>>> dann sehr
schnell sehr viel Platz und zwingt den Computer in die Knie. Und der
Algorithmus lässt sich leicht nichtrekursiv programmieren, denke ich.
Vielleicht probiere ich es nachher mal.
Ich habe das jetzt gemacht. Alllerdings doch rekursiv. Bin aber um
Ich habs nicht bleiben lassen können, meinen Algorithmus auch mal zu
programmieren, allerdings ohne *jede* Rücksicht auf Effizienz, sondern
erst mal, ob so geht (heißt heute wohl proof of concept), noch dazu in
Perl, was bei solchen Anwendungen (bloß rechnen, nichts denken)
Größenordnungen an Rechenzeit kostet. Dazu unten mehr.

Allerdings Speicherprobleme habe ich keine: man braucht nur den Platz
für den Stack bei der Rekursion, das sind 2 Integers pro Niveau Tiefe.

Die Rekursivität kann übrigens durchaus Zeit sparen. Ich halte
momentan die Nichtrekursivität bei mir für eines der möglichen
Effizienzprobleme.
Post by Ralf Goertz
There are 126126 partitions
real 0m0.044s
user 0m0.043s
sys 0m0.001s
Das sind bei mir 9,3 sec, also Faktor 217.
Post by Ralf Goertz
(Natürlich ohne output). Für 4*5 erhalte ich
There are 488864376 partitions
real 1m25.758s
user 1m25.373s
sys 0m0.033s
Das sind bei mir 10 h, also Faktor 416.

Die Faktoren sehen wild aus, sind aber Interpretation vs. Compilation
sowie ausgiebigen Laufzeitchecks geschuldet. Ich möchte das Ding mal
nach C übersetzen, was nicht so viel Arbeit ist, weil die Sachen, die
Perl besser kann, gar nicht vorkommen. Nur habe ich leider sehr wenig
Ahnung von C, auch wenn ich das eine oder andere Progrämmelchen
geschrieben habe. Aber was man machen muss, um aus einem in C
geschriebenen Algorithmus ein komplettes lauffähiges Programm zu
machen und welche Compileroptionen es gibt, da bin ich blank.
Post by Ralf Goertz
Keine Ahnung, ob das jetzt äquivalent zu Helmuts Vorgehen ist. Das
ist zwar auch elegant, aber für mich nicht so intuitiv.
Ich habe es nur sehr knapp beschrieben – so schrecklich unintuitiv ist
es meiner Ansicht nach nicht. Ich hänge eine kommentierte Version an.

Mein Anliegen war:

a) Der Algorithmus soll die Lösungen produzieren, die gesucht werden,
und nicht eine Obermenge und dann die überflüssigen wegschmeißen.
Dass immer von Permutationen (also viel mehr als Kombinationen) und
Dubletten (die solls gar nicht geben) die Rede war, hat mich
alarmiert. Ob zu Recht, weiß ich nicht, so genau habe ich in die
hier veröffentlichten Algorithmen nicht hineingesehen.

b) Wenn man eine Kombination als ganze Zahl darstellt – jedes mögliche
Element 1 Bit –, dann ist es eine billige Operation, mit ein paar
Booleschen und arithmetischen Operationen die nächste Kombination
zu finden. Neu seit dem letzten Mal ist, dass es nicht teurer wird,
auch noch eine Maske von Bits dazu anzugeben, die auf jeden Fall
vorkommen müssen. Geht billig nur bis zur Wortlänge von Integers,
aber da sind wir bis jetzt ja erst bei 20.

Jetzt, wo ich schon angefangen habe, mache ich auch noch ein wenig
weiter. Mein Plan:

1. Schauen, ob die Einführung von Rekursion was bringt oder was
kostet. Es gibt dann gar keine Arrays mehr, nur noch einfache
Variable, die allerdings im Aufrufstack gestapelt werden. Keine
Ahnung, wie viel ich da ändern muss – vermutlich nicht allzu viel,
aber doch mit der Chance auf viele neue Fehler.

2. Die bessere (klarere?, schnellere?) der beiden Versionen von Hand in
C übersetzen und dann einen realistischeren Laufzeitvergleich
machen. Da könnte ich Hilfe brauchen, weil ich, wie oben erwähnt,
für C-Programme keinen Blick habe.

Die jetzige Form des Programms steht in
http://hhr-m.userweb.mwn.de/tmp/combipart.txt

Ohne die Unterprogramme zur Ausgabe von Ergebnissen sieht das so aus:

#! /usr/bin/perl

use strict;

# ========================================================================
# Unterprogramme zur Manipulation einer einzelnen Menge
# Die Menge {a1, ..., an} wird dabei als Zahl 2^a1+...+2^an dargestelt
# ========================================================================

my $nsol = multi_comb (20, 5, 0);
print "$nsol\n";

sub lastbit {
my ($x) = @_;

# die Menge, die nur das kleinste Element von x enthält

return $x & ($x ^ ($x-1));
};

sub popcount {
my ($x) = @_;

# Mächtigkeit von x (für alte CDC-Freaks: "population count")

my $res = 0;
while ($x) {
$res++;
$x = $x ^ lastbit($x);
};
return $res;
};

sub fill {
my ($x, $n, $k) = @_;

# die um die k kleinsten bisher nicht enthaltenen (Noch-nicht-)Elemente erweiterte Menge x
# n ist dabei die maximale Größe von Mengen
# Ergebnis < 0 falls nicht möglich

my $full = (1 << $n) - 1; # alle überhaupt je vorkommenden Elemente
return -1 if $x > $full; # x enthält unmögliche Elemente
return $x unless $k; # nichts hinzufügen
my $cand = $full ^ $x; # Menge der möglicherweise hinzukommenden Elemente

for (my $i=1; $i<=$k; $i++) {
return -2 unless $cand; # nicht genug Kandidaten
my $c = lastbit($cand); # zu verschiebendes Bit
$cand ^= $c; # aus cand entfernen
$x ^= $c; # zu x hinzufügen
};

return $x;
};

sub advance {
my ($x, $n, $mask) = @_;

# x ist eine Menge, die mask als Untermenge enthält
# Das Ergebnis ist die lexikografisch nächste Menge, die gleichmächtig mit x ist
# und ebenfalls mask als Untermenge enthält
# n ist dabei die maximale Größe von Mengen
# Ergebnis < 0 falls nicht möglich

my $full = (1 << $n) - 1; # alle überhaupt je vorkommenden Elemente
return -1 if $x > $full; # x enthält unmögliche Elemente
return -3 if ($x | $mask) != $x; # Bedingung für x nicht erfüllt

my $rest = $x ^ $mask; # Bits ohne mask
my $nrest = popcount($rest); # Anzahl Bits ohne mask

$x += lastbit($rest); # so viel müssen wir mindestens addieren
$x |= $mask; # die Bits von mask wieder hinzufügen

$nrest -= popcount($x ^ $mask); # soviele Bits fehlen noch

return $x unless $nrest; # nichts fehlt mehr
return fill($x, $n, $nrest); # Rest auffüllen
};

# ========================================================================
# Algorithmus zur Lösung der Aufgabe
# ========================================================================

sub multi_comb {
my ($n, $k, $output) = @_;

# Es werden alle Möglichkeiten gesucht, aus n Elementen soviele
# disjunkte Kombinationen von je k Elementen wie möglich auszuwählen.
# Vorläufig ist die Lösung nur komplett, wenn k Teiler von n ist.
# Ergebnis ist die Anzahl der Lösungen
# Falls $output gesetzt ist, werden die Lösungen ausgegeben

my ($new_comb, $mask, $success, $nsol);
my @stack = (0); # bis jetzt die leere Menge
my @mask = (1); # obligatorisch in der nächsten Kombination

while (1) {
$new_comb = fill($stack[$#stack], $n, $k); # Angefangene Lösung um neue Kombination ergänzen
if ($new_comb > 0) { # falls gelungen
$mask[$#stack] = $stack[$#stack] | lastbit($new_comb ^ $stack[$#stack]); # kleinstes neues Element obligatorisch
push(@stack, $new_comb); # eintragen
} else {
if ($output) {
printf ("%12d ", $nsol);
print_sets (@stack);
};
$nsol++;
$success = 0;
while ($#stack) { # jüngste Kombination suchen, die sich ersetzen lässt
$mask = $mask[$#stack-1];
$new_comb = advance(pop(@stack), $n, $mask); # Kombination zu ersetzen versuchen
if ($new_comb > 0) { # falls gelungen
$mask[$#stack] = $stack[$#stack] | lastbit($new_comb ^ $stack[$#stack]); # kleinstes neues Element obligatorisch
push(@stack, $new_comb); # eintragen
$success = 1;
last; # keine weitere suchen
};
};
return $nsol unless $success; # die allererste Kombination ließ sich auch nicht ersetzen
};
};
};
Ralf Goertz
2018-09-04 08:16:35 UTC
Antworten
Permalink
Raw Message
Am Sun, 2 Sep 2018 09:54:38 +0200
Post by Helmut Richter
Post by Ralf Goertz
Post by Ralf Goertz
Die dritte Menge ist dann schon das Komplement der Vereinigung der
ersten beiden. Die erste Runde next_permutation wird fünfmal
durchlaufen, die zweite, darin geschachtelt, dreimal. Damit hätte
man die 15 Partitionen. Der Vorteil ist nicht nur die Vermeidung
von Dubletten sondern auch die Speichererparnis. Mein Rechner
hätte nämlich von der Zeit her locker auch größere m und n
zugelassen, allerdings kostet das Speichern im
set<set<vector<int>>> dann sehr schnell sehr viel Platz und
zwingt den Computer in die Knie. Und der Algorithmus lässt sich
leicht nichtrekursiv programmieren, denke ich. Vielleicht
probiere ich es nachher mal.
Ich habe das jetzt gemacht. Alllerdings doch rekursiv. Bin aber um
Ich habs nicht bleiben lassen können, meinen Algorithmus auch mal zu
programmieren, allerdings ohne *jede* Rücksicht auf Effizienz, sondern
erst mal, ob so geht (heißt heute wohl proof of concept), noch dazu in
Perl, was bei solchen Anwendungen (bloß rechnen, nichts denken)
Größenordnungen an Rechenzeit kostet. Dazu unten mehr.
Allerdings Speicherprobleme habe ich keine: man braucht nur den Platz
für den Stack bei der Rekursion, das sind 2 Integers pro Niveau Tiefe.
Die Speicherprobleme sind bei mir jetzt ja auch weg. Die hatte ich nur
deshalb, weil ich jede neu erzeugte Partition auf Einzigartigkeit prüfen
musste, als ich noch Dubletten hatte. Das ist mit dem neuen Ansatz ja
nicht mehr der Fall. Vielleicht erkläre ich den nochmal:

0 n Mengen mit jeweils m Elementen
1 für die erste Menge erzeuge ein Array mit n*m Elementen und belege die
ersten m davon mit 1, den Rest mit 0
2 gehe mit Hilfe von prev_permutation() alle „Permutationen“ dieses
Arrays durch, die das erste Element festlassen. Die Anführungsstriche
deshalb, weil es eine Multimenge ist, die natürlich viel weniger als
(m-1)! Permutationen hat. Wiederhole diesen Schritt für jede weitere
Teilmenge, wobei jedes Array immer m Elemente weniger haben als der
Vorgänger (weil ja nur weniger Elemente zur Auswahl stehen)

Jede 1 in diesen Arrays steht für ein Element der Teilmenge. Die
Position der 1 gibt an, um welches Element es sich handelt. Dabei müssen
natürlich Vorgängerteilmengen berücksichtigt werden, aber das ist kein
Ding. next_permutation ist wohl übrigens im Prinzip Knuths Algorithm L
(Lexicographic permutation generation) zu finden unter
<http://www.cs.utsa.edu/~wagner/knuth/fasc2b.pdf> Seite 5.
Post by Helmut Richter
Die Rekursivität kann übrigens durchaus Zeit sparen. Ich halte
momentan die Nichtrekursivität bei mir für eines der möglichen
Effizienzprobleme.
Ja, die Rekursion ist elegant und sollte kein Problem sein. Die Tiefe
bei mir ist n. In anderen Programmen habe ich mit Tiefen von 60
gearbeitet, ohne dass das zu Problemen geführt hätte.
Post by Helmut Richter
Post by Ralf Goertz
There are 126126 partitions
real 0m0.044s
user 0m0.043s
sys 0m0.001s
Das sind bei mir 9,3 sec, also Faktor 217.
Das sagt gar nichts aus. Perl ist eine Interpreter-Sprache, die locker
um so einen Faktor langsamer ist. Ich halte es durchaus für möglich,
dass dein Algorithmus schneller ist, obwohl das durchlaufen der
Permutationen schon extrem schnell ist.
Post by Helmut Richter
Post by Ralf Goertz
(Natürlich ohne output). Für 4*5 erhalte ich
There are 488864376 partitions
real 1m25.758s
user 1m25.373s
sys 0m0.033s
Das sind bei mir 10 h, also Faktor 416.
Die Faktoren sehen wild aus, sind aber Interpretation vs. Compilation
sowie ausgiebigen Laufzeitchecks geschuldet. Ich möchte das Ding mal
nach C übersetzen, was nicht so viel Arbeit ist, weil die Sachen, die
Perl besser kann, gar nicht vorkommen. Nur habe ich leider sehr wenig
Ahnung von C, auch wenn ich das eine oder andere Progrämmelchen
geschrieben habe. Aber was man machen muss, um aus einem in C
geschriebenen Algorithmus ein komplettes lauffähiges Programm zu
machen und welche Compileroptionen es gibt, da bin ich blank.
Ich habe wenig Ahnung von Perl, glaube aber, dass ich aus dem Programm
schon den Algorithmus extrahieren und in C++ übersetzen kann. Blankes C
benutze ich eigentlich nicht, weil man auf viel zu viel verzichten muss,
ohne dadurch einen wirklichen Geschwindigkeitsvorteil zu haben.
Post by Helmut Richter
Post by Ralf Goertz
Keine Ahnung, ob das jetzt äquivalent zu Helmuts Vorgehen ist. Das
ist zwar auch elegant, aber für mich nicht so intuitiv.
Ich habe es nur sehr knapp beschrieben – so schrecklich unintuitiv ist
es meiner Ansicht nach nicht. Ich hänge eine kommentierte Version an.
Das liegt wohl an mir. Ich habe eine Vorstellung entwickelt, was du
machst, nämlich aus der Bitdarstellung auf die Teilmengen zu schließen,
aber die „Bitschiebereien“ erschließen sich mir nicht so leicht wie
meine Idee mit den Permutationen der Einsen und Nullen, die ja
vielleicht auf dasselbe hinauslaufen könnten.
Post by Helmut Richter
a) Der Algorithmus soll die Lösungen produzieren, die gesucht werden,
und nicht eine Obermenge und dann die überflüssigen wegschmeißen.
Dass immer von Permutationen (also viel mehr als Kombinationen) und
Dubletten (die solls gar nicht geben) die Rede war, hat mich
alarmiert. Ob zu Recht, weiß ich nicht, so genau habe ich in die
hier veröffentlichten Algorithmen nicht hineingesehen.
Siehe oben, das tut mein jetziger Ansatz auch.
Post by Helmut Richter
b) Wenn man eine Kombination als ganze Zahl darstellt – jedes mögliche
Element 1 Bit –, dann ist es eine billige Operation, mit ein paar
Booleschen und arithmetischen Operationen die nächste Kombination
zu finden. Neu seit dem letzten Mal ist, dass es nicht teurer wird,
auch noch eine Maske von Bits dazu anzugeben, die auf jeden Fall
vorkommen müssen. Geht billig nur bis zur Wortlänge von Integers,
aber da sind wir bis jetzt ja erst bei 20.
Das lässt mich eben vermuten, die Ansätze könnten ähnlich sein. Meine
Arrays können ja auch als Bitfolgen interpretiert werden.
Post by Helmut Richter
Jetzt, wo ich schon angefangen habe, mache ich auch noch ein wenig
1. Schauen, ob die Einführung von Rekursion was bringt oder was
kostet. Es gibt dann gar keine Arrays mehr, nur noch einfache
Variable, die allerdings im Aufrufstack gestapelt werden. Keine
Ahnung, wie viel ich da ändern muss – vermutlich nicht allzu viel,
aber doch mit der Chance auf viele neue Fehler.
2. Die bessere (klarere?, schnellere?) der beiden Versionen von Hand
in C übersetzen und dann einen realistischeren Laufzeitvergleich
machen. Da könnte ich Hilfe brauchen, weil ich, wie oben erwähnt,
für C-Programme keinen Blick habe.
Wie gesagt, da kann ich gern mit anfassen.

Stefan Ram
2018-08-25 14:31:34 UTC
Antworten
Permalink
Raw Message
Post by Ralf Goertz
for (int i=0;i<n;++i) {
for (int j=0;j<m;++j)
*it++=i;
}
Hier könnte man vermutlich auch schreiben:

for (int i=0;i<n;++i) it = fill_n( it, m, i );

. Zu »endl« siehe auch:

CppCon 2017: Dietmar Kühl "The End of std::endl" - YouTube - 3:13


.
Ralf Goertz
2018-08-26 07:41:51 UTC
Antworten
Permalink
Raw Message
Am 25 Aug 2018 14:31:34 GMT
Post by Stefan Ram
Post by Ralf Goertz
for (int i=0;i<n;++i) {
for (int j=0;j<m;++j)
*it++=i;
}
for (int i=0;i<n;++i) it = fill_n( it, m, i );
Das ist ein guter Vorschlag, danke.
Post by Stefan Ram
CppCon 2017: Dietmar Kühl "The End of std::endl" - YouTube - 3:13
http://youtu.be/6WeEMlmrfOI
Ich glaube, ich bin zu alt, um nicht mehr „endl“ zu benutzen.
Mir ist das Problem mit flush bewusst, und ich achte normalerweise auch
darauf, wenn es zeitkritisch wird. Aber ich finde ich es viel
aufwändiger '\n' zu schreiben, weil ich zweimal die Shift- und einmal
die AltGr-Taste verwenden muss. Hier ging es mir nur um den
Algorithmus.
Roland Franzius
2018-08-24 05:18:19 UTC
Antworten
Permalink
Raw Message
Post by Stefan Ram
Das ist für mich typisch Kombinatorik: Du willst irgendetwas machen.
Das Hauptproblem besteht darin, herauszufinden, was die Fach-
bezeichnung in der Kombinatorik dafür ist. Wenn Du das
einmal herausgefunden hast, kannst Du viele Quellen finden,
und der Rest ist dann einfach.
Nachdem man das Wort "Kombinatorik" gefunden hat, kauft man sich ein
Buch oder lädt sich ein Vorlesungsscript down.

Will man was auf dem Computer machen, kauft man sich Knuth's "The Art".

https://www.amazon.de/s/ref=nb_sb_ss_i_6_12/259-1333970-0935412?__mk_de_DE=%C3%85M%C3%85%C5%BD%C3%95%C3%91&url=search-alias%3Daps&field-keywords=donald+knuth+s+the+art+of+computer+programming&sprefix=donald+knuth%2Caps%2C227&crid=17X853JDTC002

Hat man das während seiner Skype-Sitzungen hinter sich im Regal stehen,
gilt man in Fachkreisen schon als Guru.
--
Roland Franzius
Loading...