Bester Datentyp für sehr große Liste an Sachen?

Java-Forum Allgemeine Themen
1

Hallo,
ich habe bewusst diese Überschrift gewählt weil meine Frage relativ allgemein ist.
Hintergrund ist Folgender:
Just for fun und im Rahmen eines größeren Programms will ich alle (oder fast alle) Kombinationen aus 6 Zahlen haben, wobei die Zahlen aus dem pool 1-49 kommen (ohne zurücklegen).
Sozusagen Lotto6aus49.

Naturgemäß sind das viele zahlen, schätzungsweise so um die 4948474645*44/6!=ca. 10^7 Kombinationen.
Normal hätte ich jede 6zahlenkombi als int arra der Länge 6 gespeichert und wiederum Alle diese Array in einem Array eben jener Länge 10^7 gespeichert.
Also ein 2 dimensionales Array, wobei die „1. Dimension“ entsprechend sehr sehr sehr lang ist.

Da bekanntlich die indizes eines Arrays int zahlen sind, wird es da vermutlich bei so großen indexstellen gefährlich mit Überlauf und Ähnlichem.

Darum bin ich, generell gesprochen, am Überlegen wie ich eine sehr große Liste an Elementen (wobei die Elemente wie hier int arrays, Strings, irgendwas sein können. Nur halt alle Elemente gleicher Typ)
am besten bzw. überhaupt speichern kann, welcher Datentyp das am besten händelt.

Es sollte schon ein Typ sein, der sowas wie ein indexsystem anbietet.
Also bspw. Linkedlist wäre eher nicht so gut weil ich bspw. auch mal das 3467. Element der Liste für was benutzen wollen würde.

Gibts da einen guten Datentyp für solch lächerlich großen Listen?

Leider wird es sich nicht verhindenr lassen dass ich eine so große Liste brauche da ich Folgendes machen will:
Liste aller 6Zahlenkombis bauen.

Für jede der Zahlen Folgendes machen:
Diese in ihre 3-Zahlen-Kombis zerlegen (man denke an potenzmenge, nur halt dass ich nur die Mengen der Länge 3 haben will).
Dann für jede dieser 3Kombizahlen die (um die zerlegte 6erZahl reduzierte) große Lsite durchgehen und gucken ob sich eine Zahl findet, in der diese 3 zahlen enthalten sind.

Ziel ist auf gut Deutsch gesagt für eine betrachtete 6er zahl eben zu gucken, ob alle ihre 3er kombis schon irgendwo anders in anderen 6er zahlen vorkommen.
Denn dann ist die betrahctete 6er zahl überflüssig und kann gelöscht werden.

so geht man halt die lsite durch bi sich eine überflüssige 6er zahl findet und die entfernt wird.
oder man das ende ereicht hat und die Lsite shcon optimal ist.

Und wenn das Ganze so steht, dann diesen Optimierungsalgorithmus eben so oft immer wieder auf die Lsite anwenden (wobei jeder Durchgang eben max. 1 6er Zahl löscht), bis wir eine optimale Lsite vorliegen haben.

Insofern brauche ich eine liste der 6er zahlen die sehr groß sein wird, muss für eine 6er Zahl dann zwischendurch eine liste aller 3er zahlen finden, jede der 3er Zahlen mit so gut wiee der kompletten 6er Lsite gegenvergleichen.

Insofern, die komplette 6er Liste muss einfach irgendwie zugreifbar sein.

2

Die Frage ist sehr allgemein. Es gibt viele Seiten, wo beschrieben wird, unter welchen Bedingungen welche Collection „die beste“ ist. Um da „die beste“ Antwort zu finden, kann man viele Faktoren berücksichtigen. Das heißt: Nur weil du die Frage vermeintlich allgemein stellst, heißt das nicht, dass man eine allgemeine gute Antwort geben kann.

Trotzdem ein paar recht allgemeine Punkte:

Wenn du wirklich eine Liste brauchst, dann ist List<T> der Datentyp. Welche Implementierung man dann wählt, ist fast egal.

In Java haben Listen eine allgemeine Beschränkung: Sie können höchstens ca. 2 Milliarden Elemente enthalten. Das liegt schon daran, dass size() einen int zurückgibt. Wenn du mehr Elemente brauchst, muss man sich was überlegen. Wenn es darum geht, wirklich viele Daten zu speichern (oder auch mehr als 2 Milliarden) kann man eine Datenbank in Betracht ziehen. Die gibt’s auch in-Memory. Da gibt’s viele Möglichkeiten. Da muss man halt schauen…

(Wenn es nur um „6-aus-49“ geht, ist man von dieser Grenze aber noch weit weg…)

Was du da mit den 3er-Kombinationen beschrieben hast, ist nicht ganz klar, da müßte ich länger nachdenken und nachfragen…

Aber…

… speichere nicht alle diese Elemente in einer Liste!

Das folgende ist ein Programm, das eine Liste erstellt, mit allen Lottozahlen-Kombinationen „6 aus 49“. Das sind 13983816 Elemente, jeweils 6 int-Werte, die jeweils 4 byte belegen, und selbst wenn man den Overhead für die Arrays etc. außer Acht läßt, sind das über dreihundertdreißig Megabyte. (Was heutzutage ja nicht mehr viel ist, aber … immerhin).

Die Liste, die hier erstellt wird, belegt aber weniger als 100 bytes. Egal, wie groß die Liste ist. Du kannst auch so eine Liste für eine „6 aus 1000“-Ziehung erstellen, oder eine „100 aus 10000“-Ziehung, und sie belegt immer weniger als 100 bytes. (Das Problem bei letzteren ist, dass die Listengröße nicht mehr als int abgebildet werden kann, aber … du musst ja keine Liste verwenden - die generate-Methode könntest du auch direkt aufrufen).

package bytewelt;

import java.math.BigInteger;
import java.util.AbstractList;
import java.util.Arrays;
import java.util.List;

public class CeciNestPasUneList
{
    public static void main(String[] args)
    {
        List<int[]> list = createList();
        int size = list.size();
        for (int i = 0; i < 10; i++)
        {
            System.out.println("At " + i + " " + Arrays.toString(list.get(i)));
        }
        System.out.println("...");
        for (int i = size - 10; i < size; i++)
        {
            System.out.println("At " + i + " " + Arrays.toString(list.get(i)));
        }

    }
    
    private static List<int[]> createList()
    {
        int n = 49;
        int k = 6;
        int size = (int)nChooseK(n, k);
        return new AbstractList<int[]>()
        {

            @Override
            public int[] get(int index)
            {
                if (index < 0 || index >= size)
                {
                    throw new IndexOutOfBoundsException(
                        "Index must be in [0," + size + "), but is " + index);
                }
                return generate(index, n, k);
            }

            @Override
            public int size()
            {
                return size;
            }
        };
    }
    
    private static BigInteger factorial(int n)
    {
        BigInteger f = BigInteger.ONE;
        for (int i = 2; i <= n; i++)
        {
            f = f.multiply(BigInteger.valueOf(i));
        }
        return f;
    }        

    private static long nChooseK(int n, int k)
    {
        BigInteger nf = factorial(n);
        BigInteger kf = factorial(k);
        BigInteger nmkf = factorial(n-k);
        BigInteger divisor = kf.multiply(nmkf);
        BigInteger result = nf.divide(divisor);
        return result.longValue();    
    }

    // See https://math.stackexchange.com/a/1227692
    private static int[] generate(long i, int n, int k)
    {
        int c[] = new int[k];
        long r = i + 1;
        int j = 0;
        for (int s = 1; s < k + 1; s++)
        {
            int cs = j + 1;
            while (r - nChooseK(n - cs, k - s) > 0)
            {
                r -= nChooseK(n - cs, k - s);
                cs += 1;
            }
            c[s - 1] = cs;
            j = cs;
        }
        return c;
    }
    
}
3

Ich komm auf 10.068.347.520 verschiedene Kombinationen, und selbst wenn man „byte“ verwendet (was ausreichen würde für 1-49) wären das über 56 Gigabyte, und wenn man den restlichen Overhead dazu rechnet, dann sind wir bei weit über 100GB die diese Liste benötigen würde.
Selbst wenn man den Speicherplatz irgendwie bereitstellen würde, würde das nie zu Lebzeiten fertig werden.

Es wäre besser, das mathematisch herzuleiten und zu beweisen, als das Brute Force zu berechnen.

2 „Gefällt mir“
4

Wo jetzt? Wenn du auch noch diese „Dreierkombinations-Sache“ reinrechnest? (Hatte nicht ganz kapiert, was damit gemeint war - meine Zahl bezog sich nur auf Lottoziehungen…)

5

Ich sollte vielleicht mein Grundthema etwas klarer formulieren:
Sei eine Liste A an 6 stelligen Lottozahlen gegeben.
(Lottozahlen 1-49, in jeder 6er Kombi kommt jede zahl maximal 1 mal vor. Also 5,5,5,5,5,5 oder sowas unzulässig. Wie beim Lotto halt)

