Algorithmus-Hilfe

[Chasor]

Hallo zusammen.
Ich habe ein 2D-Array "int[][] field", das Zustandswerte von 0 bis 2 speichert.

Ich möchte einen "einfachen" Algorithmus entwickeln, der für das Array mit varibler Länge, ALLE verschiedenen Möglichkeiten des Arrays durchgeht und jede einzelne Möglichkeit mit einer Methode "control()" überprüft.
Die control-Methode habe ich bereits. Wenn das Kontrollergebnis wahr ist, soll das Array in der Möglichkeit, bei der die Kontrolle wahr war, bleiben und ausgegeben werden.
Die Anzahl der benötigten Schritte + Berechnungszeit sollte ausgegeben werden können.

Da ich noch nie einen solchen Algorithmus erstellt habe und google mir auch nicht helfen kann, frage ich hier nach.

(es geht konkret um einen Lösungsalgorithmus für Nonogramme)

 

[Final_Striker]

und was sollen "ALLE verschiedenen Möglichkeiten des Arrays" sein???

 

[Atze]

ich könnte mir unter "alle möglichkeiten" und "variable länge" nur folgendes vorstellen

länge / möglichkeiten
1 - [0],[1],[2]
2 - [0][0],[1][1],[2][2],[0][1],[1][0],[2][0],[0][2],[2][1],[1][2]
usw.

vorstellen. ist das so gemeint?

aber was kontrolliert dann die conrol methode?

 

[Chasor]

Angenommen, das Array ist field[3][3], dann kann:

[0][0] = 0
[0][0] = 1
[0][0] = 2

[0][1] = 0
[0][1] = 1
[0][1] = 2

usw. sein.
Weiterhin sollen dann darunter alle verschiedenen Möglichkeiten, z.B. dass [0][0] = 1 und [0][1] = 2 ist, wäre eine Möglichkeit, eine weitere Möglichkeit wäre [0][0] = 1 und [0][1] = 0, usw.
Sind bestimmt ~100 Möglichkeiten.

Die Control-Methode überprüft dann jede der Möglichkeiten, ob eine davon ein gültiges Ergebnis ist.

Ist etwas schwer zu erklären :/

 

[Marco13]

So ganz sicher, was du meinst, bin ich nicht, poste aber mal wieder den Link zu http://www.java-forum.org/codeschnipsel-u-projekte/81973-combinatorics.html - vielleicht hilft das ja schon...

 

[JohannisderKaeufer]

Sind bestimmt ~100 Möglichkeiten.

Ich komm auf 19683 Möglichkeiten.

Das Array das du beschreibst hat 9 Felder. Jedes Feld kann 3 verschiedene Werte annehmen.
-> es gibt 3 ^ 9 verschiedene Möglichkeiten, wie das Array aussehen kann.

 

[Schumi]

Die Control-Methode überprüft dann jede der Möglichkeiten, ob eine davon ein gültiges Ergebnis ist.

Ist etwas schwer zu erklären :/

Du willst dann prüfen, ob die gegebene Möglichkeit eine aus der Menge aller möglichen ist? Was soll denn dabei rausekommen?

 

[Chasor]

Ich brauche konkret einen Algorithmus, der mir ein "Nonogramm" löst.
Die einfachste Denkweise wäre da, alle Möglichkeiten zu generieren und aus diesen die passende herauszusuchen und auszugeben (bzw. soviele Möglichkeiten durchgehen, bis eine passende gefunden wurde).

Im Internet findet man zum Lösen dieser Nonogramme ein "Line-Solving"-Algorithmus, den ich zwar von der Denkweise her verstehe, aber nicht in JAVA umsetzen kann :/

 

[Marco13]

In meinem Hinterkopf pocht gerade so ein
Constraint Satisfaction Problem
Constraint Satisfaction Problem
Constraint Satisfaction Problem
Constraint Satisfaction Problem
Constraint Satisfaction Problem
Constraint Satisfaction Problem
Constraint Satisfaction Problem
Constraint Satisfaction Problem
Constraint Satisfaction Problem
Constraint Satisfaction Problem
Constraint Satisfaction Problem
Constraint Satisfaction Problem
Constraint Satisfaction Problem
...
Müßte man mal versuchen :reflect:

