Zahlenreihe mit wenig überschneidung

Computer: Software & Programmierung Programmierung allgemein
#1

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!?

#3

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.

#4

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.

#5

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!?

#6

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.

#7

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 …

#8

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

#9

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.

#10

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

#11

Als Beispiel:

| 1  2  3  4  5  6| 13 14|   1
| 7  8  9 10 11 12| 13 14|   2
|13 14 15 16 17 18|  7  8|   3
|19 20 21 22 23 24|  7  8|   4
|25 26 27 28 29 30| 19 20|   5
|31 32 33 34 35 36| 19 20|   6 
...
|61 62 63 64 65 66| 43 44|  11

wie geht’s weiter?Runterwärts, damit es keine versehentlichen Doppelungen gibt?

| 1  7 13 19 25 31| 43 44|  12
| 2  8 14 20 26 32| 43 44|  13
?

Zum checken benutz(t)e ich:

pairwise(Rel_2, Xs) :-
    i_pairwise(Xs, Rel_2).

i_pairwise([], _).
i_pairwise([X|Xs], Rel_2) :-
    maplist(call(Rel_2,X),Xs),
    i_pairwise(Xs, Rel_2).

constr(X,Y) :-
    constr(X,Y,_).
constr(X,Y,[X|Y]) :-
    intersection(X,Y,Z),
    length(Z,N),
    N #=< 2.

?- L = [[1,2,3,4,5,6,13,14],[7,8,9,10,11,12,13,14],...]), pairwise(constr, L).

Soweit ist alles gut, aberwie garantiert man, alle zu bekommen?

#12

hi,

Deine 2. Spalte verstehe ich nicht ganz.
Ich würde sie nicht bewusst doppelt nehmen. Sondern eben nur nochmal wahllos, denn einmal sind sie ja bereits verwendet worden.
Dass sie doppelt sind, ergibt sich quasi von selbst.

Da die genügend Zahlen vorhanden sind, und es wirklich nicht eng wird, dachte ich mehr an:

Einfach Doppelt
1 1 2 3 4 5 6 70 69
2 7 8 9 10 11 12 68 67
3 13 14 15 16 17 18 66 65
4 19 20 21 22 23 24 64 63
5 25 26 27 28 29 30 62 61
6 31 32 33 34 35 36 60 59
7 37 38 39 40 41 42 58 57
8 43 44 45 46 47 48 56 55
9 49 50 51 52 53 54 54 48
10 55 56 57 58 59 47 46 45
11 60 61 62 63 64 44 43 42
12 65 66 67 68 69 41 40 39

in deinem Beispiel ist in Reihe 1,2,3 und 13 die 14 drin.
So wie ich das verstanden habe, ist es damit falsch.

eben damit es keine versehentlichen Dopplungen gibt, würde ich 1 bis 6 und 7,8 getrennt betrachten [1 bis 70 und 70 bis 1] und jeweils nur einmal verwenden.
Damit ergibt sich die Dopplung automatisch und die Kontrolle beschränkt sich auf die Prüfung, ob die Zahl bereits in der 6er Reihe vorhanden ist. Dann überspringt man eben solang ein paar.
Und super einfach zu generieren.

grüße
lipi

#13

Ooh, dann lösen wir, glaube ich, verschiedene Probleme. Ich hatte den OP so verstanden, daß sich Paare beliebig oft wiederholen dürfen, aber Tripel eben nie.

Ich gebe Dir aber in Deiner Analyse recht und habe sie jetzt auch verstanden.

#14

ja, wenn man das Thema nochmal liest, hast du recht.
Danke, dass du mich vom Schlauch gehoben hast :wink:

grüße
lipi

#15

ABER Du hast mich mit Deiner Konstruktion auf die Idee gebracht, das Problem in drei Teile zu teilen: A u B u C … mit A paarweise disjunkt (Partitionierung), B paarweise genau ein Element im Schnitt und C paarweise genau zwei Elemente im Schnitt.

Die Konstruktion von A hast Du geliefert. B klingt erstmal nicht so schwer, aber vielleicht kann man B aus A bauen, dann mit derselben Methode C aus B.