Es sei ebenso eine Liste B gegeben, die wirklich alle möglichen 6 stelligen Lottozahlen enthält.
Also Alles von (1,2,3,4,5,6) bis (44,45,46,47,48,49).

A wird natürlich Teilmenge von B sein, wa aber unwichtig ist fürs Problem.

Zu finden ist die Liste A.
Zu JEDEM Zeitpunkt soll folgendes erfüllt sein:
Egal was für eine 6er kombi y aus B gezogen wird, es muss immer mind. ein (zugehöriges) x aus A existieren, sodass x und y mind. 3 Zahlen gemein haben (wenn man also die 6 Zahlen aus x getippt hätte und die 6 zahlen aus y gezogen worden wären, hätte man mind. 3 richtige).

Nun ist es praktisch unmöglich, so frei Hand eine solche minimale Liste A zu erraten.
Also nehmen wir aus vertrauten Quellen eine Liste, vond er wir wissen dass diese die Bedingung erfüllt.
Und gucken dann eins nach dem Anderen alle möglichen Elemente aus A dahingehend durch ob wir dieses Element weglassen können und die verbleibende Restliste trotzdem die Bedingung erfüllt.

Praktishc geht das nur mit Bruteforce.
Also erst mal die Liste A ohne das 1. Element betrachten und für jedes y aus B gucken ob es in der verkürzten A liste ein passendes Element gibt um gmeeinsam 3 richtige zu haben.

Finden wir ein Element aus B, zu dem kein zugehöriges Element aus der vekrürzten A Liste existiert mit dem es 3 richtige überein hat, können wir abrwchen und haben gezeigt dass das 1. element aus A „unentbehrlich ist“ und nicht gekürzt werden kann.

nun das selbe spiel mit dem 2. element aus A, dann das 3., usw.
Bis wir entweder was kürzbares gefunden haben oder eben die lsite zu ende ist.

das rinse and repeaten wir natürlich endlos woibei wir in jeder runde eben ein weiteres element aus A rauskürzen.
Oder eben in einem durchlauf durch die liste durchkommen ohne was kürzbares zu finden.
Dann stellt die verbleibende Liste (eine?) Minimalliste dar.

DIe Minimalliste will ich haben.

Mein problem ist halt nur dass hier abertausende Kreuz und Quervergleiche gemacht werden müssen.
Alleine das „Hat x aus A und y aus B 3 Richtige gemeinsam“ ist shcon so eine Sache für sich.

Sinnvoll wäre es vermutlich, gar nicht erst 6-tupel zu betrachten sondern tupel aus 3-tupeln.
eben statt einer 6er kombi dqas tupel, das alle 3er kombis enthält.
Oder so.

Vermutlich.
Keine Ahnung

6

Falls ich das richtig verstanden habe, dann willst du die mimimale Liste aller Lottoziehungen berechnen, mit denen garantiert (mindestens) drei richtige hat.

Ist das so? (Wenn ja: Warum hast du es dann nicht genau so gesagt? :smirk: )

Falls das so ist, dann gibt es ja schon das rein algorithmische Problem, dass (selbst wenn du diese Listen kompakt und effizient speichern könntest) der Algorithmus, um das Ergebnis zu bestimmen, in der beschriebenen Form viel zu aufwändig wäre.

Ich habe das gerade mal mit ein paar „kleinen“ Zahlen durchlaufen lassen…

Hier die Ausgabe, falls es relevant ist 
For 3 from 8 with 1 matches
  Start with 56
  Required: 4
    [1, 2, 3]
    [1, 2, 4]
    [1, 2, 5]
    [1, 2, 6]
For 3 from 8 with 2 matches
  Start with 56
  Required: 15
    [1, 2, 3]
    [1, 2, 4]
    [1, 2, 5]
    [1, 2, 6]
    [1, 2, 7]
    [1, 3, 4]
    [1, 3, 5]
    [1, 3, 6]
    [1, 3, 7]
    [1, 4, 5]
    [1, 4, 6]
    [1, 4, 7]
    [1, 5, 6]
    [1, 5, 7]
    [1, 6, 7]
For 4 from 8 with 1 matches
  Start with 70
  Required: 2
    [1, 2, 3, 4]
    [1, 2, 3, 5]
For 4 from 8 with 2 matches
  Start with 70
  Required: 6
    [1, 2, 3, 4]
    [1, 2, 3, 5]
    [1, 2, 3, 6]
    [1, 2, 4, 5]
    [1, 2, 4, 6]
    [1, 2, 5, 6]
For 4 from 8 with 3 matches
  Start with 70
  Required: 20
    [1, 2, 3, 4]
    [1, 2, 3, 5]
    [1, 2, 3, 6]
    [1, 2, 3, 7]
    [1, 2, 4, 5]
    [1, 2, 4, 6]
    [1, 2, 4, 7]
    [1, 2, 5, 6]
    [1, 2, 5, 7]
    [1, 2, 6, 7]
    [1, 3, 4, 5]
    [1, 3, 4, 6]
    [1, 3, 4, 7]
    [1, 3, 5, 6]
    [1, 3, 5, 7]
    [1, 3, 6, 7]
    [1, 4, 5, 6]
    [1, 4, 5, 7]
    [1, 4, 6, 7]
    [1, 5, 6, 7]
For 5 from 8 with 1 matches
  Start with 56
  Required: 1
    [1, 2, 3, 4, 5]
For 5 from 8 with 2 matches
  Start with 56
  Required: 1
    [1, 2, 3, 4, 5]
For 5 from 8 with 3 matches
  Start with 56
  Required: 4
    [1, 2, 3, 4, 5]
    [1, 2, 3, 4, 6]
    [1, 2, 3, 5, 6]
    [1, 2, 4, 5, 6]
For 5 from 8 with 4 matches
  Start with 56
  Required: 15
    [1, 2, 3, 4, 5]
    [1, 2, 3, 4, 6]
    [1, 2, 3, 4, 7]
    [1, 2, 3, 5, 6]
    [1, 2, 3, 5, 7]
    [1, 2, 3, 6, 7]
    [1, 2, 4, 5, 6]
    [1, 2, 4, 5, 7]
    [1, 2, 4, 6, 7]
    [1, 2, 5, 6, 7]
    [1, 3, 4, 5, 6]
    [1, 3, 4, 5, 7]
    [1, 3, 4, 6, 7]
    [1, 3, 5, 6, 7]
    [1, 4, 5, 6, 7]
For 3 from 9 with 1 matches
  Start with 84
  Required: 5
    [1, 2, 3]
    [1, 2, 4]
    [1, 2, 5]
    [1, 2, 6]
    [1, 2, 7]
For 3 from 9 with 2 matches
  Start with 84
  Required: 21
    [1, 2, 3]
    [1, 2, 4]
    [1, 2, 5]
    [1, 2, 6]
    [1, 2, 7]
    [1, 2, 8]
    [1, 3, 4]
    [1, 3, 5]
    [1, 3, 6]
    [1, 3, 7]
    [1, 3, 8]
    [1, 4, 5]
    [1, 4, 6]
    [1, 4, 7]
    [1, 4, 8]
    [1, 5, 6]
    [1, 5, 7]
    [1, 5, 8]
    [1, 6, 7]
    [1, 6, 8]
    [1, 7, 8]
For 4 from 9 with 1 matches
  Start with 126
  Required: 3
    [1, 2, 3, 4]
    [1, 2, 3, 5]
    [1, 2, 3, 6]
For 4 from 9 with 2 matches
  Start with 126
  Required: 10
    [1, 2, 3, 4]
    [1, 2, 3, 5]
    [1, 2, 3, 6]
    [1, 2, 3, 7]
    [1, 2, 4, 5]
    [1, 2, 4, 6]
    [1, 2, 4, 7]
    [1, 2, 5, 6]
    [1, 2, 5, 7]
    [1, 2, 6, 7]
For 4 from 9 with 3 matches
  Start with 126
  Required: 35
    [1, 2, 3, 4]
    [1, 2, 3, 5]
    [1, 2, 3, 6]
    [1, 2, 3, 7]
    [1, 2, 3, 8]
    [1, 2, 4, 5]
    [1, 2, 4, 6]
    [1, 2, 4, 7]
    [1, 2, 4, 8]
    [1, 2, 5, 6]
    [1, 2, 5, 7]
    [1, 2, 5, 8]
    [1, 2, 6, 7]
    [1, 2, 6, 8]
    [1, 2, 7, 8]
    [1, 3, 4, 5]
    [1, 3, 4, 6]
    [1, 3, 4, 7]
    [1, 3, 4, 8]
    [1, 3, 5, 6]
    [1, 3, 5, 7]
    [1, 3, 5, 8]
    [1, 3, 6, 7]
    [1, 3, 6, 8]
    [1, 3, 7, 8]
    [1, 4, 5, 6]
    [1, 4, 5, 7]
    [1, 4, 5, 8]
    [1, 4, 6, 7]
    [1, 4, 6, 8]
    [1, 4, 7, 8]
    [1, 5, 6, 7]
    [1, 5, 6, 8]
    [1, 5, 7, 8]
    [1, 6, 7, 8]
