# Permutationen mit Einschränkungen



## H2SO4 (2. Okt 2009)

Hallo!

Ich habe mal wieder ein Problem, dass mir arge Schwierigkeiten bereitet. Auch wenn es mehroder weniger nur Just for Fun ist, aber das steht hier nciht zur Debatte 

Folgendes:

Ich habe eine MySQL-Datenbank mit einer Tabelle, die folgendermaßen aufgebaut ist:

id, a, b, c, d, e, f
Primary-Key für id
und ein INDEX über (a, b, c, d, e, f)

Mein Ziel ist es, alle Lotto-Kombinationen zu generieren und in die Datenbank einzutragen. Jup, sind viele 


Zum generieren der Kombinationen habe ich die untenstehende Klasse verwendet. Funktioniert auch so weit, nur habe ich folgendes Problem:

Die Kombinationen werden so gebildet:
1 1 1 1 1 2
...
1 1 1 1 1 49
1 1 1 1 2 1
...
1) alles keine gültigen Lottozahlen s. Code

1 2 3 4 5 6 erste gültige Kombination
...
1 2 3 4 5 49
...
1 2 3 4 6 1
...
1 2 3 4 6 5 
gültige Kombination, sortieren, Problem: es gab sie schon. Deshalb wird vor jedem Einfügen in die Datenbank die Existenz der Kombination überprüft, was, wie ihr euch vorstellen könnt, immmmmmmer länger dauert.


```
LottoCombinationsDatabase l = new LottoCombinationsDatabase();
Integer input[] = l.getNumbers();        

CombinationIterable<Integer> ci = new CombinationIterable<Integer>(6, input);       

for (Integer s[] : ci) {
    //Gibt es doppelte Zahlen? 1)
    if (l.uniqueIntegerArray(s)) {
        //aufsteigend sortieren
        l.bubbleSort(s);

        //existiert die Kombination in der DB?
        if (!l.existsCombination(s)) {
            l.insertCombination(s);
        }
    }
}
```

Was ich nun möchte:

Alle Lottozahlen generieren, ohne doppelte Zahlen und Wiederholungen. Wie lässt sich das realisieren?

Nocheinmal: Der Grund/Sinn/etc. ist ja egal. Mir gehts nur um das Problem.




```
package lotto;

import java.util.*;

class CombinationIterable<T> implements Iterable<T[]>
{
    private T input[];
    private int sampleSize;
    private int numElements;
 
    public CombinationIterable(int sampleSize, T... input)
    {
        this.sampleSize = sampleSize;
        this.input = input.clone();
        numElements = (int) Math.pow(input.length, sampleSize);
    }
 
    public Iterator<T[]> iterator()
    {
        return new Iterator<T[]>()
        {
            private int current = 0;
            private int chosen[] = new int[sampleSize];
 
            public boolean hasNext()
            {
                return current < numElements;
            }
 
            public T[] next()
            {
                @SuppressWarnings("unchecked")
                T result[] = (T[]) java.lang.reflect.Array.newInstance(
                    input.getClass().getComponentType(), sampleSize);
                for (int i = 0; i < sampleSize; i++)
                {
                    result[i] = input[chosen[i]];
                }
                increase();
                current++;
                return result;
            }
 
            private void increase()
            {
                int index = chosen.length - 1;
                while (index >= 0)
                {
                    if (chosen[index] < input.length - 1)
                    {
                        chosen[index]++;
                        return;
                    }
                    else
                    {
                        chosen[index] = 0;
                        index--;
                    }
                }
            }
 
            public void remove()
            {
                throw new UnsupportedOperationException(
                    "May not remove elements from a combination");
            }
        };
    }
}
```


----------



## 0x7F800000 (2. Okt 2009)

du brauchst also alle Elemente aus (M^k)/~ wobei M endliche Menge und für zwei tupel gilt: x~y genau dann wenn (x sortiert) = (y sortiert) . Okay, mal sehen was sich da tun lässt. Ich schau's mir mal so um 16:00 an... *faulheit ftw*


----------



## Marco13 (2. Okt 2009)

Wenn ich das richtig sehe, ist das, was du suchst, nicht das CombinationIterable sondern das ChoiceIterable ?!


----------



## H2SO4 (2. Okt 2009)

0x7F800000 hat gesagt.:


> du brauchst also alle Elemente aus (M^k)/~ wobei M endliche Menge und für zwei tupel gilt: x~y genau dann wenn (x sortiert) = (y sortiert) . Okay, mal sehen was sich da tun lässt. Ich schau's mir mal so um 16:00 an... *faulheit ftw*



