Zahlenreihe mit wenig überschneidung

Hallo liebe Forum Mitglieder,

seit geraumer Zeit zerbeche ich mir den Kopf über eine auf den ersten Blick simple klingende Problematik… in der Umsetzung bin ich unbedarf von Excel über TurboPascal (ja ich weiß) gescheitert.

Ich möchte aus einem Zahlenbereich von 1-50
Mir soviele 8er Zahlenreihen genieren lassen wie möglich, beidenen sich maximal 2 Zahlen doppeln dürfen.

Also:
1 2 3 4 5 6 7 8
1 2 14 15 16 17 18 19

1 2 20 21 22 23 24 3 (wäre nicht mehr okay da die Kombi 1,2,3) schon vor kam!?

Irgendwie müssen hierbei jede neue Reihe mit allen vorhandenen Reihen abgeglichen werden. Ich hab überlegt ob ich erst 2er Zahlenpaare bilde, aber auch das, wird fast unübersichtlich!?

Hallo,
Du suchst die ersten 8 Elemente einer zufälligen Permutation.

In Unix (z.B. Linux) wäre es:

 $ seq 1 50 | shuf | head -n 8

Eine Umsetzung von shuf in C gibt es hier https://github.com/ibara/shuf/blob/master/shuf.c.

Ah, ich glaube ich habe überlesen, daß Du alle Permutationen haben willst, oder noch genauer die Variationen (da Reihenfolge bei Dir keine Rolle spielen soll?).

Wäre das okay?

 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 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
 1  2  9 10 17 18 25 26
10 11 18 19 26 27 34 35
 ...

so eine Art Sieb, bei dem man einfach an die Zahlen innerhalb eines Rechtecks der Breite zwei (und Höhe vier) greedy abschreibt? Wenn man dieses Rechteck geschickt weiterschiebt (nämlich diagonal), gibt es immer genau eine Dopplung aus jeder der Originalzeilen. Allerdings „stört“ die obere Schranke 50, die sollte 48 oder 64 sein.

Guten Morgen und vielen lieben Dank für die ausführlichen Antworten.

Die obere Schranke wäre tatsächlich 70.

Gesucht sind alle Kombinationen von 1 bis 70…in jeweils 8er Reihen.
wobei zwischen den reihen maximal nur 2er Kombinationen sich überscheiden sollen.
maximal 3 3er kombinationen.

Meinst du, das würde sich durch das diagonale verschieben ergeben?
Und wenn ja, wie könnte ich das prüfen, für einen Mensch schier unmöglich.
Deswegen hatte ich excel bemüht aber ich denke das es dafür keine Funktion gibt!?

Ich glaube, was ich gesagt habe ist alles falsch. Es muß ja auch möglich sein, 7 elementige Mengen derart paarweise zu schneiden, daß höchstens 2 Elemente im Schnitt sind. Ich versuche mich gerade selbst an einem Algorithmus. Muß mich allerdings vorher in „Combinadics“ einlesen.

Sicher ist, Excel hat in puncto Kombinatorik nichts an Bord.

Ah okay…Danke :slight_smile:
Ich denke die Schwierigkeit liegt darin einen vernünftigen Ansatz zu finden…als random zahlen zu generieren welche hinterher mit viel aufwand verglichen und sortiert werden …

die kombinatinen gehen ja fast ins unermessliche, aber mit den richtigen Ansatz, denke ich ist es möglich …

oooh, genau an dieser Brute-Force-Lösung habe ich jetzt gearbeitet. Code-mäßig sehr elegant und überschaubar, aber dafür seeeeeeeeeeeehr langsam.

Ich hab nochmal nachgedacht und fasse nun das Problem als Graphenproblem auf:
Eine Variation [a,b,c,d,…] wird dargestellt als ein Pfad [(a,b),(b,c),(c,d),…].

Die Tupel (a,b) (mit a<b) symbolisieren das Paar {a,b}. Der Knoten (a,b) ist mit allen (b,x) verbunden. Das sieht ungefähr so aus:

(1,2) (1,3) (1,4) ...
      (2,3) (2,4) ...
            (3,4) ...

eine obere Dreiecksgestalt.

Die Bedingung, daß nur zwei Elemente sich doppeln dürfen, drückt man nun graphenmäßig aus, daß je zwei Pfade nur höchstens einen Knoten gemeinsam haben. Die Aufgabe ist also: Suche alle Pfade der Länge 7, die sich paarweise höchstens einmal kreuzen.

Das ganze habe ich naturgemäß in Prolog implementiert. Allerdings ist meine dumme C Variante doch um einiges schneller. Für den kleinen Raum (mit Zahlen von 1 bis 40) habe ich nach über zwei Stunden noch keine Lösung gehabt. Im trace konnte ich aber sehen, daß es im Prinzip funktioniert.

Parallel habe ich noch einen CLPZ-Solver laufen lassen (auf viel viel kleineren Räumen), um zu schauen, ob der vielleicht einen konstruktiven Weg findet, sprich eine Vorschrift um aus der bisher besten Lösung L eine Lösung L1 zu konstruieren. Außer einer Explosion von Constraints, die vermutlich unentscheidbar sind (Gödel läßt grüßen), habe ich nichts gesehen. Den Code habe ich erfolgreich auf 5-elementigen Variation mit Alphabet 1-10 getestet, dauerte ein paar Sekunden. Den 8/1-40 Fall habe ich ebenfalls nach zwei Stunden ausgemacht.

namd,

nochmal der Ansatz, den ich schonmal im Kopf hatte:

Bei 8 Zahlen, davon 2 schonmal verwendet, ergibt sich zunächst, dass man die 2 ignorieren könnte, da sie, bei der gleichen Menge, überschüssig vorhanden sind.

Bleibt also die 6er Reihe und beliebige 2 andere dazu, die begrenzen die Sache nicht.
Damit sind es 11 Reihen, bei 70 Zahlen.
Bleiben die 3 Reihen, bei denen 3 doppelt sein durften. Die 3 sind auch übrig und begrenzen die Zahlen aus den Doppelten 2ern nicht (11*2… da ist ewig Luft).

also 3 zusätzlich, das reicht für eine weitere Reihe, da diese dann nur 5 Zahlen verbraucht.

Also 9*6 + 3*5 macht 12 Reihen.

Hab ich nen Denkfehler?

Das generieren ergibt sich daraus, 6er Reihen von vorn, die 2er wahllos von hinten. Wenn diese zufällig eine schon vorhanden ist. dann eben die Nächste - sind ja genug da.

grüße
lipi