For 5 from 9 with 1 matches
  Start with 126
  Required: 1
    [1, 2, 3, 4, 5]
For 5 from 9 with 2 matches
  Start with 126
  Required: 3
    [1, 2, 3, 4, 5]
    [1, 2, 3, 4, 6]
    [1, 2, 3, 5, 6]
For 5 from 9 with 3 matches
  Start with 126
  Required: 10
    [1, 2, 3, 4, 5]
    [1, 2, 3, 4, 6]
    [1, 2, 3, 4, 7]
    [1, 2, 3, 5, 6]
    [1, 2, 3, 5, 7]
    [1, 2, 3, 6, 7]
    [1, 2, 4, 5, 6]
    [1, 2, 4, 5, 7]
    [1, 2, 4, 6, 7]
    [1, 2, 5, 6, 7]
For 5 from 9 with 4 matches
  Start with 126
  Required: 35
    [1, 2, 3, 4, 5]
    [1, 2, 3, 4, 6]
    [1, 2, 3, 4, 7]
    [1, 2, 3, 4, 8]
    [1, 2, 3, 5, 6]
    [1, 2, 3, 5, 7]
    [1, 2, 3, 5, 8]
    [1, 2, 3, 6, 7]
    [1, 2, 3, 6, 8]
    [1, 2, 3, 7, 8]
    [1, 2, 4, 5, 6]
    [1, 2, 4, 5, 7]
    [1, 2, 4, 5, 8]
    [1, 2, 4, 6, 7]
    [1, 2, 4, 6, 8]
    [1, 2, 4, 7, 8]
    [1, 2, 5, 6, 7]
    [1, 2, 5, 6, 8]
    [1, 2, 5, 7, 8]
    [1, 2, 6, 7, 8]
    [1, 3, 4, 5, 6]
    [1, 3, 4, 5, 7]
    [1, 3, 4, 5, 8]
    [1, 3, 4, 6, 7]
    [1, 3, 4, 6, 8]
    [1, 3, 4, 7, 8]
    [1, 3, 5, 6, 7]
    [1, 3, 5, 6, 8]
    [1, 3, 5, 7, 8]
    [1, 3, 6, 7, 8]
    [1, 4, 5, 6, 7]
    [1, 4, 5, 6, 8]
    [1, 4, 5, 7, 8]
    [1, 4, 6, 7, 8]
    [1, 5, 6, 7, 8]
For 3 from 10 with 1 matches
  Start with 120
  Required: 6
    [1, 2, 3]
    [1, 2, 4]
    [1, 2, 5]
    [1, 2, 6]
    [1, 2, 7]
    [1, 2, 8]
For 3 from 10 with 2 matches
  Start with 120
  Required: 28
    [1, 2, 3]
    [1, 2, 4]
    [1, 2, 5]
    [1, 2, 6]
    [1, 2, 7]
    [1, 2, 8]
    [1, 2, 9]
    [1, 3, 4]
    [1, 3, 5]
    [1, 3, 6]
    [1, 3, 7]
    [1, 3, 8]
    [1, 3, 9]
    [1, 4, 5]
    [1, 4, 6]
    [1, 4, 7]
    [1, 4, 8]
    [1, 4, 9]
    [1, 5, 6]
    [1, 5, 7]
    [1, 5, 8]
    [1, 5, 9]
    [1, 6, 7]
    [1, 6, 8]
    [1, 6, 9]
    [1, 7, 8]
    [1, 7, 9]
    [1, 8, 9]
For 4 from 10 with 1 matches
  Start with 210
  Required: 4
    [1, 2, 3, 4]
    [1, 2, 3, 5]
    [1, 2, 3, 6]
    [1, 2, 3, 7]
For 4 from 10 with 2 matches
  Start with 210
  Required: 15
    [1, 2, 3, 4]
    [1, 2, 3, 5]
    [1, 2, 3, 6]
    [1, 2, 3, 7]
    [1, 2, 3, 8]
    [1, 2, 4, 5]
    [1, 2, 4, 6]
    [1, 2, 4, 7]
    [1, 2, 4, 8]
    [1, 2, 5, 6]
    [1, 2, 5, 7]
    [1, 2, 5, 8]
    [1, 2, 6, 7]
    [1, 2, 6, 8]
    [1, 2, 7, 8]
For 4 from 10 with 3 matches
  Start with 210
  Required: 56
    [1, 2, 3, 4]
    [1, 2, 3, 5]
    [1, 2, 3, 6]
    [1, 2, 3, 7]
    [1, 2, 3, 8]
    [1, 2, 3, 9]
    [1, 2, 4, 5]
    [1, 2, 4, 6]
    [1, 2, 4, 7]
    [1, 2, 4, 8]
    [1, 2, 4, 9]
    [1, 2, 5, 6]
    [1, 2, 5, 7]
    [1, 2, 5, 8]
    [1, 2, 5, 9]
    [1, 2, 6, 7]
    [1, 2, 6, 8]
    [1, 2, 6, 9]
    [1, 2, 7, 8]
    [1, 2, 7, 9]
    [1, 2, 8, 9]
    [1, 3, 4, 5]
    [1, 3, 4, 6]
    [1, 3, 4, 7]
    [1, 3, 4, 8]
    [1, 3, 4, 9]
    [1, 3, 5, 6]
    [1, 3, 5, 7]
    [1, 3, 5, 8]
    [1, 3, 5, 9]
    [1, 3, 6, 7]
    [1, 3, 6, 8]
    [1, 3, 6, 9]
    [1, 3, 7, 8]
    [1, 3, 7, 9]
    [1, 3, 8, 9]
    [1, 4, 5, 6]
    [1, 4, 5, 7]
    [1, 4, 5, 8]
    [1, 4, 5, 9]
    [1, 4, 6, 7]
    [1, 4, 6, 8]
    [1, 4, 6, 9]
    [1, 4, 7, 8]
    [1, 4, 7, 9]
    [1, 4, 8, 9]
    [1, 5, 6, 7]
    [1, 5, 6, 8]
    [1, 5, 6, 9]
    [1, 5, 7, 8]
    [1, 5, 7, 9]
    [1, 5, 8, 9]
    [1, 6, 7, 8]
    [1, 6, 7, 9]
    [1, 6, 8, 9]
    [1, 7, 8, 9]
For 5 from 10 with 1 matches
  Start with 252
  Required: 2
    [1, 2, 3, 4, 5]
    [1, 2, 3, 4, 6]
For 5 from 10 with 2 matches
  Start with 252
  Required: 6
    [1, 2, 3, 4, 5]
    [1, 2, 3, 4, 6]
    [1, 2, 3, 4, 7]
    [1, 2, 3, 5, 6]
    [1, 2, 3, 5, 7]
    [1, 2, 3, 6, 7]
For 5 from 10 with 3 matches
  Start with 252
  Required: 20
    [1, 2, 3, 4, 5]
    [1, 2, 3, 4, 6]
    [1, 2, 3, 4, 7]
    [1, 2, 3, 4, 8]
    [1, 2, 3, 5, 6]
    [1, 2, 3, 5, 7]
    [1, 2, 3, 5, 8]
    [1, 2, 3, 6, 7]
    [1, 2, 3, 6, 8]
    [1, 2, 3, 7, 8]
    [1, 2, 4, 5, 6]
    [1, 2, 4, 5, 7]
    [1, 2, 4, 5, 8]
    [1, 2, 4, 6, 7]
    [1, 2, 4, 6, 8]
    [1, 2, 4, 7, 8]
    [1, 2, 5, 6, 7]
    [1, 2, 5, 6, 8]
    [1, 2, 5, 7, 8]
    [1, 2, 6, 7, 8]