Genau  Cool, dass du mal rüber schaust.




Marco13 hat gesagt.:


> Wenn ich das richtig sehe, ist das, was du suchst, nicht das CombinationIterable sondern das ChoiceIterable ?!



Ich hatte schonmal eine Ähnliche Anfrage gestellt. Damals empfahl man mir das CombiI. Werde aber das andere mal austesten.


----------



## Marco13 (2. Okt 2009)

Und ich hatte es damals schon gesagt: http://www.java-forum.org/java-basi...63-kombinationsmoeglichkeiten.html#post557921


----------



## H2SO4 (2. Okt 2009)

Nur das es daran scheitern wird, dass 49! von Java nicht mehr zu berechnen ist. Zumindest bei mir nicht 

Für den Wert kommt immer div/0 raus. zB als Länge 10 geht ohne Probleme


```
numElements = Combinatorics.factorial(input.length) /
            (Combinatorics.factorial(sampleSize) * 
                Combinatorics.factorial(input.length - sampleSize));
```


----------



## Marco13 (2. Okt 2009)

Oh ja - das jetzt auf BigInteger umzustellen wäre etwas frickelig  
@Andrey: Soll ich die PM auspacken, die du mir neulich geschickt hast?


----------



## 0x7F800000 (3. Okt 2009)

Marco13 hat gesagt.:


> @Andrey: Soll ich die PM auspacken, die du mir neulich geschickt hast?


Öhm... "neulich"? War das dieser Vorschlag zur schmerzlosen Übersetzung von Recursionsergebnissen in Iterables mittels zusätzlicher Threads? Ja, "neulich", hehe^^  Wenn diese Diskussion gemeint ist, dann kannst du natürlich nach eigenem Ermessen auspacken was du möchtest, allerdings könnte dich folgende direktere Lösung für dieses spezielle Problem interessieren:


```
import java.util.*;

import static java.util.Collections.*;
import static java.lang.System.*;

public class _ {
	
	//help method
	/*
	 * This method returns three kinds of Iterables.
	 * All this Iterables are nodes or leafs of a tree consisting of such iterables.
	 * Result is an Iterable that returns all the possibilities to fill a tuple of specified size
	 * with remaining elements of an ArrayList m, where by "remaining elements" i mean all elements
	 * from startIndex to the last Element.
	 * 
	 * For example call with Arguments ({0,2,3,4,5},4,2) returns the same tuples as call ({4,5},0,2):
	 * ->
	 * {4,4}
	 * {4,5}
	 * {5,5}
	 * 
	 * First kind of returned Iterable is a List containing just an empty List (tuple of size 0):
	 * -> List(List())
	 * This Iterable is returned, if tupleSize is 0. Size of m does not matter. ["Leaf"]
	 * 
	 * Second kind of returned Iterable is a List containing single List with many copies of same element:
	 * -> List(List(x,x,x,x,x,x,x,x,x)) 
	 * where x appears "toupleSize"-times. This iterable is returned, when m contains only one element.
	 * The specified tupleSize does not matter. ["Leaf"]
	 * 
	 * The third kind of returned Iterable is a "Node": it saves iterators of Tterables of "lower order".
	 * It divides m in "head and tail":  m = head+tail = {h}+{t1,t2,t3...t_x}
	 * then it creates for each integer filledPositions=0...tupleSize an Iterable of "lower order".
	 * This Iterable of lower order must for each filledPositions create all tuples of length 
	 * (tupleSize-filledPositions) out of tail-elements {t1,t2,...,t_x}.
	 *
	 * So the node returns something like this:
	 * {t		| where t are all tuples of length tupleSize     made out of {t1,t2...t_x} } and
	 * {h+t		| where t are all tuples of length (tupleSize-1) made out of {t1,t2...t_x} } and
	 * {h,h+t	| where t are all tuples of length (tupleSize-2) made out of {t1,t2...t_x} } and
	 * {h,h,h+t	| where t are all tuples of length (tupleSize-3) made out of {t1,t2...t_x} } and
	 * ...
	 * {h...h+t	| where h appears tupleSize-times and t is an empty tuple }
	 */
	private static <T> Iterable<LinkedList<T>> sortedCartesianProductRec(
			final ArrayList<T> m,
			final int startIndex,
			final int tupleSize){
		
		if(tupleSize==0){
			List<LinkedList<T>> result=new LinkedList<LinkedList<T>>();
			result.add(new LinkedList<T>());
			return result;
		}else if(startIndex==m.size()-1){
			List<LinkedList<T>> result=new LinkedList<LinkedList<T>>();
			LinkedList<T> homogeneousBlock=new LinkedList<T>();
			for(int k=0; k<tupleSize; k++) homogeneousBlock.add(m.get(startIndex));
			result.add(homogeneousBlock);
			return result;
		}else{
			return new Iterable<LinkedList<T>>(){
				@Override public Iterator<LinkedList<T>> iterator() {
					return new Iterator<LinkedList<T>>(){
						private int filledPositions=0;
						private Iterator<LinkedList<T>> innerIterator
							=sortedCartesianProductRec(m,
									startIndex+1,
									tupleSize
							).iterator();
						@Override public boolean hasNext() {
							if(filledPositions<tupleSize){
								return true;
							}else{
								return innerIterator.hasNext();
							}
						}

						@Override public LinkedList<T> next() {
							if(innerIterator.hasNext()){
								LinkedList<T> res=innerIterator.next();
								for(int i=0; i<filledPositions; i++) 
									res.addFirst(m.get(startIndex));
								return res;
							}else{
								filledPositions++;
								innerIterator
									=sortedCartesianProductRec(m,
											startIndex+1,
											tupleSize-filledPositions
									).iterator();
								return next();
							}
						}

						@Override public void remove() { 
							throw new UnsupportedOperationException("no remove"); 
						}
					};
				}
			};
		}
	}
	
	/* returns m^k/~ as Iterable (where ~ is equality after sorting)
	 * for example:
	 * m={1,2} k=3
	 * m^k/~ = {
	 *   (1,1,1)
	 *   (1,1,2)
	 *   (1,2,2)
	 *   (2,2,2)
	 * }
	*/
	public static <T> Iterable<LinkedList<T>> sortedCartesianProduct(
			final Set<T> m,
			final int k){
		
		return sortedCartesianProductRec(new ArrayList<T>(m),0,k);
	}
	
	public static void main(String... args){
		Set<Integer> m=new TreeSet<Integer>();
		for(int i=1; i<=49; i++) m.add(i);
		for(List<Integer> l:sortedCartesianProduct(m,6)){
			out.println(l);
		}
	}
}
```
:exclaim:Ausführung dauert viertel Stunde, das sind viiile Kombis!:exclaim:

