turrex0100
Goto Top

Strings aus char Array generieren

Hallo Forum,

Ich bin auf der Suche nach einem Algorithmus um aus einem gegebenen char Array
alle möglichen Buchstabenkombinationen einer länge k in ein String Array zu schreiben.

Ein beispiel:

Char array enthält: 'a','b','c'
k = 2
dann soll das String Array so aussehen: "ab","ac","ba","bc","cb","ca"


Im Prinzip ist das Ganze doch ein Auswahlproblem quasi "ziehen ohne zurücklegen"
wie zb Lotto somit müsste die Anzahl der Kombinationen n über k sein.


die Länge des Char Arrays und der Wert von k kann dabei unterschiedlich sein.

Leide hab ich noch keine richtige Idee wie ich das Problem lösen kann.
Gibt es bereits einen solchen Algorithmus den ich nur noch implementieren muss,
oder habt ihr vielleicht irgendwelche Ideen?

Gruss Malte.

Content-Key: 207402

Url: https://administrator.de/contentid/207402

Printed on: April 25, 2024 at 15:04 o'clock

Member: colinardo
colinardo Jun 03, 2013 updated at 18:57:11 (UTC)
Goto Top
Hallo Malte,
das gleiche Problem wird hier diskutiert, ist zwar für VB aber lässt sich sicher auch in Java umsetzen:
http://www.tutorials.de/visual-basic-6-0/260088-algorithmus-fuer-kombin ...

Grüsse Uwe
Member: colinardo
colinardo Jun 05, 2013 updated at 12:41:42 (UTC)
Goto Top
Das was du suchst nennt sich Permutation, bin zwar kein Java-Profi aber das hier müsste funktionieren(p.s. ist nicht sehr performant):
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.Set;

public class GenerateCombinations {

    public static String chars = "ABCDEFGH";  
    public static int anzahl = 2;
    
    public static void main(String Args){
        PermutationGenerator generator = new PermutationGenerator(chars,anzahl);
        ArrayList<String> permutations = generator.getPermutations();
        Set<String> s = new LinkedHashSet<String>(permutations);
        System.out.println(s);
    }
}
class PermutationGenerator {

    private String string;
    private ArrayList<String> permutations;
    private int MaxLengthOfFinalString;

    public PermutationGenerator(String string, int laenge) {
        this.string = string;
        this.permutations = new ArrayList<String>();
        this.MaxLengthOfFinalString = laenge;
    }

    public ArrayList<String> getPermutations() {
        permutation("", this.string);  
        return this.permutations;
    }

    private void permutation(String prefix, String str) {
        int n = str.length();
        if (n == 0) {
            this.permutations.add(prefix.substring(0,MaxLengthOfFinalString));
        } else {
            for (int i = 0; i < n; i++) {
                permutation(prefix + str.charAt(i), str.substring(0,i) + str.substring(i+1,n));
            }
        }
    }
}

Grüße Uwe