Генерация всех перестановок данной строки

Question

Какой элегантный способ найти все перестановки строки.Например, ba, будет ba и ab, но как насчет abcdefgh?Есть ли пример реализации 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));
    }
}

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

Answer 2

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

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

Answer 3

Вот мое решение, основанное на идее книги «Взлом интервью» (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;
}

---

Запуск вывода строки "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, cdb, cabd, dacb, adcb, acdb, acbd, dabc, adbc, abdc, abcd] 1017 *

Answer 4

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

public class PermTest {

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

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

        if(index <= 0)
            System.out.println(str);            
        else { //recursively solve this by placing all other chars at current first pos
            doPerm(str, index-1);
            int currPos = str.length()-index;
            for (int i = currPos+1; i < str.length(); i++) {//start swapping all other chars with current first char
                swap(str,currPos, i);
                doPerm(str, index-1);
                swap(str,i, currPos);//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).Но я просто чувствую, что это лучше, чем первое решение, где создается слишком много строковых литералов.Может быть, какой-то парень из производительности может оценить это с точки зрения «памяти» (для «времени» он уже отстает из-за этого дополнительного «обмена»)

Answer 5

Очень базовое решение в Java - использовать рекурсию + Set (чтобы избежать повторений), если вы хотите сохранить и вернуть строки решения:

public static Set<String> generatePerm(String input)
{
    Set<String> set = new HashSet<String>();
    if (input == "")
        return set;

    Character a = input.charAt(0);

    if (input.length() > 1)
    {
        input = input.substring(1);

        Set<String> permSet = generatePerm(input);

        for (String x : permSet)
        {
            for (int i = 0; i <= x.length(); i++)
            {
                set.add(x.substring(0, i) + a + x.substring(i));
            }
        }
    }
    else
    {
        set.add(a + "");
    }
    return set;
}

Answer 6

Все предыдущие авторы проделали большую работу, объясняя и предоставляя код.Я подумал, что тоже должен поделиться этим подходом, потому что он тоже может кому-то помочь.Решение основано на ( алгоритм куч) )

Пара вещей:

1. Обратите внимание, что последний элемент, который изображен в Excel, простодля того, чтобы помочь вам лучше визуализировать логику.Таким образом, фактические значения в последнем столбце будут 2,1,0 (если бы мы запускали код, потому что имеем дело с массивами, а массивы начинаются с 0).

2. Алгоритм обмена происходит на основе четных или нечетных значений текущей позиции.Это самоочевидно, если вы посмотрите, где вызывается метод обмена. Вы можете видеть, что происходит.

Вот что происходит:

public static void main(String[] args) {

        String ourword = "abc";
        String[] ourArray = ourword.split("");
        permute(ourArray, ourArray.length);

    }

    private static void swap(String[] ourarray, int right, int left) {
        String temp = ourarray[right];
        ourarray[right] = ourarray[left];
        ourarray[left] = temp;
    }

    public static void permute(String[] ourArray, int currentPosition) {
        if (currentPosition == 1) {
            System.out.println(Arrays.toString(ourArray));
        } else {
            for (int i = 0; i < currentPosition; i++) {
                // subtract one from the last position (here is where you are
                // selecting the the next last item 
                permute(ourArray, currentPosition - 1);

                // if it's odd position
                if (currentPosition % 2 == 1) {
                    swap(ourArray, 0, currentPosition - 1);
                } else {
                    swap(ourArray, i, currentPosition - 1);
                }
            }
        }
    }

Answer 7

Это без рекурсии

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

Answer 8

Ну вот элегантное, нерекурсивное, O (n!) Решение:

public static StringBuilder[] permutations(String s) {
        if (s.length() == 0)
            return null;
        int length = fact(s.length());
        StringBuilder[] sb = new StringBuilder[length];
        for (int i = 0; i < length; i++) {
            sb[i] = new StringBuilder();
        }
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int times = length / (i + 1);
            for (int j = 0; j < times; j++) {
                for (int k = 0; k < length / times; k++) {
                    sb[j * length / times + k].insert(k, ch);
                }
            }
        }
        return sb;
    }

Answer 9

Давайте использовать в качестве примера входные данные abc.

Начнем с последнего элемента (c) в наборе (["c"]), затем добавим второй последний элемент (b)) к его передней, конечной и всевозможным позициям в середине, делая его ["bc", "cb"], а затем таким же образом он добавит следующий элемент сзади (a) к каждой строке в наборе, делающем его:

"a" + "bc" = ["abc", "bac", "bca"]  and  "a" + "cb" = ["acb" ,"cab", "cba"] 

Таким образом вся перестановка:

["abc", "bac", "bca","acb" ,"cab", "cba"]

Код:

public class Test 
{
    static Set<String> permutations;
    static Set<String> result = new HashSet<String>();

    public static Set<String> permutation(String string) {
        permutations = new HashSet<String>();

        int n = string.length();
        for (int i = n - 1; i >= 0; i--) 
        {
            shuffle(string.charAt(i));
        }
        return permutations;
    }

    private static void shuffle(char c) {
        if (permutations.size() == 0) {
            permutations.add(String.valueOf(c));
        } else {
            Iterator<String> it = permutations.iterator();
            for (int i = 0; i < permutations.size(); i++) {

                String temp1;
                for (; it.hasNext();) {
                    temp1 = it.next();
                    for (int k = 0; k < temp1.length() + 1; k += 1) {
                        StringBuilder sb = new StringBuilder(temp1);

                        sb.insert(k, c);

                        result.add(sb.toString());
                    }
                }
            }
            permutations = result;
            //'result' has to be refreshed so that in next run it doesn't contain stale values.
            result = new HashSet<String>();
        }
    }

    public static void main(String[] args) {
        Set<String> result = permutation("abc");

        System.out.println("\nThere are total of " + result.size() + " permutations:");
        Iterator<String> it = result.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

Answer 10

Одним из простых решений может быть продолжение рекурсивного обмена символами с использованием двух указателей.

public static void main(String[] args)
{
    String str="abcdefgh";
    perm(str);
}
public static void perm(String str)
{  char[] char_arr=str.toCharArray();
    helper(char_arr,0);
}
public static void helper(char[] char_arr, int i)
{
    if(i==char_arr.length-1)
    {
        // print the shuffled string 
            String str="";
            for(int j=0; j<char_arr.length; j++)
            {
                str=str+char_arr[j];
            }
            System.out.println(str);
    }
    else
    {
    for(int j=i; j<char_arr.length; j++)
    {
        char tmp = char_arr[i];
        char_arr[i] = char_arr[j];
        char_arr[j] = tmp;
        helper(char_arr,i+1);
        char tmp1 = char_arr[i];
        char_arr[i] = char_arr[j];
        char_arr[j] = tmp1;
    }
}
}