Der Witz hierbei ist, dass ich weder Iterationen, noch parallel laufende Rekursionen verwende, sondern stattdessen _gleichartige Iterables baumartig verschachtle_. Das kommt diesem deinem Vorschlag aus dem ersten Absatz der letzten PM der besagten Diskussion eigentlich am nächsten 





			
				Marco13 hat gesagt.:
			
		

> Ja, habe gerade nochmal ganz kurz(!) versucht, das iterativ zu machen. Rein formal ist das ja einfach: Man legt einfach auf einen Stack, was normalerweise die JVM bei einem Methodenaufruf "automatisch" auf den Stack legen würde. Aber das, was man da rauf legt, muss eben ein alles beschreibendes "Zustandsobjekt" sein, und das dann "auf Anfrage hin" in den nächsten Zustand zu bringen ist schon ein bißchen fummeling.


Die baumartig verschachtelten Iterables ähneln gewissermaßen den dort beschriebenen Stack-Objekten, die den gesammten Zustand abspeichern und auf Nachfrage "weiterklicken".

@H2S04: Ja, 16:00^^ Sorry, war davor zu demotiviert... 

edit: Zitat eingefügt


----------



## Marco13 (3. Okt 2009)

Du darfst zitieren, was du willst ... Das gepostete müßte ich bei Gelegenheit mal nachvollziehen, aber das bezieht sich ja auf eine spätere Diskussion - die Sache mit den ""Raumfüllenden" Kurven", oder?


----------



## 0x7F800000 (3. Okt 2009)

Marco13 hat gesagt.:


> Du darfst zitieren, was du willst ...


Hab jetzt den Absatz als Zitat eingefügt, so wird's hoffentlich klarer wovon ich hier geredet habe. 



> Das gepostete müßte ich bei Gelegenheit mal nachvollziehen


Aah, aufgrund der (wie immer miesen) "strategischen Kommentierung" ist das hier evtl. wieder weniger angenehm  

Ws ich hier eigentlich nur demonstrieren wollte: dein Vorschlag, die Elemente des Call-Stacks bei einer Rekursion durch eigene, zustandsspeichernde Objekte zu ersetzen, ist auch in der Praxis durchaus anwendbar und gar nicht so übertrieben "fummelig".