Wenn du versuchen willst, alles durchzuprobieren, wirst du spätestens bei ... was weiß ich, vielleicht 5x5 großen Rätseln ein Problem bekommen. Abgesehen davon sollte man sich vielleicht eine.... geeignete Datenstruktur dafür überlegen...

 

[ARadauer]

wieso 0,1,2 ? nonogramm oder? ausgefüllt oder nicht ausgefült also 2^9 gar nicht mal so tragisch ;-)

512
aber bei einem 10x10 Raster wirds interessant...
1,26765E+30

 

[Chasor]

Ich brauche immernoch eine Implementierung eines solchen "einfachen" Algorithmusses.

Folgendes Array ist gegeben:

field.array = new int[nCols][nRows];

Ich möchte also in einer For-Next-Schleife (oder While-Schleife) alle Felder durchgehen, diese jeweils mit den Werte "1" oder "2" füttern und jede Möglichkeit eines kompletten Arrays durch die Methode "control()" überprüfen. Wenn die boolean-Variable valid der control()-Methode auf true gesetzt wird, also eine "wahre" Möglichkeit gefunden wurde, soll dieses richtige Array durch meine paintComponent()-Methode gezeichnet werden.

Würde mir schon reichen, wenn ich wüsste, wie ich alle Möglichkeiten generiere und nach jeder kompletten Möglichkeit die Methode control() starten kann.


MfG

 

[Marco13]

Warum denn 1 und 2? Am Anfang stehen im Array lauter 0en, wenn man davon ausgeht, dass dort nicht 1 und 2 sondern 0 und 1 durchprobiert werden soll, könnte man sowas machen wie

int i=0; 
int j=0;
while (true)
{
    if (array[i][j]==0) array[i][j]=1;
    else // array[i][j]==1
    {
        array[i][j] = 0;
        j++;
        if (j==nRows)
        {
            j=0;
            i++;
            if (i==nRows) 
            {
                i=0;
            }
        }
        array[i][j]=1;
    }
    boolean done = control(array);
    if (done) return;
}

(ungetestet, nur schnell hingehackt)

Wenn es unbedingt 1 und 2 sein soll, kannst du das ja anpassen. Es KÖNNTE natürlich sein, dass du dazu NACHDENKEN musst (tut mir schrecklich leid...)

 

[Chasor]

Das ganze macht dann letztendlich aus den 1en 2en, geht zum nächsten, setzt diesen 2, den Vorgänger wieder 1, und wieder so weiter. Damit ist jeweils immer nur 1 Feld im Array mit dem Wert 2 besetzt. Es wird auch immer der gleiche Vorgang durchgeführt, somit können nicht alle Statusmöglichkeiten des Feldes durchgegangen werden :/ ...

 

[Ziegenpeter]

Könntest du mal erläutern wofür du dir gedacht hast die 0,1 und 2 zu brauchen? Ich meine du erklärst zwar, dass du das so machen willst und man dir doch bitte helfen soll, allerdings haben glaub ich die wenigsten verstanden wofür du die 2 brauchst.

 

[Chasor]

0 = Leeres Feld
1 = ausgefülltes Feld
2 = gepunktetes Feld

Es darf am Ende kein leeres Feld mehr da sein, und das Ergebnis muss durch die Kontrolle stimmen.
Es sollen also alle möglichen Feld-Variationen erstellt und geprüft werden.

 

[Marco13]

Ja, so ganz stimmte der Code noch nicht - waurm sollte ich mir auch die Mühe (nochmal) machen. Schau' dir das CombinationIterable aus dem oben schon geposteten Link an, das macht GENAU das, was du willst. Das dann in einen Array zu packen ist dein Job.

 

[Marco13]

Jetzt kannst du stolz auf dich sein: DU HAST ES GESCHAFFT

import java.util.*;

public class CombinationStuff
{

