Générer toutes les permutations d'une chaîne donnée

Question

Quel est le moyen le plus élégant de trouver toutes les permutations d'une chaîne de caractères ? Par exemple, la permutation de ba serait ba et ab mais qu'en est-il des chaînes plus longues telles que abcdefgh ? Existe-t-il un exemple de mise en œuvre en Java ?

Answer 1

public static void permutation(String str) { 
    permutation("", str); 
}

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}

(via Introduction à la programmation en Java )

Answer 2

Utilisez la récursion.

• Essayez chacune des lettres à tour de rôle comme première lettre, puis trouvez toutes les permutations des lettres restantes en utilisant un appel récursif.
• Le cas de base est le suivant : lorsque l'entrée est une chaîne vide, la seule permutation est la chaîne vide.

Answer 3

Voici ma solution qui est basée sur l'idée du livre "Cracking the Coding Interview" (P54) :

/**
 * List permutations of a string.
 * 
 * @param s the input string
 * @return  the list of permutations
 */
public static ArrayList<String> permutation(String s) {
    // The result
    ArrayList<String> res = new ArrayList<String>();
    // If input string's length is 1, return {s}
    if (s.length() == 1) {
        res.add(s);
    } else if (s.length() > 1) {
        int lastIndex = s.length() - 1;
        // Find out the last character
        String last = s.substring(lastIndex);
        // Rest of the string
        String rest = s.substring(0, lastIndex);
        // Perform permutation on the rest string and
        // merge with the last character
        res = merge(permutation(rest), last);
    }
    return res;
}

/**
 * @param list a result of permutation, e.g. {"ab", "ba"}
 * @param c    the last character
 * @return     a merged new list, e.g. {"cab", "acb" ... }
 */
public static ArrayList<String> merge(ArrayList<String> list, String c) {
    ArrayList<String> res = new ArrayList<>();
    // Loop through all the string in the list
    for (String s : list) {
        // For each string, insert the last character to all possible positions
        // and add them to the new list
        for (int i = 0; i <= s.length(); ++i) {
            String ps = new StringBuffer(s).insert(i, c).toString();
            res.add(ps);
        }
    }
    return res;
}

---

Sortie en cours d'exécution de la chaîne "abcd" :

• Étape 1 : Fusionner [a] et b : [ba, ab]

• Étape 2 : fusionner [ba, ab] et c : [cba, bca, bac, cab, acb, abc]

• Étape 3 : Fusionner [cba, bca, bac, cab, acb, abc] et d : [dcba, cdba, cbda, cbad, dbca, bdca, bcda, bcad, dbac, bdac, badc, bacd, dcab, cdab, cadb, cabd, dacb, adcb, acdb, acbd, dabc, adbc, abdc, abcd].

Answer 4

De toutes les solutions données ici et dans d'autres forums, c'est Mark Byers qui m'a le plus plu. Sa description m'a fait réfléchir et coder moi-même. Dommage que je ne puisse pas voter pour sa solution car je suis un débutant.
Quoi qu'il en soit, voici mon application de sa description

public class PermTest {

    public static void main(String[] args) throws Exception {
        String str = "abcdef";
        StringBuffer strBuf = new StringBuffer(str);
        doPerm(strBuf,0);
    }

    private static void doPerm(StringBuffer str, int index){

        if(index == str.length())
            System.out.println(str);            
        else { //recursively solve this by placing all other chars at current first pos
            doPerm(str, index+1);
            for (int i = index+1; i < str.length(); i++) {//start swapping all other chars with current first char
                swap(str,index, i);
                doPerm(str, index+1);
                swap(str,i, index);//restore back my string buffer
            }
        }
    }

    private  static void swap(StringBuffer str, int pos1, int pos2){
        char t1 = str.charAt(pos1);
        str.setCharAt(pos1, str.charAt(pos2));
        str.setCharAt(pos2, t1);
    }
}   

Je préfère cette solution à la première dans ce fil car cette solution utilise StringBuffer. Je ne dirais pas que ma solution ne crée pas de chaîne temporaire (elle le fait en fait dans le cas de system.out.println où le toString() de StringBuffer est appelé). Mais je pense que c'est mieux que la première solution qui crée trop de chaînes littérales. Peut-être qu'un spécialiste des performances pourra évaluer cette solution en termes de "mémoire" (en termes de "temps", elle est déjà en retard en raison de ce "swap" supplémentaire).

Answer 5

Celui-ci est sans récurrence

public static void permute(String s) {
    if(null==s || s.isEmpty()) {
        return;
    }

    // List containing words formed in each iteration 
    List<String> strings = new LinkedList<String>();
    strings.add(String.valueOf(s.charAt(0))); // add the first element to the list

     // Temp list that holds the set of strings for 
     //  appending the current character to all position in each word in the original list
    List<String> tempList = new LinkedList<String>(); 

    for(int i=1; i< s.length(); i++) {

        for(int j=0; j<strings.size(); j++) {
            tempList.addAll(merge(s.charAt(i), strings.get(j)));
                        }
        strings.removeAll(strings);
        strings.addAll(tempList);

        tempList.removeAll(tempList);

    }

    for(int i=0; i<strings.size(); i++) {
        System.out.println(strings.get(i));
    }
}

/**
 * helper method that appends the given character at each position in the given string 
 * and returns a set of such modified strings 
 * - set removes duplicates if any(in case a character is repeated)
 */
private static Set<String> merge(Character c,  String s) {
    if(s==null || s.isEmpty()) {
        return null;
    }

    int len = s.length();
    StringBuilder sb = new StringBuilder();
    Set<String> list = new HashSet<String>();

    for(int i=0; i<= len; i++) {
        sb = new StringBuilder();
        sb.append(s.substring(0, i) + c + s.substring(i, len));
        list.add(sb.toString());
    }

    return list;
}