> aber das bezieht sich ja auf eine spätere Diskussion - die Sache mit den ""Raumfüllenden" Kurven", oder?


Ne, grad das meinte ich nicht. Ich meinte die reihe von PM's unter dem Titel "Combinatorics", wo ich noch eine andere Art beschrieben habe, wie man mithilfe einer blockenden Queue und eines parallelen Threads ergebnisse der Rekursion leicht in Iterable verpacken kann.


----------



## Marco13 (3. Okt 2009)

Das mit dem "das bezog sich auf die Rumfüllenden Kurven" bezog sich auf das, was der gepostete Code ausrechnet  Muss ich mir wirklich mal genauer ansehen...


----------



## 0x7F800000 (3. Okt 2009)

Marco13 hat gesagt.:


> Das mit dem "das bezog sich auf die Rumfüllenden Kurven" bezog sich auf das, was der gepostete Code ausrechnet  Muss ich mir wirklich mal genauer ansehen...


Ne, das ist wieder was anderes. Hier wird das kartesische Produkt von derselben endlichen menge mit sich selbst genommen, und dazu werden die Tupel auch noch sortiert. Das mit Raumfüllenden Kurven bezog sich auf eine etwas andere Situation: dort betrachtete man das kartesische Produkt von _unterschiedlichen_ Mengen, und dazu nicht endlich zu sein brauchten. 

Das sind alles variationen vom selben Liedchen, und mir fällt es mit jedem mal schwerer, einen einigermaßen passenden namen zu finden. ;(

falls es sich jemand den code mal anschauen will: habe jetzt ein breites ausführliches Kommentar zur Idee eingefügt, das dürfte hilfreich sein. And sorry for my friggin awfu1 inglisch^^ :rtfm: (auf deutsch kann ich's doch auch nich)


----------



## H2SO4 (3. Okt 2009)

Hallo!

Ich habe es jetzt endlich mit dem ChoiceIt. hinbekommen.

Vielleicht könnt ihr mir noch eine Frage beantworten?

Warum nimmt der Speicherbedarf des Programms immer weiter zu? Natürlich bricht es irgendwann ab (Java heap space...).


```
package lotto;

import java.util.*;

import java.sql.*;

public class LottoCombinationsDatabase {

    public final static String DRIVER = "com.mysql.jdbc.Driver";
    public final static String SERVER = "localhost";
    public final static String DATABASE = "test";
    public final static String USER = "root";
    public final static String PASSWORD = "";
    private Connection cn = null;
    private Integer[] numbers;

    public LottoCombinationsDatabase() {
        this.numbers = new Integer[49];

        for (int i = 0; i < this.numbers.length; i++) {
            this.numbers[i] = new Integer(i + 1);
        }

        this.mysqlStart();
    }

    private void mysqlStart() {
        try {
            Class.forName(LottoCombinationsDatabase.DRIVER);
            this.cn = DriverManager.getConnection("jdbc:mysql://" + LottoCombinationsDatabase.SERVER + ":3306/"
+ LottoCombinationsDatabase.DATABASE ,
 LottoCombinationsDatabase.USER, LottoCombinationsDatabase.PASSWORD);
        }
        catch (Exception e) {
            System.out.println(e);
        }
    }

    private void mysqlClose() {
        try {
            if(this.cn != null)
            	this.cn.close();
        }
        catch (Exception e) {
        }
        
        this.cn = null;
    }

    public Integer[] getNumbers() {
        return this.numbers;
    }

    public void insertCombination(Integer[] i) {
        try {
            Statement st = this.cn.createStatement();
            st.executeUpdate(
                "INSERT INTO combos (a, b, c, d, e, f) VALUES(" + i[0] + ", " + i[1] + ", " + i[2] + ", " + i[3] + ", " + i[4] + ", " + i[5] + ")"
            );
            st = null;
        }
        catch (Exception e) {
            System.out.println(e);
        }
    }

    public static void main(String[] args) {
        int k = 6;

        LottoCombinationsDatabase l = new LottoCombinationsDatabase();

        Integer input[] = l.getNumbers();

        ChoiceIterable<Integer> ci = new ChoiceIterable<Integer>(k, input);


        for (Integer s[] : ci) {
            l.insertCombination(s);                // Hier wird immer ausgestiegen
        }

        l.mysqlClose();
    }
}
```


----------