Ich denke gerade um die Ecke, aber ist A nicht ein B’ bestehend aus neun Elementen, bei dem man „paarweise“ das Element im Schnitt weglaesst und so genau disjunkte Mengen erhaelt?

#16

Hallo ihr beiden,

ich danke euch für eure bisherigen Lösungsansätze…die für mich teils neue Denkanstöße geben.

Ich bin mir sicher das bei 70 Zahlen, 8 Reihen und maximal 2er Komibantionen pro Reihe…
es insgesamt zirka 2415 (8er) Reihen geben sollte… wobei jede Zahl (1-70) dann zirka 280x enthalten sein sollte…!?

Der Weg dahin ist halt das Problem,grds habe ich kein Zeitproblem (Der Computer darf gerne durchlaufen…) und würde wenn ich das recht verstanden haben die 40er Variante einfach mal probieren, auf 70 Zahlen!?
Wichtig ist nur das die Reihen dann stimmen :slight_smile: !?

#17

Mist, die mittlere Passage war nicht ganz fertig…hier die Ergänzung

Ich bin mir sicher das bei 70 Zahlen, 8 Reihen und maximal 2er Komibantionen pro Reihe…und maximal 3 gleichen Dreiern…es insgesamt zirka 2450 (8er) Reihen geben sollte… wobei jede Zahl (1-70) dann zirka 280x enthalten sein sollte…!?

2er Kombinationen wiederholen sich in der Tat mehrfach…beginne ich bsp in der ersten Reihe von Zeile 1 bis 280 die Zahl 1 niederzuschreiben und lege in Spalte 2 die Zahl 2 an, so beginnen die erste 34 Reihen mit 1, 2, , , , , ,

#18

34 Reihen mit 1,2 ohne weiteren Überlapp? Kannst Du die mal schicken?

#19

Hallo speedking,

habe ich es richtig verstanden?
Du willst ein Programm schreiben, mit dem Du eine maximal große Menge an Zahlenreihen ermitteln kannst, die folgende Bedingungen erfüllen:
Die Zahlenreihen haben immer 8 Elemente.
Die Zahlenreihen enthalten verschiedene Zahlen aus 1 … n (z.B. n=50)
Untereinander dürfen die Zahlenreihen maximal 2 gleiche Zahlen enthalten.

Stimmt das so?

Wenn ja, ist das sicherlich nichts, was man sinnvoll mit EXCEL errechnet. Allein die Anzahl der potenziellen Reihen bei n=50 ist „50 über 8“, also rund 537 Mio Möglichkeiten, die noch mal untereinander zu prüfen sind. Macht 1,4*10hoch17 Reihenvergleiche. Was wiederum noch mal rund 50 Einzelvergleiche sind.

Da brauchst Du schon einen extrem schnellen Rechner, damit Du auf diese Weise das Ergebnis noch erlebst. Bei n=70 dürfte es keine käufliche Hardware geben, die das noch schaffst.

Und dabei ist mir noch nicht klar, dass dieser Ansatz gleich zur maximalen Anzahl führt.

Ein Denkfehler in der bisherigen Diskussion ist, dass man nicht davon ausgehen darf, dass die zugelassene Doppelung immer die gleich zwei Ziffern betrifft. So hat man nur eine untere Schranke.

#20

Magst Du das erklären?

#21

Hallo liebe Mitdenkenden :slight_smile:

Die Interpretation von „allesquatsch“ ist richtig, was die zahlenreihen, elemente etc betrifft.
Zu der Dopplung gibt es zu sagen, dass jede Zahl in jeder Kombination doppelt, mehrfach vorkommen wird/darf. Also bspw. 1 ,2 kommt mehrfach vor, genauso 56,62 oder andere 2.er Kombinationen…

Ich hänge mal eine händisch erstelle Tabelle an, welche durch einfaches verschieben der Zeilen zum quasi gewünschten Ergebnis führt. Da keine Logik dahinter liegt, erschöpft sich das ganze recht schnell…und man sieht in der T

kombination
kombination1365×2016 2.06 MB
at schon die ersten Dreier…ich denke das der Computer schon in der Lage wäre, mit entsprechender Logik, einfach die ZahlenReihen nach einer entsprechenden Wohlverteilung anzulegen…aber die Lösung scheint tatsächlich nicht ganz trivial zu sein…