array alle möglichen Reihenfolgen

[cybernewb]

hi ich möchte gern ein programm implementieren, welches von einem array, wie zum Beispiel:
A,B,C,D,E,F alle möglichen Kombinationen ausgibt, dabei dürfen aber nur die Buchstaben ausgetauscht werden also zum Beispiel B,A,C,D,E,F oder F,D,E,A,C,B; und soetwas wie A,A,A,B,D,F soll nicht vorkommen. Ich komme leider einfach nicht auf die passende Idee um dies zu implementieren.

ich weiss das es je nach länge des arrays, n! verschiedene kombinationen gibt und das ist auch ok.
Und es ist auch ok wenn ich n Schleifen ineinander setzen müsste.

Nur eines würde nicht gehen, nämlich alles durchlaufen und faule ergebnisse aussortieren denn dass würde n^n Kombinationen ergeben, was zu lange dauern würde.

Das ist übrigens keine Hausaufgabe, sondern dient dazu ein brute force Programm zu erstellen.



Hoffe ihr könnt mir helfen mir fehlt einfach die passende Idee.

 

[hdi]

edit: Oh man du willst ja nicht sowas wie A,A, usw :roll:

Dir ist aber schon klar dass das dann kein Brute Force Algorithmus ist, und demnach auch
zu einer recht grossen Wahrscheinlichkeit den Code niemals knacken wird?

 

[0x7F800000]

import java.util.*;

...

public static <X> List<List<X>> getAllPermutations(List<X> sequence){
		return getAllPermutationsRecursion(sequence, new boolean[sequence.size()], sequence.size());
	}
	
	public static <X> List<List<X>> getAllPermutationsRecursion(List<X> sequence, boolean[] used, int available){
		
		List<List<X>> result=new LinkedList<List<X>>();
		
		if(available!=0){
			int usedIndex=0;
			for(Iterator<X> i=sequence.iterator(); i.hasNext(); usedIndex++){
				X currentElement=i.next();
				if(used[usedIndex]){
					continue;
				}else{
					used[usedIndex]=true;
					for(List<X> permutation:getAllPermutationsRecursion(sequence,used,available-1)){
						permutation.add(currentElement);
						result.add(permutation);
					}
					used[usedIndex]=false;
				}
			}
		}else{
			result.add(new LinkedList<X>());
		}
		return result;
	}


//kleiner test
public static void main(String... _){
		List<String> l=new LinkedList<String>();
		for(char c='A'; c<'F'; c++) l.add(String.valueOf(c));
		System.out.println(getAllPermutations(l));
	}

Funktioniert allerdings nicht für arrays, sondern für listen.
Aber das ist jetzt eher vom rein theoretischen interesse, für bruteforce ist das wenig geeignet. Müsstest du selbst für arrays umschreiben. Vielleicht mach ich's auch noch irgendwann später mal...

 

[cybernewb]

Es geht nicht darum ein Passwort zu knacken, sonst hätte ich keine Probleme einen normalen brute force zu erstellen, nur das Problem ist, dass wenn ich ca. 10 verschiedene Zeichen umsortiere mit nem n! schnellen Verfahren schneller bin als mit dem n^n Verfahren.

 

[0x7F800000]

shit... 10*10! Listen passen schon nicht mehr in den speicher
Ich überleg mir mal, wie man irgendein Iterable basteln kann, das zwar alle permutationen ausgibt, aber diese nicht abspeichert. Momentan habe ich keine ideen ???:L

 

[Marco13]

Jo geht - man kann eine Bijektion ( ) zwischen der Nummer der Permutation und der Permutation selbst aufbauen. Wenn man das nachvollziehen würde (was ich NICHT getan habe) könnte man es ggf. noch effizienter oder schöner machen, aber so hab' ich jetzt einfach mal die Methode von http://en.wikipedia.org/wiki/Permutation#Lexicographical_order_generation in ein Iterable gepackt:

import java.util.*;

class PermutationIterable<T> implements Iterable<T[]>
{

    public static void main(String args[])
    {
        String input[] = new String[]{"A","B","C","D"};
        PermutationIterable<String> pi = new PermutationIterable<String>(input);
        for (String s[] : pi)
        {
            System.out.println(Arrays.toString(s));
        }
    }

    private T input[];
    private int numPermutations = 0;

    public PermutationIterable(T input[])
    {
        this.input = input.clone();
        numPermutations = factorial(input.length);
    }

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

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

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

            // Adapted from [url]http://en.wikipedia.org/wiki/Permutation#Lexicographical_order_generation[/url]
            public T[] next()
            {
                T result[] = input.clone();
                int factorial = numPermutations / input.length;
                for(int i = 0; i < result.length - 1; i++)
                {
                    int tempIndex = (current / factorial) % (result.length - i);
                    T temp = result[i + tempIndex];
                    for(int j = i + tempIndex; j > i; j--)
                    {
                        result[j] = result[j-1];
                    }
                    result[i] = temp;
                    factorial /= (result.length - (i + 1));
                }
                current++;
                return result;
            }

            public void remove()
            {
                throw new UnsupportedOperationException("Forget it");
            }
        };
    }

}

 

[0x7F800000]

:toll: genau sowas hab ich gemeint. Den code hab ich mir nicht genau angeguggt, aber das ist jetzt genau die idee. Von solchen iterables sollte ich mal öfters gebrauch machen.

Etwa für die Potenzmenge damals... Da wäre so eine Vorgehensweise echt angebrachter. Damit wäre deine Methode nochmal einen Tick sinnvoller :applaus: