找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
基于Mark Byers的回答,我的python实现:
def permutations(string):
if len(string) == 1:
return [string]
permutations=[]
for i in range(len(string)):
for perm in permutations(string[:i]+string[i+1:]):
permutations.append(string[i] + perm)
return permutations
其他回答
这是一个具有O(n!)时间复杂度的算法,具有纯递归和直观。
public class words {
static String combinations;
public static List<String> arrlist=new ArrayList<>();
public static void main(String[] args) {
words obj = new words();
String str="premandl";
obj.getcombination(str, str.length()-1, "");
System.out.println(arrlist);
}
public void getcombination(String str, int charIndex, String output) {
if (str.length() == 0) {
arrlist.add(output);
return ;
}
if (charIndex == -1) {
return ;
}
String character = str.toCharArray()[charIndex] + "";
getcombination(str, --charIndex, output);
String remaining = "";
output = output + character;
remaining = str.substring(0, charIndex + 1) + str.substring(charIndex + 2);
getcombination(remaining, remaining.length() - 1, output);
}
}
让我试着用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],…)
这是一个更快的解决方案,因为它不受字符串连接计算复杂度O(n^2)的影响。另一方面它是无循环的,完全递归的
public static void main(String[] args) {
permutation("ABCDEFGHIJKLMNOPQRSTUVWXYZ");
}
private static void permutation(String str) {
char[] stringArray = str.toCharArray();
printPermutation(stringArray, 0, stringArray.length, 0, 1);
}
private static void printPermutation(char[] string, int loopCounter, int length, int indexFrom, int indexTo) {
// Stop condition
if (loopCounter == length)
return;
/*
When reaching the end of the array:
1- Reset loop indices.
2- Increase length counter.
*/
if (indexTo == length) {
indexFrom = 0;
indexTo = 1;
++loopCounter;
}
// Print.
System.out.println(string);
// Swap from / to indices.
char temp = string[indexFrom];
string[indexFrom] = string[indexTo];
string[indexTo] = temp;
// Go for next iteration.
printPermutation(string, loopCounter, length, ++indexFrom, ++indexTo);
}
这是一个C解:
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
char* addLetter(char* string, char *c) {
char* result = malloc(sizeof(string) + 2);
strcpy(result, string);
strncat(result, c, 1);
return result;
}
char* removeLetter(char* string, char *c) {
char* result = malloc(sizeof(string));
int j = 0;
for (int i = 0; i < strlen(string); i++) {
if (string[i] != *c) {
result[j++] = string[i];
}
}
result[j] = '\0';
return result;
}
void makeAnagram(char *anagram, char *letters) {
if (*letters == '\0') {
printf("%s\n", anagram);
return;
}
char *c = letters;
while (*c != '\0') {
makeAnagram(addLetter(anagram, c),
removeLetter(letters, c));
c++;
}
}
int main() {
makeAnagram("", "computer");
return 0;
}
基于Heap算法的我的实现:
import java.util.ArrayList;
import java.util.List;
public class PermutationString {
public static List<String> permute(char[] str, int n) {
List<String> permutations = new ArrayList<>();
if (n == 1) {
permutations.add(new String(str));
}
else {
for (int i = 0; i < n; i++) {
permutations.addAll(permute(str, n-1));
if (n % 2 == 0) {
swap(str, i, n-1);
}
else {
swap(str, 0, n-1);
}
}
}
return permutations;
}
public static void swap(char[] str, int i, int j) {
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
public static void main(String[] args) {
List<String> permutations = permute("abcdefgh".toCharArray(), 8);
System.out.println(permutations);
}
}
时间复杂度为O(n!* n), O(n)为空间复杂度。
推荐文章
- 在流中使用Java 8 foreach循环移动到下一项
- 访问限制:'Application'类型不是API(必需库rt.jar的限制)
- 用Java计算两个日期之间的天数
- 如何配置slf4j-simple
- 在Jar文件中运行类
- 带参数的可运行?
- 我如何得到一个字符串的前n个字符而不检查大小或出界?
- 我可以在Java中设置enum起始值吗?
- Java中的回调函数
- c#和Java中的泛型有什么不同?和模板在c++ ?
- 在Java中,流相对于循环的优势是什么?
- Jersey在未找到InjectionManagerFactory时停止工作
- 在Java流是peek真的只是调试?
- Recyclerview不调用onCreateViewHolder
- 将JSON字符串转换为HashMap