문자열의 모든 순열을 찾는 우아한 방법은 무엇입니까? 예를 들어 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 프로그래밍 소개를 통해 )
답변
재귀를 사용하십시오.
- 각 문자를 차례로 첫 번째 문자로 시도한 다음 재귀 호출을 사용하여 나머지 문자의 모든 순열을 찾으십시오.
- 기본 사례는 입력이 빈 문자열 인 경우 유일한 순열은 빈 문자열입니다.
답변
다음은 “코딩 인터뷰 크래킹”(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, 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]
답변
여기 및 다른 포럼에서 제공된 모든 솔루션 중에서 Mark Byers가 가장 마음에 들었습니다. 그 설명은 실제로 저 자신을 생각하고 코딩하게했습니다. 너무 나도 초보자이기 때문에 자신의 솔루션을 투표 할 수 없습니다.
어쨌든 여기에 그의 설명의 구현이 있습니다.
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를 사용하기 때문에이 스레드의 첫 번째 솔루션보다이 솔루션을 선호합니다. 내 솔루션이 임시 문자열을 만들지 않는다고 말하지는 않습니다 (실제로 of of StringBuffer가 호출 system.out.println되는 위치에서 toString()수행함). 그러나 나는 이것이 너무 많은 문자열 리터럴이 생성되는 첫 번째 솔루션보다 낫다고 생각합니다. ‘메모리’의 관점에서 이것을 평가할 수있는 성능 사람이있을 수 있습니다 ( ‘시간’의 경우 여분의 ‘스왑’으로 인해 이미 지연됩니다)
답변
Java에서 매우 기본적인 솔루션은 솔루션 문자열을 저장하고 반환하려는 경우 재귀 + 설정 (반복을 피하기 위해)을 사용하는 것입니다.
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;
}답변
이전의 모든 기고자들은 코드를 설명하고 제공하는 훌륭한 일을했습니다. 나는 누군가에게 도움이 될 수 있기 때문에이 접근법을 공유해야한다고 생각했습니다. 솔루션은 ( 힙 알고리즘 )을 기반으로합니다.
몇 가지 :
-
엑셀에 표시된 마지막 항목은 로직을 더 잘 시각화하는 데 도움이되는 것입니다. 따라서 마지막 열의 실제 값은 2,1,0입니다 (배열을 처리하기 때문에 코드를 실행하는 경우 배열은 0으로 시작합니다).
-
스와핑 알고리즘은 현재 위치의 짝수 또는 홀수 값을 기반으로 발생합니다. swap 메소드가 어디에서 호출되는지 살펴보면 매우 설명이 필요합니다.
다음과 같은 일이 발생합니다.
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);
}
}
}
}답변
이건 재귀가 없다
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;
}