    public static void main(String args[])
    {
        int nRows = 3;
        int nCols = 3;
        int a[][] = new int[nRows][nCols];
        Integer input[] = new Integer[] { 0, 1, 2 };
        CombinationIterable<Integer> ci =
            new CombinationIterable<Integer>(nRows*nCols, input);
        for (Integer s[] : ci)
        {
            fill(s,a);
            control(a);
        }
    }

    private static void fill(Integer s[], int a[][])
    {
        int index = 0;
        for (int i=0; i<a.length; i++)
        {
            for (int j=0; j<a[i].length; j++)
            {
                a[i][j] = s[index];
                index++;
            }
        }
    }

    private static boolean control(int a[][])
    {
        System.out.println("Control");
        for (int i=0; i<a.length; i++)
        {
            System.out.println(Arrays.toString(a[i]));
        }
        return false;
    }



}


/**
 * A class providing an iterator over all combinations of a certain number
 * of elements of a given set. For a set S with n = |S|, there are are n^k
 * combinations of k elements of the set. This is the number of possible
 * samples when doing sampling with replacement. Example:<br />
 * <pre>
 * S = { A,B,C }, n = |S| = 3
 * k = 2
 * m = n^k = 9
 *
 * Combinations:
 * [A, A]
 * [A, B]
 * [A, C]
 * [B, A]
 * [B, B]
 * [B, C]
 * [C, A]
 * [C, B]
 * [C, C]
 * </pre>
 *
 * @author [url]http://www.java-forum.org/members/Marco13.html[/url]
 */
class CombinationIterable<T> implements Iterable<T[]>
{
    private T input[];
    private int sampleSize;
    private int numElements;

    /**
     * Creates an iterable over all multisets of
     * 'sampleSize' elements of the given array.
     *
     * @param sampleSize
     * @param input
     */
    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()
            {
                // The array of 'chosen' elements for a set of size n
                // effectively is a number represented in k-ary form,
                // and thus, this method does nothing else than count.
                // For example, when choosing 2 elements of a set with
                // n=10, the contents of 'chosen' would represent all
                // values
                // 00, 01, 02,... 09,
                // 10, 11, 12,... 19,
                // ...
                // 90, 91, 92, ...99
                // with each digit indicating the index of the element
                // of the input array that should be placed at the
                // respective position of the output array.
                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");
            }
        };
    }
}



/**
 * A class providing an iterator over all combinations of a certain number
 * of elements from a given set, ignoring the order of the elements. For
 * a set S with n = |S|, there are are (n+k-1)/(k!*(n-1)!) ways of
 * choosing k elements from the set when the order of the elements in the
 * resulting set should be ignored. This is, for example, the number of
 * distinct results when throwing k dices with n sides. Example:<br />
 * <pre>
 * S = { A,B,C,D }, n = |S| = 4
 * k = 2
 * m = (n+k-1)/(k!*(n-1)!) = 10
 *
 * Unordered combinations of length 2:
 * [A, A]
 * [A, B]
 * [A, C]
 * [A, D]
 * [B, B]
 * [B, C]
 * [B, D]
 * [C, C]
 * [C, D]
 * [D, D]
 * </pre>
 *
 * @author [url]http://www.java-forum.org/members/Marco13.html[/url]
 */
class UnorderedCombinationIterable<T> implements Iterable<T[]>
{
    private T input[];
    private int length;
    private int numElements;
    private Integer positions[];

    public static int factorial(int n)
    {
        int f = 1;
        for (int i = 2; i <= n; i++)
        {
            f *= i;
        }
        return f;
    }

    public UnorderedCombinationIterable(int length, T... input)
    {
        this.length = length;
        this.input = input.clone();

        numElements = factorial(input.length + length - 1) /
            (factorial(length) *
                factorial(input.length - 1));

        int numPositions = length + input.length - 1;
        positions = new Integer[numPositions];
        for (int i = 0; i < numPositions; i++)
        {
            positions[i] = i;
        }
    }