For 5 from 10 with 4 matches
  Start with 252
  Required: 70
    [1, 2, 3, 4, 5]
    [1, 2, 3, 4, 6]
    [1, 2, 3, 4, 7]
    [1, 2, 3, 4, 8]
    [1, 2, 3, 4, 9]
    [1, 2, 3, 5, 6]
    [1, 2, 3, 5, 7]
    [1, 2, 3, 5, 8]
    [1, 2, 3, 5, 9]
    [1, 2, 3, 6, 7]
    [1, 2, 3, 6, 8]
    [1, 2, 3, 6, 9]
    [1, 2, 3, 7, 8]
    [1, 2, 3, 7, 9]
    [1, 2, 3, 8, 9]
    [1, 2, 4, 5, 6]
    [1, 2, 4, 5, 7]
    [1, 2, 4, 5, 8]
    [1, 2, 4, 5, 9]
    [1, 2, 4, 6, 7]
    [1, 2, 4, 6, 8]
    [1, 2, 4, 6, 9]
    [1, 2, 4, 7, 8]
    [1, 2, 4, 7, 9]
    [1, 2, 4, 8, 9]
    [1, 2, 5, 6, 7]
    [1, 2, 5, 6, 8]
    [1, 2, 5, 6, 9]
    [1, 2, 5, 7, 8]
    [1, 2, 5, 7, 9]
    [1, 2, 5, 8, 9]
    [1, 2, 6, 7, 8]
    [1, 2, 6, 7, 9]
    [1, 2, 6, 8, 9]
    [1, 2, 7, 8, 9]
    [1, 3, 4, 5, 6]
    [1, 3, 4, 5, 7]
    [1, 3, 4, 5, 8]
    [1, 3, 4, 5, 9]
    [1, 3, 4, 6, 7]
    [1, 3, 4, 6, 8]
    [1, 3, 4, 6, 9]
    [1, 3, 4, 7, 8]
    [1, 3, 4, 7, 9]
    [1, 3, 4, 8, 9]
    [1, 3, 5, 6, 7]
    [1, 3, 5, 6, 8]
    [1, 3, 5, 6, 9]
    [1, 3, 5, 7, 8]
    [1, 3, 5, 7, 9]
    [1, 3, 5, 8, 9]
    [1, 3, 6, 7, 8]
    [1, 3, 6, 7, 9]
    [1, 3, 6, 8, 9]
    [1, 3, 7, 8, 9]
    [1, 4, 5, 6, 7]
    [1, 4, 5, 6, 8]
    [1, 4, 5, 6, 9]
    [1, 4, 5, 7, 8]
    [1, 4, 5, 7, 9]
    [1, 4, 5, 8, 9]
    [1, 4, 6, 7, 8]
    [1, 4, 6, 7, 9]
    [1, 4, 6, 8, 9]
    [1, 4, 7, 8, 9]
    [1, 5, 6, 7, 8]
    [1, 5, 6, 7, 9]
    [1, 5, 6, 8, 9]
    [1, 5, 7, 8, 9]
    [1, 6, 7, 8, 9]
For 3 from 11 with 1 matches
  Start with 165
  Required: 7
    [1, 2, 3]
    [1, 2, 4]
    [1, 2, 5]
    [1, 2, 6]
    [1, 2, 7]
    [1, 2, 8]
    [1, 2, 9]
For 3 from 11 with 2 matches
  Start with 165
  Required: 36
    [1, 2, 3]
    [1, 2, 4]
    [1, 2, 5]
    [1, 2, 6]
    [1, 2, 7]
    [1, 2, 8]
    [1, 2, 9]
    [1, 2, 10]
    [1, 3, 4]
    [1, 3, 5]
    [1, 3, 6]
    [1, 3, 7]
    [1, 3, 8]
    [1, 3, 9]
    [1, 3, 10]
    [1, 4, 5]
    [1, 4, 6]
    [1, 4, 7]
    [1, 4, 8]
    [1, 4, 9]
    [1, 4, 10]
    [1, 5, 6]
    [1, 5, 7]
    [1, 5, 8]
    [1, 5, 9]
    [1, 5, 10]
    [1, 6, 7]
    [1, 6, 8]
    [1, 6, 9]
    [1, 6, 10]
    [1, 7, 8]
    [1, 7, 9]
    [1, 7, 10]
    [1, 8, 9]
    [1, 8, 10]
    [1, 9, 10]
For 4 from 11 with 1 matches
  Start with 330
  Required: 5
    [1, 2, 3, 4]
    [1, 2, 3, 5]
    [1, 2, 3, 6]
    [1, 2, 3, 7]
    [1, 2, 3, 8]
For 4 from 11 with 2 matches
  Start with 330
  Required: 21
    [1, 2, 3, 4]
    [1, 2, 3, 5]
    [1, 2, 3, 6]
    [1, 2, 3, 7]
    [1, 2, 3, 8]
    [1, 2, 3, 9]
    [1, 2, 4, 5]
    [1, 2, 4, 6]
    [1, 2, 4, 7]
    [1, 2, 4, 8]
    [1, 2, 4, 9]
    [1, 2, 5, 6]
    [1, 2, 5, 7]
    [1, 2, 5, 8]
    [1, 2, 5, 9]
    [1, 2, 6, 7]
    [1, 2, 6, 8]
    [1, 2, 6, 9]
    [1, 2, 7, 8]
    [1, 2, 7, 9]
    [1, 2, 8, 9]
For 4 from 11 with 3 matches
  Start with 330
  Required: 84
    [1, 2, 3, 4]
    [1, 2, 3, 5]
    [1, 2, 3, 6]
    [1, 2, 3, 7]
    [1, 2, 3, 8]
    [1, 2, 3, 9]
    [1, 2, 3, 10]
    [1, 2, 4, 5]
    [1, 2, 4, 6]
    [1, 2, 4, 7]
    [1, 2, 4, 8]
    [1, 2, 4, 9]
    [1, 2, 4, 10]
    [1, 2, 5, 6]
    [1, 2, 5, 7]
    [1, 2, 5, 8]
    [1, 2, 5, 9]
    [1, 2, 5, 10]
    [1, 2, 6, 7]
    [1, 2, 6, 8]
    [1, 2, 6, 9]
    [1, 2, 6, 10]
    [1, 2, 7, 8]
    [1, 2, 7, 9]
    [1, 2, 7, 10]
    [1, 2, 8, 9]
    [1, 2, 8, 10]
    [1, 2, 9, 10]
    [1, 3, 4, 5]
    [1, 3, 4, 6]
    [1, 3, 4, 7]
    [1, 3, 4, 8]
    [1, 3, 4, 9]
    [1, 3, 4, 10]
    [1, 3, 5, 6]
    [1, 3, 5, 7]
    [1, 3, 5, 8]
    [1, 3, 5, 9]
    [1, 3, 5, 10]
    [1, 3, 6, 7]
    [1, 3, 6, 8]
    [1, 3, 6, 9]
    [1, 3, 6, 10]
    [1, 3, 7, 8]
    [1, 3, 7, 9]
    [1, 3, 7, 10]
    [1, 3, 8, 9]
    [1, 3, 8, 10]
    [1, 3, 9, 10]
    [1, 4, 5, 6]
    [1, 4, 5, 7]
    [1, 4, 5, 8]
    [1, 4, 5, 9]
    [1, 4, 5, 10]
    [1, 4, 6, 7]
    [1, 4, 6, 8]
    [1, 4, 6, 9]
    [1, 4, 6, 10]
    [1, 4, 7, 8]
    [1, 4, 7, 9]
    [1, 4, 7, 10]
    [1, 4, 8, 9]
    [1, 4, 8, 10]
    [1, 4, 9, 10]
    [1, 5, 6, 7]
    [1, 5, 6, 8]
    [1, 5, 6, 9]
    [1, 5, 6, 10]
    [1, 5, 7, 8]
    [1, 5, 7, 9]
    [1, 5, 7, 10]
    [1, 5, 8, 9]
    [1, 5, 8, 10]
    [1, 5, 9, 10]
    [1, 6, 7, 8]
    [1, 6, 7, 9]
    [1, 6, 7, 10]
    [1, 6, 8, 9]
    [1, 6, 8, 10]
    [1, 6, 9, 10]
    [1, 7, 8, 9]
    [1, 7, 8, 10]
    [1, 7, 9, 10]
    [1, 8, 9, 10]
For 5 from 11 with 1 matches
  Start with 462
  Required: 3
    [1, 2, 3, 4, 5]
    [1, 2, 3, 4, 6]
    [1, 2, 3, 4, 7]
For 5 from 11 with 2 matches
  Start with 462
  Required: 10
    [1, 2, 3, 4, 5]
    [1, 2, 3, 4, 6]
    [1, 2, 3, 4, 7]
    [1, 2, 3, 4, 8]
    [1, 2, 3, 5, 6]
    [1, 2, 3, 5, 7]
    [1, 2, 3, 5, 8]
    [1, 2, 3, 6, 7]
    [1, 2, 3, 6, 8]
    [1, 2, 3, 7, 8]
For 5 from 11 with 3 matches
  Start with 462
  Required: 35
    [1, 2, 3, 4, 5]
    [1, 2, 3, 4, 6]
    [1, 2, 3, 4, 7]
    [1, 2, 3, 4, 8]
    [1, 2, 3, 4, 9]
    [1, 2, 3, 5, 6]
    [1, 2, 3, 5, 7]
    [1, 2, 3, 5, 8]
    [1, 2, 3, 5, 9]
    [1, 2, 3, 6, 7]
    [1, 2, 3, 6, 8]
    [1, 2, 3, 6, 9]
    [1, 2, 3, 7, 8]
    [1, 2, 3, 7, 9]
    [1, 2, 3, 8, 9]
    [1, 2, 4, 5, 6]
    [1, 2, 4, 5, 7]
    [1, 2, 4, 5, 8]
    [1, 2, 4, 5, 9]
    [1, 2, 4, 6, 7]
    [1, 2, 4, 6, 8]
    [1, 2, 4, 6, 9]
    [1, 2, 4, 7, 8]
    [1, 2, 4, 7, 9]
    [1, 2, 4, 8, 9]
    [1, 2, 5, 6, 7]
    [1, 2, 5, 6, 8]
    [1, 2, 5, 6, 9]
    [1, 2, 5, 7, 8]
    [1, 2, 5, 7, 9]
    [1, 2, 5, 8, 9]
    [1, 2, 6, 7, 8]
    [1, 2, 6, 7, 9]
    [1, 2, 6, 8, 9]
    [1, 2, 7, 8, 9]
