找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
基于Mark Byers的回答,我想出了这个解决方案:
JAVA
public class Main {
public static void main(String[] args) {
myPerm("ABCD", 0);
}
private static void myPerm(String str, int index)
{
if (index == str.length()) System.out.println(str);
for (int i = index; i < str.length(); i++)
{
char prefix = str.charAt(i);
String suffix = str.substring(0,i) + str.substring(i+1);
myPerm(prefix + suffix, index + 1);
}
}
}
C#
我还使用新的c# 8.0范围操作符在c#中编写了该函数
class Program
{
static void Main(string[] args)
{
myPerm("ABCD", 0);
}
private static void myPerm(string str, int index)
{
if (index == str.Length) Console.WriteLine(str);
for (int i = index; i < str.Length; i++)
{
char prefix = str[i];
string suffix = str[0..i] + str[(i + 1)..];
myPerm(prefix + suffix, index + 1);
}
}
我们只是把每个字母放在开头,然后排列。 第一次迭代是这样的:
/*
myPerm("ABCD",0)
prefix = "A"
suffix = "BCD"
myPerm("ABCD",1)
prefix = "B"
suffix = "ACD"
myPerm("BACD",2)
prefix = "C"
suffix = "BAD"
myPerm("CBAD",3)
prefix = "D"
suffix = "CBA"
myPerm("DCBA",4)
Console.WriteLine("DCBA")
*/
其他回答
在这里和其他论坛给出的所有解决方案中,我最喜欢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。我不会说我的解决方案没有创建任何临时字符串(它实际上在system.out.println中创建,其中调用StringBuffer的toString())。但我只是觉得这比第一个解决方案好太多的字符串字面值被创建。可能有些性能人员可以根据“内存”来评估这一点(对于“时间”来说,由于额外的“交换”,它已经滞后了)
这个没有递归
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;
}
让我试着用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],…)
基于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中一个非常基本的解决方案是使用递归+设置(以避免重复),如果你想存储和返回解决方案字符串:
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 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