    public Iterator<T[]> iterator()
    {
        return new Iterator<T[]>()
        {
            private int current = 0;
            private Iterator<Integer[]> positionChoiceIterator;

            // Initialization of the positionChoiceIterator
            {
                ChoiceIterable<Integer> positionChoiceIterable =
                    new ChoiceIterable<Integer>(length, positions);
                positionChoiceIterator = positionChoiceIterable.iterator();
            }

            public boolean hasNext()
            {
                return current < numElements;
            }

            public T[] next()
            {
                current++;
                return toSelection(positionChoiceIterator.next());
            }

            private T[] toSelection(Integer positionChoice[])
            {
                // Selecting k elements from n elements, ignoring the
                // order of the selected elements, may be formulated
                // as selecting k elements from (n+k-1) elements
                // obeying the order.
                // The positionChoiceIterator provides choices of k
                // elements from (n+k-1) elements, and they are converted
                // to the corresponding selection of elements here.
                //
                // For example:
                // 4 elements should be selected from a set of 6 elements,
                // and the order of the selected elements is not relevant
                // (like when rolling 4 six-sided dices).
                // The positionChoiceIterator will be used for choosing
                // 4 elements from (6+4-1)=9 elements. If it provides the
                // choice 0,3,4,7 then this will be translated into a
                // selection in the following way:
                //
                // Positions array                        : 012345678
                // Choice done by positionChoiceIterator  : 0  34  7
                // For interpreting this choice, place
                // asterisks at the respective positions
                // filling the remaining positions with
                // consecutive numbers                    : *12**34*5
                // This pattern can then be interpreted as...
                // - take 0 once
                // - take 2 twice
                // - take 4 once
                // resulting the the selection 0,2,2,4

                @SuppressWarnings("unchecked")
                T result[] = (T[]) java.lang.reflect.Array.newInstance(
                    input.getClass().getComponentType(), length);

                int currentValue = 0;
                int currentIndex = 0;
                for (int x = 0; x < positions.length; x++)
                {
                    if (x == positionChoice[currentIndex])
                    {
                        result[currentIndex] = input[currentValue];
                        currentIndex++;
                    }
                    else
                    {
                        currentValue++;
                    }
                    if (currentIndex >= positionChoice.length)
                    {
                        break;
                    }
                }
                return result;
            }

            public void remove()
            {
                throw new UnsupportedOperationException(
                    "May not remove elements from a combination");
            }
        };
    }
}



class ChoiceIterable<T> implements Iterable<T[]>
{
    private T input[];
    private int sampleSize;
    private int numElements;

    public static int factorial(int n)
    {
        int f = 1;
        for (int i = 2; i <= n; i++)
        {
            f *= i;
        }
        return f;
    }

    /**
     * Creates an iterable over all choices of 'sampleSize'
     * elements taken from the given array.
     *
     * @param sampleSize
     * @param input
     */
    public ChoiceIterable(int sampleSize, T... input)
    {
        this.sampleSize = sampleSize;
        this.input = input.clone();

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

    public Iterator<T[]> iterator()
    {
        return new Iterator<T[]>()
        {
            private int current = 0;
            private int chosen[] = new int[sampleSize];

            // Initialization of first choice
            {
                for (int i = 0; i < sampleSize; i++)
                {
                    chosen[i] = i;
                }
            }

            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]];
                }
                current++;
                if (current < numElements)
                {
                    increase(sampleSize - 1, input.length - 1);
                }
                return result;
            }

            private void increase(int n, int max)
            {
                // The fist choice when choosing 3 of 5 elements consists
                // of 0,1,2. Subsequent choices are created by increasing
                // the last element of this sequence:
                // 0,1,3
                // 0,1,4
                // until the last element of the choice has reached the
                // maximum value. Then, the earlier elements of the
                // sequence are increased recursively, while obeying the
                // maximum value each element may have so that there may
                // still be values assigned to the subsequent elements.
                // For the example:
                // - The element with index 2 may have maximum value 4.
                // - The element with index 1 may have maximum value 3.
                // - The element with index 0 may have maximum value 2.
                // Each time that the value of one of these elements is
                // increased, the subsequent elements will simply receive
                // the subsequent values.
                if (chosen[n] < max)
                {
                    chosen[n]++;
                    for (int i = n + 1; i < sampleSize; i++)
                    {
                        chosen[i] = chosen[i - 1] + 1;
                    }
                }
                else
                {
                    increase(n - 1, max - 1);
                }
            }

            public void remove()
            {
                throw new UnsupportedOperationException(
                    "May not remove elements from a choice");
            }
        };
    }
}

 