For 5 from 11 with 4 matches
  Start with 462
  Required: 126
    [1, 2, 3, 4, 5]
    [1, 2, 3, 4, 6]
    [1, 2, 3, 4, 7]
    [1, 2, 3, 4, 8]
    [1, 2, 3, 4, 9]
    [1, 2, 3, 4, 10]
    [1, 2, 3, 5, 6]
    [1, 2, 3, 5, 7]
    [1, 2, 3, 5, 8]
    [1, 2, 3, 5, 9]
    [1, 2, 3, 5, 10]
    [1, 2, 3, 6, 7]
    [1, 2, 3, 6, 8]
    [1, 2, 3, 6, 9]
    [1, 2, 3, 6, 10]
    [1, 2, 3, 7, 8]
    [1, 2, 3, 7, 9]
    [1, 2, 3, 7, 10]
    [1, 2, 3, 8, 9]
    [1, 2, 3, 8, 10]
    [1, 2, 3, 9, 10]
    [1, 2, 4, 5, 6]
    [1, 2, 4, 5, 7]
    [1, 2, 4, 5, 8]
    [1, 2, 4, 5, 9]
    [1, 2, 4, 5, 10]
    [1, 2, 4, 6, 7]
    [1, 2, 4, 6, 8]
    [1, 2, 4, 6, 9]
    [1, 2, 4, 6, 10]
    [1, 2, 4, 7, 8]
    [1, 2, 4, 7, 9]
    [1, 2, 4, 7, 10]
    [1, 2, 4, 8, 9]
    [1, 2, 4, 8, 10]
    [1, 2, 4, 9, 10]
    [1, 2, 5, 6, 7]
    [1, 2, 5, 6, 8]
    [1, 2, 5, 6, 9]
    [1, 2, 5, 6, 10]
    [1, 2, 5, 7, 8]
    [1, 2, 5, 7, 9]
    [1, 2, 5, 7, 10]
    [1, 2, 5, 8, 9]
    [1, 2, 5, 8, 10]
    [1, 2, 5, 9, 10]
    [1, 2, 6, 7, 8]
    [1, 2, 6, 7, 9]
    [1, 2, 6, 7, 10]
    [1, 2, 6, 8, 9]
    [1, 2, 6, 8, 10]
    [1, 2, 6, 9, 10]
    [1, 2, 7, 8, 9]
    [1, 2, 7, 8, 10]
    [1, 2, 7, 9, 10]
    [1, 2, 8, 9, 10]
    [1, 3, 4, 5, 6]
    [1, 3, 4, 5, 7]
    [1, 3, 4, 5, 8]
    [1, 3, 4, 5, 9]
    [1, 3, 4, 5, 10]
    [1, 3, 4, 6, 7]
    [1, 3, 4, 6, 8]
    [1, 3, 4, 6, 9]
    [1, 3, 4, 6, 10]
    [1, 3, 4, 7, 8]
    [1, 3, 4, 7, 9]
    [1, 3, 4, 7, 10]
    [1, 3, 4, 8, 9]
    [1, 3, 4, 8, 10]
    [1, 3, 4, 9, 10]
    [1, 3, 5, 6, 7]
    [1, 3, 5, 6, 8]
    [1, 3, 5, 6, 9]
    [1, 3, 5, 6, 10]
    [1, 3, 5, 7, 8]
    [1, 3, 5, 7, 9]
    [1, 3, 5, 7, 10]
    [1, 3, 5, 8, 9]
    [1, 3, 5, 8, 10]
    [1, 3, 5, 9, 10]
    [1, 3, 6, 7, 8]
    [1, 3, 6, 7, 9]
    [1, 3, 6, 7, 10]
    [1, 3, 6, 8, 9]
    [1, 3, 6, 8, 10]
    [1, 3, 6, 9, 10]
    [1, 3, 7, 8, 9]
    [1, 3, 7, 8, 10]
    [1, 3, 7, 9, 10]
    [1, 3, 8, 9, 10]
    [1, 4, 5, 6, 7]
    [1, 4, 5, 6, 8]
    [1, 4, 5, 6, 9]
    [1, 4, 5, 6, 10]
    [1, 4, 5, 7, 8]
    [1, 4, 5, 7, 9]
    [1, 4, 5, 7, 10]
    [1, 4, 5, 8, 9]
    [1, 4, 5, 8, 10]
    [1, 4, 5, 9, 10]
    [1, 4, 6, 7, 8]
    [1, 4, 6, 7, 9]
    [1, 4, 6, 7, 10]
    [1, 4, 6, 8, 9]
    [1, 4, 6, 8, 10]
    [1, 4, 6, 9, 10]
    [1, 4, 7, 8, 9]
    [1, 4, 7, 8, 10]
    [1, 4, 7, 9, 10]
    [1, 4, 8, 9, 10]
    [1, 5, 6, 7, 8]
    [1, 5, 6, 7, 9]
    [1, 5, 6, 7, 10]
    [1, 5, 6, 8, 9]
    [1, 5, 6, 8, 10]
    [1, 5, 6, 9, 10]
    [1, 5, 7, 8, 9]
    [1, 5, 7, 8, 10]
    [1, 5, 7, 9, 10]
    [1, 5, 8, 9, 10]
    [1, 6, 7, 8, 9]
    [1, 6, 7, 8, 10]
    [1, 6, 7, 9, 10]
    [1, 6, 8, 9, 10]
    [1, 7, 8, 9, 10]

… und schon das hat eine Weile gedauert. (Es ist nur hingehackt, man könnte das auch dreimal so schnell machen, aber ob es bei 6-aus-49-mit-3 nun 90 Trilliarden Jahre oder nur 30 Trilliarden Jahre brauchen würde, ist nicht so wichtig…)

Aber ich bin sicher, dass es einen Ansatz gibt, der nicht darauf aufsetzt, diese Listen zu erstellen und in der beschriebenen Form mit „rinse and repeat“ durchzuprobieren. Wie genau dieser Ansatz aussieht? Das ist die Frage. Mein Bauchgefühl ist, dass man da was mit Vertex cover - Wikipedia machen oder es als Constraint satisfaction problem - Wikipedia formulieren könnte. Ja, das bedeutet nicht, dass es eine effiziente Lösung gäbe. Aber einen Komplexitätsbeweis für das Problem an sich zu führen, wäre etwas aufwändig. (Es könnte auch sein, dass es eine geschickte Möglichkeit gibt, diese minimale Liste direkt zu konstruieren, aber da müßte man genauer nachdenken).

Im Moment habe ich ein paar zeitliche Constraints, aber … es ist ein interessantes Problem, und vielleicht schau’ ich da am Wochenende nochmal genauer nach…

7

Nachtrag: Mein Instinkt sagt mir, dass man einige der Zahlen, die in der Ausgabe vorkommen, auch mal in https://oeis.org/ werfen könnte, und ich bin sicher, dass man da was findet. Aber ob es zur Lösung des Problems beiträgt, ist eine andere Frage…

8

Gute Frage, wahrscheinlich weil ich mich echt nicht gut ausdrücken kann?

Klar, mein Vorgehen ist extrem umständlich und vermutlich ineffizient.
Vor Allem aber zeit und performance aufwendig.

Es wäre halt die primitivste Brute Force Methode, die garantiert die Liste sukzessive um je 1 unnötige 6er Kombi pro Runde verkürzt.
Vermutlich geht das Alles viel einfacher, wer weiß?

Was ich so grundsätzlich dachte:
Wie ich schrieb, wäre es vielleicht sinnvoll, für die Elemente aus A und B statt 6-zahlen-kombis eher die 20 dreierkombis zu haben (halt statt den 6 zahlen die liste alle vorkommenden 3er kombis zu haben)

Und aber so einer dreierkombi jetzt nicht als simples array mit länge 3 zu haben, sondern einen extra datentyp für 3 elemetige tupel hzu haben und bspw. für das 3 tupel (1,2,3) überall, egal ob in a,b, sosntwo wo es vorkommt dieses objekt zu haben.

Natürlich extrem viel aufwand um anfang die lsiten A und B zu erstellen bei denen ein element letztlich ein Array mit 20 referenzen auf 3tupel-objekte sind.

Hätte, das erhoffe ich mir zumindest, den vorteil, wenn man dann in den rekursiven bereinigungsrunden ist, dass man nicht 2 3elementige arrays miteinander vergleichen muss, sondern nur referenzen vergleichen muss.

Ich sage ja, meine Erklärungen sind sch…ße :slight_smile:

Mal als als Beispiel:

