지정된 문자열의 모든 순열 생성
끈의 모든 배열을 찾는 우아한 방법은 무엇일까요?예: 치환ba,되지요ba그리고.ab단, 다음과 같은 긴 문자열은 어떨까요?abcdefgh자바 구현 예가 있습니까?
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"(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, cbda, cbca, bdca, bdca, bcad, dbac, bdc, bdc, dcab, cadbcab, cab, adbcbc, adbcbcbc, adbc, adbc, abc, abc, abc, abc, abc, abc, abc, abc, abc, ad
여기와 다른 포럼에서 주어진 모든 솔루션 중에서 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);
}
}
이 솔루션은 String Buffer를 사용하기 때문에 이 스레드의 첫 번째 솔루션보다 이 솔루션을 선호합니다.이 솔루션에서는 일시적인 스트링이 생성되지 않습니다(실제로 작성됩니다).system.out.println어디서toString()StringBuffer가 호출됩니다).하지만 나는 이것이 너무 많은 문자열 리터럴이 만들어지는 첫 번째 해결책보다 낫다고 느낀다.퍼포먼스를 중시하는 사람이라면, 이것을 「메모리」라고 하는 관점에서 평가할 수 있을 것입니다(「시간」의 경우, 그 여분의 「스왑」에 의해서 이미 늦어지고 있습니다).
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;
}
이전 기고자들은 모두 코드를 잘 설명하고 제공해 주었습니다.저도 누군가에게 도움이 될지도 모르기 때문에 이 방법을 공유해야겠다고 생각했습니다.솔루션은 (Heaps 알고리즘)에 기초하고 있습니다.
몇 가지 사항:
엑셀에 기재되어 있는 마지막 항목은 논리를 보다 잘 시각화할 수 있도록 하기 위한 것입니다.따라서 마지막 열의 실제 값은 2,1,0입니다(어레이를 다루고 있기 때문에 코드를 실행하면 어레이는 0으로 시작됩니다).
스왑 알고리즘은 현재 위치의 짝수 또는 홀수 값을 기반으로 발생합니다.스왑 방식이 호출되는 위치를 보면 매우 설명이 됩니다.무슨 일이 벌어지는지 알 수 있어요.
.
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);
}
}
}
}
력력 input를 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());
}
}
}
이건 재귀가 없어요
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;
}
다음은 우아하고 반복적이지 않은 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;
}
간단한 해결책 중 하나는 두 개의 포인터를 사용하여 문자를 재귀적으로 계속 교환하는 것입니다.
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;
}
}
}
python 구현
def getPermutation(s, prefix=''):
if len(s) == 0:
print prefix
for i in range(len(s)):
getPermutation(s[0:i]+s[i+1:len(s)],prefix+s[i] )
getPermutation('abcd','')
이것은 순열과 재귀 함수 호출에 대한 기본적인 이해를 통해 수행되었습니다.시간이 좀 걸리지만 개별적으로 진행됩니다.
public class LexicographicPermutations {
public static void main(String[] args) {
// TODO Auto-generated method stub
String s="abc";
List<String>combinations=new ArrayList<String>();
combinations=permutations(s);
Collections.sort(combinations);
System.out.println(combinations);
}
private static List<String> permutations(String s) {
// TODO Auto-generated method stub
List<String>combinations=new ArrayList<String>();
if(s.length()==1){
combinations.add(s);
}
else{
for(int i=0;i<s.length();i++){
List<String>temp=permutations(s.substring(0, i)+s.substring(i+1));
for (String string : temp) {
combinations.add(s.charAt(i)+string);
}
}
}
return combinations;
}}
출력은 다음과 같이 생성됩니다.[abc, acb, bac, bca, cab, cba].
그 배후에 있는 기본적인 논리는
각 문자에 대해 첫 번째 문자로 간주하고 나머지 문자의 조합을 찾습니다.[abc](Combination of abc)->.
a->[bc](a x Combination of (bc))->{abc,acb}b->[ac](b x Combination of (ac))->{bac,bca}c->[ab](c x Combination of (ab))->{cab,cba}
후, 각 「」(으로 콜)을 실시합니다.[bc] ,[ac]&[ab]독자적으로
재귀 사용.
입력이 빈 문자열일 경우 유일한 순열은 빈 문자열입니다.문자열의 각 문자에 대해 첫 번째 문자로 만들고 재귀 호출을 사용하여 나머지 문자의 모든 순서를 찾습니다.
import java.util.ArrayList;
import java.util.List;
class Permutation {
private static List<String> permutation(String prefix, String str) {
List<String> permutations = new ArrayList<>();
int n = str.length();
if (n == 0) {
permutations.add(prefix);
} else {
for (int i = 0; i < n; i++) {
permutations.addAll(permutation(prefix + str.charAt(i), str.substring(i + 1, n) + str.substring(0, i)));
}
}
return permutations;
}
public static void main(String[] args) {
List<String> perms = permutation("", "abcd");
String[] array = new String[perms.size()];
for (int i = 0; i < perms.size(); i++) {
array[i] = perms.get(i);
}
int x = array.length;
for (final String anArray : array) {
System.out.println(anArray);
}
}
}
이건 나한테 효과가 있었어
import java.util.Arrays;
public class StringPermutations{
public static void main(String args[]) {
String inputString = "ABC";
permute(inputString.toCharArray(), 0, inputString.length()-1);
}
public static void permute(char[] ary, int startIndex, int endIndex) {
if(startIndex == endIndex){
System.out.println(String.valueOf(ary));
}else{
for(int i=startIndex;i<=endIndex;i++) {
swap(ary, startIndex, i );
permute(ary, startIndex+1, endIndex);
swap(ary, startIndex, i );
}
}
}
public static void swap(char[] ary, int x, int y) {
char temp = ary[x];
ary[x] = ary[y];
ary[y] = temp;
}
}
Kotlin과 함께 이 문제에 대처해 보겠습니다.
fun <T> List<T>.permutations(): List<List<T>> {
//escape case
if (this.isEmpty()) return emptyList()
if (this.size == 1) return listOf(this)
if (this.size == 2) return listOf(listOf(this.first(), this.last()), listOf(this.last(), this.first()))
//recursive case
return this.flatMap { lastItem ->
this.minus(lastItem).permutations().map { it.plus(lastItem) }
}
}
핵심 개념: 긴 목록을 더 작은 목록으로 분할 + 재귀
예 목록 [1, 2, 3, 4]을 포함한 긴 답변:
심지어 4개의 목록도 머릿속에서 가능한 모든 순열을 나열하는 것은 혼란스러울 수 있습니다. 그리고 우리가 해야 할 일은 정확히 그것을 피하는 것입니다.사이즈가 0, 1, 2인 리스트의 모든 배열을 이해하기 쉽기 때문에 그 사이즈 중 하나로 분할하여 올바르게 백업하기만 하면 됩니다.잭팟 머신을 상상해 보세요.이 알고리즘은 오른쪽에서 왼쪽으로 회전하기 시작하고, 써내려갑니다.
- 목록 크기가 0 또는 1인 경우 빈 목록/1을 반환합니다.
- 리스트 사이즈가 2(예: [3, 4])인 경우 처리하여 2개의 순열([3, 4] & [4, 3)을 생성합니다.
- 각 항목에 대해 마지막 항목으로 표시하고 목록의 나머지 항목에 대한 모든 순열을 찾습니다.(예: [4]를 테이블 위에 놓고 [1, 2, 3]을 다시 순열 상태로 던집니다.)
- 모든 치환과 함께 목록 맨 끝으로 돌아갑니다(예: [1, 2, 3][, 4], [1, 3, 2][, 4], [2, 3, 1][, 4],).
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
public class hello {
public static void main(String[] args) throws IOException {
hello h = new hello();
h.printcomp();
}
int fact=1;
public void factrec(int a,int k){
if(a>=k)
{fact=fact*k;
k++;
factrec(a,k);
}
else
{System.out.println("The string will have "+fact+" permutations");
}
}
public void printcomp(){
String str;
int k;
Scanner in = new Scanner(System.in);
System.out.println("enter the string whose permutations has to b found");
str=in.next();
k=str.length();
factrec(k,1);
String[] arr =new String[fact];
char[] array = str.toCharArray();
while(p<fact)
printcomprec(k,array,arr);
// if incase u need array containing all the permutation use this
//for(int d=0;d<fact;d++)
//System.out.println(arr[d]);
}
int y=1;
int p = 0;
int g=1;
int z = 0;
public void printcomprec(int k,char array[],String arr[]){
for (int l = 0; l < k; l++) {
for (int b=0;b<k-1;b++){
for (int i=1; i<k-g; i++) {
char temp;
String stri = "";
temp = array[i];
array[i] = array[i + g];
array[i + g] = temp;
for (int j = 0; j < k; j++)
stri += array[j];
arr[z] = stri;
System.out.println(arr[z] + " " + p++);
z++;
}
}
char temp;
temp=array[0];
array[0]=array[y];
array[y]=temp;
if (y >= k-1)
y=y-(k-1);
else
y++;
}
if (g >= k-1)
g=1;
else
g++;
}
}
/** Returns an array list containing all
* permutations of the characters in s. */
public static ArrayList<String> permute(String s) {
ArrayList<String> perms = new ArrayList<>();
int slen = s.length();
if (slen > 0) {
// Add the first character from s to the perms array list.
perms.add(Character.toString(s.charAt(0)));
// Repeat for all additional characters in s.
for (int i = 1; i < slen; ++i) {
// Get the next character from s.
char c = s.charAt(i);
// For each of the strings currently in perms do the following:
int size = perms.size();
for (int j = 0; j < size; ++j) {
// 1. remove the string
String p = perms.remove(0);
int plen = p.length();
// 2. Add plen + 1 new strings to perms. Each new string
// consists of the removed string with the character c
// inserted into it at a unique location.
for (int k = 0; k <= plen; ++k) {
perms.add(p.substring(0, k) + c + p.substring(k));
}
}
}
}
return perms;
}
Java의 간단한 미니멀리즘 재귀 솔루션을 다음에 나타냅니다.
public static ArrayList<String> permutations(String s) {
ArrayList<String> out = new ArrayList<String>();
if (s.length() == 1) {
out.add(s);
return out;
}
char first = s.charAt(0);
String rest = s.substring(1);
for (String permutation : permutations(rest)) {
out.addAll(insertAtAllPositions(first, permutation));
}
return out;
}
public static ArrayList<String> insertAtAllPositions(char ch, String s) {
ArrayList<String> out = new ArrayList<String>();
for (int i = 0; i <= s.length(); ++i) {
String inserted = s.substring(0, i) + ch + s.substring(i);
out.add(inserted);
}
return out;
}
계수를 사용하여 특정 문자로 시작하는 문자열 수를 확인할 수 있습니다.
예: 입력을 받습니다.abcd(3!) == 6은 한 한 로 시작합니다.abcd.
static public int facts(int x){
int sum = 1;
for (int i = 1; i < x; i++) {
sum *= (i+1);
}
return sum;
}
public static void permutation(String str) {
char[] str2 = str.toCharArray();
int n = str2.length;
int permutation = 0;
if (n == 1) {
System.out.println(str2[0]);
} else if (n == 2) {
System.out.println(str2[0] + "" + str2[1]);
System.out.println(str2[1] + "" + str2[0]);
} else {
for (int i = 0; i < n; i++) {
if (true) {
char[] str3 = str.toCharArray();
char temp = str3[i];
str3[i] = str3[0];
str3[0] = temp;
str2 = str3;
}
for (int j = 1, count = 0; count < facts(n-1); j++, count++) {
if (j != n-1) {
char temp1 = str2[j+1];
str2[j+1] = str2[j];
str2[j] = temp1;
} else {
char temp1 = str2[n-1];
str2[n-1] = str2[1];
str2[1] = temp1;
j = 1;
} // end of else block
permutation++;
System.out.print("permutation " + permutation + " is -> ");
for (int k = 0; k < n; k++) {
System.out.print(str2[k]);
} // end of loop k
System.out.println();
} // end of loop j
} // end of loop i
}
}
재귀 없는 Java 구현
public Set<String> permutate(String s){
Queue<String> permutations = new LinkedList<String>();
Set<String> v = new HashSet<String>();
permutations.add(s);
while(permutations.size()!=0){
String str = permutations.poll();
if(!v.contains(str)){
v.add(str);
for(int i = 0;i<str.length();i++){
String c = String.valueOf(str.charAt(i));
permutations.add(str.substring(i+1) + c + str.substring(0,i));
}
}
}
return v;
}
//각 문자를 배열 목록에 삽입
static ArrayList al = new ArrayList();
private static void findPermutation (String str){
for (int k = 0; k < str.length(); k++) {
addOneChar(str.charAt(k));
}
}
//insert one char into ArrayList
private static void addOneChar(char ch){
String lastPerStr;
String tempStr;
ArrayList locAl = new ArrayList();
for (int i = 0; i < al.size(); i ++ ){
lastPerStr = al.get(i).toString();
//System.out.println("lastPerStr: " + lastPerStr);
for (int j = 0; j <= lastPerStr.length(); j++) {
tempStr = lastPerStr.substring(0,j) + ch +
lastPerStr.substring(j, lastPerStr.length());
locAl.add(tempStr);
//System.out.println("tempStr: " + tempStr);
}
}
if(al.isEmpty()){
al.add(ch);
} else {
al.clear();
al = locAl;
}
}
private static void printArrayList(ArrayList al){
for (int i = 0; i < al.size(); i++) {
System.out.print(al.get(i) + " ");
}
}
//Rotate and create words beginning with all letter possible and push to stack 1
//Read from stack1 and for each word create words with other letters at the next location by rotation and so on
/* eg : man
1. push1 - man, anm, nma
2. pop1 - nma , push2 - nam,nma
pop1 - anm , push2 - amn,anm
pop1 - man , push2 - mna,man
*/
public class StringPermute {
static String str;
static String word;
static int top1 = -1;
static int top2 = -1;
static String[] stringArray1;
static String[] stringArray2;
static int strlength = 0;
public static void main(String[] args) throws IOException {
System.out.println("Enter String : ");
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader bfr = new BufferedReader(isr);
str = bfr.readLine();
word = str;
strlength = str.length();
int n = 1;
for (int i = 1; i <= strlength; i++) {
n = n * i;
}
stringArray1 = new String[n];
stringArray2 = new String[n];
push(word, 1);
doPermute();
display();
}
public static void push(String word, int x) {
if (x == 1)
stringArray1[++top1] = word;
else
stringArray2[++top2] = word;
}
public static String pop(int x) {
if (x == 1)
return stringArray1[top1--];
else
return stringArray2[top2--];
}
public static void doPermute() {
for (int j = strlength; j >= 2; j--)
popper(j);
}
public static void popper(int length) {
// pop from stack1 , rotate each word n times and push to stack 2
if (top1 > -1) {
while (top1 > -1) {
word = pop(1);
for (int j = 0; j < length; j++) {
rotate(length);
push(word, 2);
}
}
}
// pop from stack2 , rotate each word n times w.r.t position and push to
// stack 1
else {
while (top2 > -1) {
word = pop(2);
for (int j = 0; j < length; j++) {
rotate(length);
push(word, 1);
}
}
}
}
public static void rotate(int position) {
char[] charstring = new char[100];
for (int j = 0; j < word.length(); j++)
charstring[j] = word.charAt(j);
int startpos = strlength - position;
char temp = charstring[startpos];
for (int i = startpos; i < strlength - 1; i++) {
charstring[i] = charstring[i + 1];
}
charstring[strlength - 1] = temp;
word = new String(charstring).trim();
}
public static void display() {
int top;
if (top1 > -1) {
while (top1 > -1)
System.out.println(stringArray1[top1--]);
} else {
while (top2 > -1)
System.out.println(stringArray2[top2--]);
}
}
}
다른 간단한 방법은 문자열을 루프하고 아직 사용되지 않은 문자를 선택하여 버퍼에 넣은 후 버퍼 크기가 문자열 길이와 같아질 때까지 루프를 계속하는 것입니다.이 백 트래킹 솔루션이 더 마음에 드는 이유는 다음과 같습니다.
- 알기 쉽다
- 중복 회피가 용이함
- 출력이 정렬되었습니다.
Java 코드는 다음과 같습니다.
List<String> permute(String str) {
if (str == null) {
return null;
}
char[] chars = str.toCharArray();
boolean[] used = new boolean[chars.length];
List<String> res = new ArrayList<String>();
StringBuilder sb = new StringBuilder();
Arrays.sort(chars);
helper(chars, used, sb, res);
return res;
}
void helper(char[] chars, boolean[] used, StringBuilder sb, List<String> res) {
if (sb.length() == chars.length) {
res.add(sb.toString());
return;
}
for (int i = 0; i < chars.length; i++) {
// avoid duplicates
if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) {
continue;
}
// pick the character that has not used yet
if (!used[i]) {
used[i] = true;
sb.append(chars[i]);
helper(chars, used, sb, res);
// back tracking
sb.deleteCharAt(sb.length() - 1);
used[i] = false;
}
}
}
입력 문자열: 1231
출력 목록: {1123, 1132, 1213, 1231, 1312, 1321, 2113, 2131, 2311, 3112, 3121, 3211}
출력이 정렬되어 중복된 결과가 없는 것을 확인.
재귀는 불필요합니다.직접 치환을 계산할 수 있는 경우에도 이 솔루션에서는 제네릭을 사용하여 어레이를 조정합니다.
다음은 이 algorihtm에 대한 좋은 정보입니다.
C# 개발자에게는 이 쪽이 더 도움이 됩니다.
public static void main(String[] args) {
String word = "12345";
Character[] array = ArrayUtils.toObject(word.toCharArray());
long[] factorials = Permutation.getFactorials(array.length + 1);
for (long i = 0; i < factorials[array.length]; i++) {
Character[] permutation = Permutation.<Character>getPermutation(i, array, factorials);
printPermutation(permutation);
}
}
private static void printPermutation(Character[] permutation) {
for (int i = 0; i < permutation.length; i++) {
System.out.print(permutation[i]);
}
System.out.println();
}
이 알고리즘은 각 치환을 계산하기 위한 O(N) 시공간 복잡성을 가집니다.
public class Permutation {
public static <T> T[] getPermutation(long permutationNumber, T[] array, long[] factorials) {
int[] sequence = generateSequence(permutationNumber, array.length - 1, factorials);
T[] permutation = generatePermutation(array, sequence);
return permutation;
}
public static <T> T[] generatePermutation(T[] array, int[] sequence) {
T[] clone = array.clone();
for (int i = 0; i < clone.length - 1; i++) {
swap(clone, i, i + sequence[i]);
}
return clone;
}
private static int[] generateSequence(long permutationNumber, int size, long[] factorials) {
int[] sequence = new int[size];
for (int j = 0; j < sequence.length; j++) {
long factorial = factorials[sequence.length - j];
sequence[j] = (int) (permutationNumber / factorial);
permutationNumber = (int) (permutationNumber % factorial);
}
return sequence;
}
private static <T> void swap(T[] array, int i, int j) {
T t = array[i];
array[i] = array[j];
array[j] = t;
}
public static long[] getFactorials(int length) {
long[] factorials = new long[length];
long factor = 1;
for (int i = 0; i < length; i++) {
factor *= i <= 1 ? 1 : i;
factorials[i] = factor;
}
return factorials;
}
}
위의 Mark Byers 설명에 근거한 구현:
static Set<String> permutations(String str){
if (str.isEmpty()){
return Collections.singleton(str);
}else{
Set <String> set = new HashSet<>();
for (int i=0; i<str.length(); i++)
for (String s : permutations(str.substring(0, i) + str.substring(i+1)))
set.add(str.charAt(i) + s);
return set;
}
}
문자열 순열:
public static void main(String args[]) {
permu(0,"ABCD");
}
static void permu(int fixed,String s) {
char[] chr=s.toCharArray();
if(fixed==s.length())
System.out.println(s);
for(int i=fixed;i<s.length();i++) {
char c=chr[i];
chr[i]=chr[fixed];
chr[fixed]=c;
permu(fixed+1,new String(chr));
}
}
다음은 문자열의 순열을 수행하는 또 다른 간단한 방법입니다.
public class Solution4 {
public static void main(String[] args) {
String a = "Protijayi";
per(a, 0);
}
static void per(String a , int start ) {
//bse case;
if(a.length() == start) {System.out.println(a);}
char[] ca = a.toCharArray();
//swap
for (int i = start; i < ca.length; i++) {
char t = ca[i];
ca[i] = ca[start];
ca[start] = t;
per(new String(ca),start+1);
}
}//per
}
중복된 문자를 고려하여 특정 문자열의 모든 순열을 인쇄하고 고유한 문자만 인쇄하는 Java 구현은 다음과 같습니다.
import java.util.Set;
import java.util.HashSet;
public class PrintAllPermutations2
{
public static void main(String[] args)
{
String str = "AAC";
PrintAllPermutations2 permutation = new PrintAllPermutations2();
Set<String> uniqueStrings = new HashSet<>();
permutation.permute("", str, uniqueStrings);
}
void permute(String prefixString, String s, Set<String> set)
{
int n = s.length();
if(n == 0)
{
if(!set.contains(prefixString))
{
System.out.println(prefixString);
set.add(prefixString);
}
}
else
{
for(int i=0; i<n; i++)
{
permute(prefixString + s.charAt(i), s.substring(0,i) + s.substring(i+1,n), set);
}
}
}
}
Es6를 사용한 스트링 퍼뮤테이션
reduce() 메서드 사용
const permutations = str => {
if (str.length <= 2)
return str.length === 2 ? [str, str[1] + str[0]] : [str];
return str
.split('')
.reduce(
(acc, letter, index) =>
acc.concat(permutations(str.slice(0, index) + str.slice(index + 1)).map(val => letter + val)),
[]
);
};
console.log(permutations('STR'));보이드 방식으로 인쇄하는 것이 아니라 어떤 작업을 수행하기 위해 순열을 생성하려는 경우:
static List<int[]> permutations(int n) {
class Perm {
private final List<int[]> permutations = new ArrayList<>();
private void perm(int[] array, int step) {
if (step == 1) permutations.add(array.clone());
else for (int i = 0; i < step; i++) {
perm(array, step - 1);
int j = (step % 2 == 0) ? i : 0;
swap(array, step - 1, j);
}
}
private void swap(int[] array, int i, int j) {
int buffer = array[i];
array[i] = array[j];
array[j] = buffer;
}
}
int[] nVector = new int[n];
for (int i = 0; i < n; i++) nVector [i] = i;
Perm perm = new Perm();
perm.perm(nVector, n);
return perm.permutations;
}
언급URL : https://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string
'programing' 카테고리의 다른 글
| 왜 Itable은 stream() 메서드와 parallel Stream() 메서드를 제공하지 않습니까? (0) | 2022.08.07 |
|---|---|
| VueJ에는 React와 같은 제어되지 않은 컴포넌트라는 개념이 있습니까? (0) | 2022.08.07 |
| 파일 설명자에서 파일 포인터를 가져오려면 어떻게 해야 합니까? (0) | 2022.08.07 |
| Vuex에서 상태 속성을 기준으로 계산하는 올바른 방법은 무엇입니까? (0) | 2022.08.07 |
| Spring Security를 사용할 때 빈에서 현재 사용자 이름(Security Context 등) 정보를 얻는 적절한 방법은 무엇입니까? (0) | 2022.08.07 |