[Chasor]

Ist mir zu kompliziert und unverständlich als JAVA-Anfänger ... trotzdem Danke für deine Mühe und "Freundlichkeit" =).

Wieso muss so ein "einfacher" Denkvorgang für alle Möglichkeiten so schwer umsetzbar sein? :/
Da muss es doch eine einfachere Möglichkeit geben...

 

[Marco13]

Geht auch einfacher. Wenn du Parallelen zu dem erkennst, was ich oben schon gepostet habe, denk' mal drüber nach, woran das liegen könnte.

Das Programm gibt auch ein paar desillusionierende Informationen aus. Auf meinem (recht alten) Rechner würde die Überprüfung eines 5x5-Feldes (wenn man davon ausgeht, dass die control-Methode KEINE Rechenzeit benötigt) etwas mehr als einen Monat dauern.

import java.util.*;

class CombinationStuff2
{
    static int nRows = 5;
    static int nCols = 5;
    static int max = 2;
    static long controlCount = 0;
    static long totalCount = (long)Math.pow(max+1, nRows*nCols);
    static long startTime = 0;

    public static void main(String args[])
    {
        startTime = System.currentTimeMillis();
        int a[][] = new int[nRows][nCols];
        boolean increased = true;
        while (increased)
        {
            control(a);
            increased = increase(a,0,0);
        }
    }

    private static boolean increase(int a[][], int r, int c)
    {
        a[r][c]++;
        if (a[r][c]<=max)
        {
            return true;
        }
        else
        {
            a[r][c]=0;
            c++;
            if (c==nCols)
            {
                c=0;
                r++;
                if (r==nRows)
                {
                    return false;
                }
            }
            return increase(a, r, c);
        }
    }

    private static boolean control(int a[][])
    {
        controlCount++;
        double donePercent = 100.0*controlCount/totalCount;
        double durationMS = System.currentTimeMillis()-startTime;
        double remainingMS = (100.0/donePercent) * durationMS - durationMS;
        double remainingH = remainingMS / (1000*60*60);
        System.out.println("Done "+String.format("%.2f", donePercent)+"%");
        System.out.println("Duration "+String.format("%.2f", (durationMS/1000))+" seconds");
        System.out.println("Remaining "+String.format("%.2f", (remainingMS/1000))+" seconds");
        System.out.println("          "+String.format("%.2f", (remainingH))+" hours");
        for (int i=0; i<a.length; i++)
        {
            System.out.println(Arrays.toString(a[i]));
        }
        return false;
    }
}

Und sei freundlich zu deinem Prüfer, dann kriegst du vielleicht eine bessere Note.

 

[JohannisderKaeufer]

Jetzt machen wir aus dem field[n][m], sowas

field[n*m]

jetzt stellen wir uns vor field[n*m] sei eine n*m-Stellige Zahl mit führenden 0en und sei desweiteren eine Zahl zur Basis 3.

Jetzt kann man alle Werte in [n*m] auf 0 setzen.

Nun geht man hin und fängt an zu zählen.

Also erhöht man die letzte Ziffer um 1.
Bspl.
field[3][3]

field[3*3]

field = {0,0,0,0,0,0,0,0,0}

[0,0,0,0,0,0,0,0,0]

um 1 erhöhen

[0,0,0,0,0,0,0,0,1]

um 1 erhöhen

[0,0,0,0,0,0,0,0,2]

um 1 erhöhen

[0,0,0,0,0,0,0,0,3] drei ist zugroß deshalb 3 gleich 0 und macht einen Übertrag

[0,0,0,0,0,0,0,1,0]

um 1 erhöhen

[0,0,0,0,0,0,0,1,1]

...

 

[Marco13]

Genau das wird oben gemacht Genaugenommen könnte man ja auch einfach (3^(x*y) mal) sowas wie

String s = Long.toString(n, 3);

machen und den String in den Array umwandeln, aber ... joa... :bahnhof: