Generating all permutations of a given string

Какой элегантный способ найти все перестановки строки. Например. перестановкой для ba, было бы ba и ab, но как насчет более длинной строки, такой как abcdefgh? Есть ли какой-нибудь пример реализации Java?

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));
    }
}

(через Введение в программирование на Java)

Используйте рекурсию.

• Попробуйте каждую из букв по очереди в качестве первой буквы, а затем найдите все перестановки оставшихся букв с помощью рекурсивного вызова.


• Базовый случай заключается в том, что когда входные данные представляют собой пустую строку, единственной перестановкой является пустая строка.

Вот мое решение, основанное на идее книги "Cracking the Coding Interview" (Стр. 54):

/**
 * 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;
}

Запуск вывода строки "abcd":

• Шаг 1: Объединить [a] и b: [ba, ab]




• Шаг 2: Объединить [ba, ab] и c: [cba, bca, bac, cab, acb, abc]




• Шаг 3: Объединить [cba, bca, bac, cab, acb, abc] и 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]

Из всех решений, приведенных здесь и на других форумах, мне больше всего понравился Марк Байерс. Это описание на самом деле заставило меня подумать и написать его самому. Жаль, что я не могу проголосовать за его решение, поскольку я новичок.
В любом случае, вот моя реализация его описания

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);
    }
}   

Я предпочитаю это решение перед первым в этом потоке, потому что это решение использует StringBuffer. Я бы не сказал, что мое решение не создает никакой временной строки (на самом деле это происходит в system.out.println где toString() вызывается StringBuffer ). Но я просто чувствую, что это лучше, чем первое решение, где создается слишком много строковых литералов. Может быть, какой-нибудь специалист по производительности может оценить это с точки зрения "памяти" (что касается "времени", то оно уже отстает из-за дополнительной "подкачки")