Sagen wir A enthält das Tupel x=(1,2,3,4,5,6) und B das Tupel y=(1,2,3,7,8,9)

normal müssten wir für die 2 zahlen jeweils die zugehörigen 3 tupel suchen und für jedes der 3tupel links mit den 3 tupeln rechts vergleichen.

wobei jeder dieser vergleiche auf das durchlaufen zweier arrays hinausliefe.

offensichtlich ist ja dass das 3tupel (1,2,3) in beiden zahlen vorkommt.

hätten wir die die zahl (1,2,3,4,5,6) und auch die andere zahl zuvor aber als liste von 20 referenzen auf einzigartige 3Tupel-Objekte gespeichert, dann müssten wir nur nachgucken ob das in y vorkommende 3Tupel, das wir hier ja als Referenz oder faktisch als numerische Speicheradresse vorliegen haben, auch in x vorkommt.

Wir gucken also:
y enthält die referenz auf ein 3TupelObjekt mit Speicherid „3f4ff4g“.
wenn dieses 3tupel und damit das entsprechende 3Tupel Objekt auch in x vorkommt, muss sich dort auch eine referenz finden, die auf jenes objekt an speicherstelle „3f4ff4g“ zeigt.

Kurzum aus dem problem „vergleiche ob jede der ziffern (1,2,3) mit jeder der ziffern (1,2,3) inklusive reihenfolge übereinstimmt“ (was schleifen und so erfordert) wurde das simplere problem „ist die nummer „3f4ff4g“ gleich der nummer „3f4ff4g““ (halt vergleich zweier speicheradressen bzw. vergleich zweier einfacher nummern.

Hat halt den Vortiel dass überall wo das 3 tupel (1,2,3) vorkäme, überall die referenz auf das selbe 3 tupel element benutzt wird.
Dadurch dürfte das vergleichen, was bei meinem rinse and repeat vorgehen ja tausendfach vorkommt, etwas einfacher und kürzer ausfallen.

Natürlich müssen vorab die 6er-komibs in listen on 3er kombis zerlegt werden , entsprechende 3Tupel Objekte erzeugt werden, etc. pp.
viel vorarbeit damit das tausendfach kreuz und quer vergleichen hoffentlich halbwegs einfacher ist.

ob es natürlich so praktisch ist, in der hinterhand eine Liste aller möglichen 18424 3-Tupel verwalten zu müssen, ist die andere frage.

9

Das mit den 3er-Kombis klingt wieder recht kompliziert. Ich nehme an, diese „3“ kommt von der Anfrorderung, dass es „3 Richtige“ sein müssen? Ich müßte das noch genauer durchdenken, aber … nach dem ersten, schnellen (!) Durchlesen fühlt sich das komisch an: Das passt vielleicht bei „6 (aus 49) mit 3 Richtigen“. Aber wie man das auf „5 (aus 49) mit 3 Richtigen“ oder „6 (aus 49) mit 4 Richtigen“ anwenden wollte, weiß ich gerade nicht.

(Allgemein: Wenn die Anzahl der Gezogenen nicht durch die Anzahl der Richtigen teilbar ist, passt das irgendwie nicht…)

Nochmal zum ursprünglichen „Brute Force“:

Also erst mal die Liste A ohne das 1. Element betrachten und für jedes y aus B gucken ob es in der verkürzten A liste ein passendes Element gibt um gmeeinsam 3 richtige zu haben.

Finden wir ein Element aus B, zu dem kein zugehöriges Element aus der vekrürzten A Liste existiert mit dem es 3 richtige überein hat, können wir abrwchen und haben gezeigt dass das 1. element aus A „unentbehrlich ist“ und nicht gekürzt werden kann.

nun das selbe spiel mit dem 2. element aus A, dann das 3., usw.
Bis wir entweder was kürzbares gefunden haben oder eben die lsite zu ende is

Das funktioniert so glaube ich nicht. Angenommen, man stellt damit fest, dass

  • das 1. Element aus A unentbehrlich ist
  • das 2. Element aus A unentbehrlich ist
  • das 3. Element aus A unentbehrlich ist

Dann könnte es sein, dass das 2. doch entbehrlich wäre, wenn man das 1. und das 3. behalten würde.

(Ich hatte diesen Ansatz schnell hingehackt, und nicht tief genug darüber nachgedacht, und vielleicht habe ich irgendwo einen dummen Fehler drin, oder ein Mißverständnis, bin mir aber inwzwischen ziemlich sicher, dass das nicht die optimiale Lösung liefern würde)

Wenn du magst, kannst du deinen aktuellen Ansatz ja mal hier in der computeSolution-Methode einfügen:

package bytewelt;

import java.math.BigInteger;
import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;
import java.util.RandomAccess;

public class CeciNestPasUneListBase
{
    public static void main(String[] args)
    {
        int n = 49;
        int k = 6;
        int minMatches = 3;

        n = 10;
        k = 5;
        minMatches = 3;
        
        List<List<Integer>> solution = computeSolution(n, k, minMatches);
        
        System.out.println("Solution: " + solution.size());
        for (List<Integer> guess : solution)
        {
            System.out.println("    " + guess);
        }        
    }

    private static List<List<Integer>> computeSolution(int n, int k, int minMatches)
    {
        System.out.println(
            "For " + k + " from " + n + " with " + minMatches + " matches");
        List<List<Integer>> draws = createList(n, k);
        List<List<Integer>> solution = new ArrayList<List<Integer>>();

        // TODO Implement this!
        solution.add(Arrays.asList(-666,-666,-666));
        
        return solution;
    }

    private static int countMatches(
        Collection<Integer> draw, Collection<Integer> guess) 
    {
        int n = 0;
        for (Integer g : guess) 
        {
            if (draw.contains(g))
            {
                n++;
            }
        }
        return n;
    }

    private static List<List<Integer>> createList(int n, int k)
    {
        int size = (int)nChooseK(n, k);
        class Result extends AbstractList<List<Integer>> implements RandomAccess
        {

            @Override
            public List<Integer> get(int index)
            {
                if (index < 0 || index >= size)
                {
                    throw new IndexOutOfBoundsException(
                        "Index must be in [0," + size + "), but is " + index);
                }
                return asList(generate(index, n, k));
            }

            @Override
            public int size()
            {
                return size;
            }
        };
        return new Result();
    }

    private static List<Integer> asList(int array[])
    {
        class Result extends AbstractList<Integer> implements RandomAccess
        {
            @Override
            public Integer get(int index)
            {
                return array[index];
            }

            @Override
            public int size()
            {
                return array.length;
            }
        };
        return new Result();
    }

    private static BigInteger factorial(int n)
    {
        BigInteger f = BigInteger.ONE;
        for (int i = 2; i <= n; i++)
        {
            f = f.multiply(BigInteger.valueOf(i));
        }
        return f;
    }        

    private static long nChooseK(int n, int k)
    {
        BigInteger nf = factorial(n);
        BigInteger kf = factorial(k);
        BigInteger nmkf = factorial(n-k);
        BigInteger divisor = kf.multiply(nmkf);
        BigInteger result = nf.divide(divisor);
        return result.longValue();    
    }

    // See https://math.stackexchange.com/a/1227692
    private static int[] generate(long i, int n, int k)
    {
        int c[] = new int[k];
        long r = i + 1;
        int j = 0;
        for (int s = 1; s < k + 1; s++)
        {
            int cs = j + 1;
            while (r - nChooseK(n - cs, k - s) > 0)
            {
                r -= nChooseK(n - cs, k - s);
                cs += 1;
            }
            c[s - 1] = cs;
            j = cs;
        }
        return c;
    }
}

Bei mir liefert der beschriebene Ansatz da

  Required: 20
    [1, 2, 3, 4, 5]
    [1, 2, 3, 4, 6]
    [1, 2, 3, 4, 7]
    [1, 2, 3, 4, 8]
    [1, 2, 3, 5, 6]
    [1, 2, 3, 5, 7]
    [1, 2, 3, 5, 8]
    [1, 2, 3, 6, 7]
    [1, 2, 3, 6, 8]
    [1, 2, 3, 7, 8]
    [1, 2, 4, 5, 6]
    [1, 2, 4, 5, 7]
    [1, 2, 4, 5, 8]
    [1, 2, 4, 6, 7]
    [1, 2, 4, 6, 8]
    [1, 2, 4, 7, 8]
    [1, 2, 5, 6, 7]
    [1, 2, 5, 6, 8]
    [1, 2, 5, 7, 8]
    [1, 2, 6, 7, 8]

was sicher nicht optimal ist.

Ein Greedy-Ansatz, den ich gerade mal ausprobiert habe: Man betrachtet alle möglichen „draws“ (also alle Ziehungen) und alle möglichen „guesses“ (also alle möglichen Tipps).

  1. Für jeden Tipp: Bestimmte die Menge alle Ziehungen bei denen man mit diesem Tipp mindestens drei Richtige hätte
  2. Der „beste“ Tipp, mit dem man die meisten Ziehungen abdeckt, wird ausgewählt. Die Ziehungen, die damit abgedeckt sind, werden entfernt.
  3. Mit den Ziehungen, für die man dann noch keinen Tipp hat, macht man weiter bei 1.

In jeder Runde wird also der „beste“ Tipp bestimmt, mit dem man bei den meisten noch übrigen Ziehungen die gewünschten 3 Richtigen erreichen würde.

Erfahrungsgemäß liefern Greedy-Strategien auch nicht notwendigerweise die optimale Lösung. Aber erfahrungsgemäß liefern sie sehr oft sehr schnell sehr gute Lösungen bei Problemen, bei denen es praktisch unmöglich ist, die optimale Lösung zu bestimmen. (Vielleicht ist die Lösung hier aber auch optimal - das weiß ich nicht, und es ist schwierig, sowas zu beweisen…)

Hier mal mit „5 aus 16, mit 3 Richtigen“:

package bytewelt;

import java.math.BigInteger;
import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.RandomAccess;
import java.util.Set;

public class CeciNestPasUneListGreedy
{
    public static void main(String[] args)
    {
        int n = 49;
        int k = 6;
        int minMatches = 3;

        n = 16;
        k = 5;
        minMatches = 3;
        
        List<List<Integer>> solution = computeSolution(n, k, minMatches);
        
        System.out.println("Solution: " + solution.size());
        for (List<Integer> guess : solution)
        {
            System.out.println("    " + guess);
        }        
    }

    private static List<List<Integer>> computeSolution(int n, int k, int minMatches)
    {
        System.out.println(
            "For " + k + " from " + n + " with " + minMatches + " matches");

        Set<List<Integer>> uncoveredDraws = 
            new LinkedHashSet<List<Integer>>(createList(n, k));
        Set<List<Integer>> possibleGuesses = 
            new LinkedHashSet<List<Integer>>(uncoveredDraws);
        
        List<List<Integer>> bestGuesses = new ArrayList<List<Integer>>();
        while (!uncoveredDraws.isEmpty()) 
        {            
            System.out.println("Have "+uncoveredDraws.size()+" uncovered");
            
            List<Integer> maxCoveredGuess = null;
            Set<List<Integer>> maxCoveredDraws = 
                new LinkedHashSet<List<Integer>>();
            
            for (List<Integer> guess : possibleGuesses)
            {
                Set<List<Integer>> coveredDraws = 
                    new LinkedHashSet<List<Integer>>();
                for (List<Integer> draw : uncoveredDraws)
                {
                    int matches = countMatches(draw, guess);
                    if (matches >= minMatches)
                    {
                        coveredDraws.add(draw);
                    }
                }
                if (coveredDraws.size() > maxCoveredDraws.size())
                {
                    maxCoveredGuess = guess;
                    maxCoveredDraws = coveredDraws;
                }
            }
            System.out.println("Guess " + maxCoveredGuess + " covers "
                + maxCoveredDraws.size() + " of " + uncoveredDraws.size());
            
            bestGuesses.add(maxCoveredGuess);
            possibleGuesses.remove(maxCoveredGuess);
            uncoveredDraws.removeAll(maxCoveredDraws);
        }
        return bestGuesses;
    }

    private static int countMatches(
        Collection<Integer> draw, Collection<Integer> guess) 
    {
        int n = 0;
        for (Integer g : guess) 
        {
            if (draw.contains(g))
            {
                n++;
            }
        }
        return n;
    }

    private static List<List<Integer>> createList(int n, int k)
    {
        int size = (int)nChooseK(n, k);
        class Result extends AbstractList<List<Integer>> implements RandomAccess
        {

            @Override
            public List<Integer> get(int index)
            {
                if (index < 0 || index >= size)
                {
                    throw new IndexOutOfBoundsException(
                        "Index must be in [0," + size + "), but is " + index);
                }
                return asList(generate(index, n, k));
            }

            @Override
            public int size()
            {
                return size;
            }
        };
        return new Result();
    }

    private static List<Integer> asList(int array[])
    {
        class Result extends AbstractList<Integer> implements RandomAccess
        {
            @Override
            public Integer get(int index)
            {
                return array[index];
            }

            @Override
            public int size()
            {
                return array.length;
            }
        };
        return new Result();
    }

    private static BigInteger factorial(int n)
    {
        BigInteger f = BigInteger.ONE;
        for (int i = 2; i <= n; i++)
        {
            f = f.multiply(BigInteger.valueOf(i));
        }
        return f;
    }        

    private static long nChooseK(int n, int k)
    {
        BigInteger nf = factorial(n);
        BigInteger kf = factorial(k);
        BigInteger nmkf = factorial(n-k);
        BigInteger divisor = kf.multiply(nmkf);
        BigInteger result = nf.divide(divisor);
        return result.longValue();    
    }

    // See https://math.stackexchange.com/a/1227692
    private static int[] generate(long i, int n, int k)
    {
        int c[] = new int[k];
        long r = i + 1;
        int j = 0;
        for (int s = 1; s < k + 1; s++)
        {
            int cs = j + 1;
            while (r - nChooseK(n - cs, k - s) > 0)
            {
                r -= nChooseK(n - cs, k - s);
                cs += 1;
            }
            c[s - 1] = cs;
            j = cs;
        }
        return c;
    }
}

Schon bei „6 aus 16“ oder „5 aus 18“ muss man ein Momentchen warten, deswegen ist das auch noch weit weg, von einer Lösung, aber … deutlich näher dran, als Brute Force.

10

Das alleine shcon zu erklären ist umstänlich genug…

Mal ein unvollständiges Beispiel um die Situation ein wenig zu erklären:

Sagen wir jetzt einfach mal, es sei
A={(1,2,3,4),(7,11,34,45), (1,12,13,14)}
Aus gottgegebenen Gründen könnte nur eine der 3 Zahlenkombis gezogen werden.

und wir hätten eine Liste
b={(1,2,5,6),(1,3,7,11),(1,12,34,4),(12,13,4,45)}
Auch diese Lsite sei, wie es auch in der Aufgabe wäre, als Inoput vorgegeben.

Unds geht es darum, dass wenn man alle Elemente aus B auf einmal tippt, man garantiert 2 Richtige hat. Egal welche der 3 Zahlenkombis aus A nun an dem Tag gezogen werden.
B wird uns als Input vorgegeben und wir können sicher sein dass es das erfüllt, es ist so vorgegeben.

Nun ksotet bekanntlich jede getippte zahlenkombi Geld und wir wollen es billiger haben, falls möglich (und natürlich trotzdem garantiert 2 Richtige finden).
Wir gucken also, welche Zahlenkombi aus B „überflüssig“ ist, also entfernt werden kann, und die Restliste erfüllt trotzdem die 2 Richtige Bedingung.

Seien also wie gesagt

A={(1,2,3,4),(7,11,34,45), (1,12,13,14)}
B={(1,2,5,6),(1,3,7,11),(1,12,34,4),(12,13,4,45)}

Nun könnten wir ganz naiv hingehen, das erste Lement aus B betrachten und uns fragen:
Ist (1,2,5,6) eine überflüssige Kombi?
Um das zu beantworten, müssten wir die verkürzte Liste
B*={(1,3,7,11),(1,12,34,4),(12,13,4,45)}
betrachten und gucken:

Gibt es zu jedem x aus A (immer noch) (mindestens) ein zugehöriges y aus B*, sodass x und y
2 Richtige haben, also 2 Zahlen übereinstimmen?
(Nehmen wir mal oben an, die Zahlenkombis wären überall aufsteigend sortiert)
Dann kann man mit nem synchronem Durchlauf durhc x und y das testen wie viele zahlen die gmeinsam haben.

Konkret würden wir also wie folgt vorgehen:
(1,2,3,4) aus A und (1,3,7,11) aus B* haben 2 Zahlen gemeinsam.
Die Zahlenkombi (1,2,3,4) aus A ist also auch weiterhin durch die verkürzte Liste abgedeckt.

Guchen wir also weiter:
(7,11,34,45) aus A und (1,3,7,11) aus B* haben 2 Richtige gemeinsam.

gucken wir weiter:
(1,12,13,14) aus A und (1,3,7,11) aus B* haben keine 2 Zahlen gemeinsam.
(1,12,13,14) aus A und (1,12,34,4) aus B* haben 2 Zahlen gemeinsam.

Wir sind am Ende.
Wir haben erfolgreich gezeigt dass es für jedes Element aus A jeweils irgendein Element aus
B* gibt sodass diese (mindestens) 2 Zahlen gemeinsam haben.
(Mathematisch: Wir haben bewiesen: Für Alle x aus A exisitert ein y aus B: x und y haben 2 Zahlen gemeinsam).

Damit erfüllt auch die verkürzte Lsite B* unsere Bedingung, die Zahlenkombi (1,2,5,6) kann gekickt werden und von nun an ist B=B*; die neue Lsite, die wir im nächsten Durchgang, falls möglich, wieder um eine überflüssige Zahlenkombi bereinigen.

Hier hatten wir glücklich, das erste Element aus B war gleich kickbar.
Hätten wir festgestellt dass ohne (1,2,5,6) nicht mehr Alles "abgedeckt) ist, hätten wir eben dann die Liste B*=B ohne das 2. Element betrachtet.
Und halt so für jedes Element aus B durchprobiert ob wir es weglassen können und das Ganze trotzdem passt.
Entweder würden wir irgendwann ein kickbares lement finden, dann wird das gekickt und fertig für diese Runde.
Oder wir gelangen am Ende von B an und haben eben gezeigt dass B schon eine „optimale“ Liste ist, in der nichts überflüssiges vorkommt.

Zu dem Beispiel:
In Real wäre A eben die Menge aller möglichen Lottozahlen 6 aus 49, also Alles von (1,2,3,4,5,6) bis (44,45,46,47,48,49).
B wäre eine vorgegebene Menge, die unser 3 Richtige Kriterium erfüllt und halt zwangsläufig eine Teilmenge von A ist.

Zwar absolut krank zu tun aber theoretisch könnte man A wie erwähnt setzen, mit B=A beginnen (Also B enthält anfangs alle möglichen Lottozahlen) und dann in mühsamer Kleinarbeit Stück für Stück eine nach der anderen Zahl kicken.

Das würde zwar kein Computer der Welt in hinnehmbarer Zeit schaffen, aber egal.
Wobei Quantencomputer uns da vielleicht helfen könnten in naher Zukunft :slight_smile:

So jedenfalls mein „Algorithmus“, wenn man dieses primitive Vorgehen üebrhaupt so nennen kann.
So zumindest die Grundversion davon

11

Der Übersichtlichkeit halber hier nun mein kürzlicher „Verbesserungsvorschlag“:
Wir interessieren uns ja grundsätzlich für bestimmte 3er Kombis wie bspw. (1,33,49).

Man könnte nun also hingehen und in A und B jedes Element durch eine Lsite seienr 3erkombis ersetzen.
Dann ist in A jeder Listeneintrag eben eine Liste an 3er Kombis.
Programmtechnisch gesprochen ist dann jedes Element aus A eine Liste an Referenzen auf „3Tupel“ Objekte, also sowas wie
(a1,a2,a3,…,a20)

wobei jedes a1i eine Referenz auf ein bestimmtes 3TupelElement ist.

Gleiches kann mn auch in B machen, jedes Element aus B ist dann ebenso eine Lsite an Referenzen auf 3TupelObjekte.
(b1,b2,b3,…,b20)

Will man nun wissen ob ein Element aus A und ein Element aus B 3 Richtige haben, müsste man nur gucken ob eins der ai und eins der bj das selbe 3TupelObjekt referenzieren.

Ob das jetzt viel besser ist als stupides Zahlenvergleichen, weiß ich nicht.
Hoffe halt dass es speichermässig besser ist weil man halt öfters vorkommende 3Tupel nur einmal als Objekt erzeugen muss und die dann von verschiedenen Liasen referenziert werden können.
Obs besser ist, weiß ich nicht. Nur so eine Idee.

Eine Weitere Idee die mir da käme:
Eine Liste aller möglcihen 3Tupel anfertigen.
Und sich irgendwie, separat für A und B, merken, in welchen Zahlenkonbis von A und B das jeweilige 3Tupel vorkommt.
Da könnte man vielleicht halbwegs effizient dann vergleichen

12

Hier mal ein output für den beschriebenen Prozess:

Try to find something that can be removed
draws: 20
    [1, 2, 3]
    [1, 2, 4]
    [1, 2, 5]
    [1, 2, 6]
    [1, 3, 4]
    [1, 3, 5]
    [1, 3, 6]
    [1, 4, 5]
    [1, 4, 6]
    [1, 5, 6]
    [2, 3, 4]
    [2, 3, 5]
    [2, 3, 6]
    [2, 4, 5]
    [2, 4, 6]
    [2, 5, 6]
    [3, 4, 5]
    [3, 4, 6]
    [3, 5, 6]
    [4, 5, 6]
guesses: 6
    [1, 2, 3]
    [1, 2, 4]
    [1, 2, 5]
    [1, 3, 4]
    [1, 3, 5]
    [1, 4, 5]
Try   removing [1, 4, 5]
Found no guess that covers [4, 5, 6]
Can NOT remove [1, 4, 5]
Try   removing [1, 3, 5]
Found no guess that covers [3, 5, 6]
Can NOT remove [1, 3, 5]
Try   removing [1, 3, 4]
Found no guess that covers [3, 4, 6]
Can NOT remove [1, 3, 4]
Try   removing [1, 2, 5]
Found no guess that covers [2, 5, 6]
Can NOT remove [1, 2, 5]
Try   removing [1, 2, 4]
Found no guess that covers [2, 4, 6]
Can NOT remove [1, 2, 4]
Try   removing [1, 2, 3]
Found no guess that covers [2, 3, 6]
Can NOT remove [1, 2, 3]
Found nothing that can be removed
Solution: 6
    [1, 2, 3]
    [1, 2, 4]
    [1, 2, 5]
    [1, 3, 4]
    [1, 3, 5]
    [1, 4, 5]

Bei jedem einzelnen „guess“, den er NICHT entfernt, gibt es einen Grund. Nämlich, dass (wenn man das Element entfernt) irgendeine Ziehung (draw) nicht mehr mit 2 Richtigen abgedeckt ist.

Keines der 6 Elemente, die am Ende aufgelistet sind, kann entfernt werden.

Die richtige Lösung wäre aber

Solution: 2
    [1, 2, 3]
    [4, 5, 6]

Natürlich ist Teil der Ausgabe oben auch

...
Try   removing [4, 5, 6]
For each draw, there is a guess with at least 2 matches
Can     remove [4, 5, 6]
...

Er hat also das „richtige“ Lösungselement [4,5,6] vorher entfernt, weil es immer noch andere gab, mit denen alle Ziehungen „abgedeckt“ waren. Später stellt sich das dann halt als dumm raus. Weil dieses eine Element entfernt wurde, muss man 5 andere Elemente behalten, um die Abdeckung sicherzustellen.

13

Habe nie behauptet dass es allzu effizient ist.
Kann durchaus sein dass sich eine „optimale Liste“ mit 20 Elementen findet, während man, hätte man andere überflüssige Sachen gekickt, auf eine kürzere optimale Liste gekommen wäre.

14

Dann ist hier mal eine Lösung für das Problem:

package bytewelt;

import java.math.BigInteger;
import java.util.AbstractList;
import java.util.List;
import java.util.RandomAccess;

public class CeciNestPasUneListBase
{
    public static void main(String[] args)
    {
        int n = 49;
        int k = 6;
        int minMatches = 3;

        List<List<Integer>> solution = computeSolution(n, k, minMatches);
        System.out.println("Solution: " + solution.size());
        for (List<Integer> guess : solution)
        {
            System.out.println("    " + guess);
        }        
    }

    private static List<List<Integer>> computeSolution(int n, int k, int minMatches)
    {
        return createList(n, k);
    }

    private static List<List<Integer>> createList(int n, int k)
    {
        int size = (int)nChooseK(n, k);
        class Result extends AbstractList<List<Integer>> implements RandomAccess
        {

            @Override
            public List<Integer> get(int index)
            {
                if (index < 0 || index >= size)
                {
                    throw new IndexOutOfBoundsException(
                        "Index must be in [0," + size + "), but is " + index);
                }
                return asList(generate(index, n, k));
            }

            @Override
            public int size()
            {
                return size;
            }
        };
        return new Result();
    }

    private static List<Integer> asList(int array[])
    {
        class Result extends AbstractList<Integer> implements RandomAccess
        {
            @Override
            public Integer get(int index)
            {
                return array[index];
            }

            @Override
            public int size()
            {
                return array.length;
            }
        };
        return new Result();
    }

    private static BigInteger factorial(int n)
    {
        BigInteger f = BigInteger.ONE;
        for (int i = 2; i <= n; i++)
        {
            f = f.multiply(BigInteger.valueOf(i));
        }
        return f;
    }        

    private static long nChooseK(int n, int k)
    {
        BigInteger nf = factorial(n);
        BigInteger kf = factorial(k);
        BigInteger nmkf = factorial(n-k);
        BigInteger divisor = kf.multiply(nmkf);
        BigInteger result = nf.divide(divisor);
        return result.longValue();    
    }

    // See https://math.stackexchange.com/a/1227692
    private static int[] generate(long i, int n, int k)
    {
        int c[] = new int[k];
        long r = i + 1;
        int j = 0;
        for (int s = 1; s < k + 1; s++)
        {
            int cs = j + 1;
            while (r - nChooseK(n - cs, k - s) > 0)
            {
                r -= nChooseK(n - cs, k - s);
                cs += 1;
            }
            c[s - 1] = cs;
            j = cs;
        }
        return c;
    }
}

Das berechnet die Lösung in konstanter Zeit, und mit konstantem Speicherbedarf, unabhängig von der Problemgröße.