Вопрос-ответ

Generating all permutations of a given string

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

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

Переведено автоматически
Ответ 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)

Ответ 2

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


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

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

Ответ 3

Вот мое решение, основанное на идее книги "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]


Ответ 4

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

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 ). Но я просто чувствую, что это лучше, чем первое решение, где создается слишком много строковых литералов. Может быть, какой-нибудь специалист по производительности может оценить это с точки зрения "памяти" (что касается "времени", то оно уже отстает из-за дополнительной "подкачки")

2023-11-22 04:53 java algorithm