找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
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;
}
其他回答
使用递归。
依次尝试每个字母作为第一个字母,然后使用递归调用找到剩余字母的所有排列。 基本情况是,当输入是空字符串时,唯一的排列就是空字符串。
下面是一个简单的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;
}
递归Python解决方案
def permute(input_str):
_permute("", input_str)
def _permute(prefix, str_to_permute):
if str_to_permute == '':
print(prefix)
else:
for i in range(len(str_to_permute)):
_permute(prefix+str_to_permute[i], str_to_permute[0:i] + str_to_permute[i+1:])
if __name__ == '__main__':
permute('foobar')
让我试着用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],…)
改进的代码相同
static String permutationStr[];
static int indexStr = 0;
static int factorial (int i) {
if (i == 1)
return 1;
else
return i * factorial(i-1);
}
public static void permutation(String str) {
char strArr[] = str.toLowerCase().toCharArray();
java.util.Arrays.sort(strArr);
int count = 1, dr = 1;
for (int i = 0; i < strArr.length-1; i++){
if ( strArr[i] == strArr[i+1]) {
count++;
} else {
dr *= factorial(count);
count = 1;
}
}
dr *= factorial(count);
count = factorial(strArr.length) / dr;
permutationStr = new String[count];
permutation("", str);
for (String oneStr : permutationStr){
System.out.println(oneStr);
}
}
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) {
for (int i = 0; i < indexStr; i++){
if(permutationStr[i].equals(prefix))
return;
}
permutationStr[indexStr++] = prefix;
} else {
for (int i = 0; i < n; i++) {
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, 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