找出弦的所有排列的优雅方法是什么。例如，ba的排列，将是ba和ab，但更长的字符串，如abcdefgh?是否有Java实现示例?
当前回答
递归是不必要的，甚至你可以直接计算任何排列，这个解决方案使用泛型来排列任何数组。
这里有关于这个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;
}
}
其他回答
这是另一个更简单的方法来做一个字符串的排列。
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
}
为排列和组合添加更详细的NcK/NcR
public static void combinationNcK(List<String> inputList, String prefix, int chooseCount, List<String> resultList) {
if (chooseCount == 0)
resultList.add(prefix);
else {
for (int i = 0; i < inputList.size(); i++)
combinationNcK(inputList.subList(i + 1, inputList.size()), prefix + "," + inputList.get(i), chooseCount - 1, resultList);
// Finally print once all combinations are done
if (prefix.equalsIgnoreCase("")) {
resultList.stream().map(str -> str.substring(1)).forEach(System.out::println);
}
}
}
public static void permNcK(List<String> inputList, int chooseCount, List<String> resultList) {
for (int count = 0; count < inputList.size(); count++) {
permNcK(inputList, "", chooseCount, resultList);
resultList = new ArrayList<String>();
Collections.rotate(inputList, 1);
System.out.println("-------------------------");
}
}
public static void permNcK(List<String> inputList, String prefix, int chooseCount, List<String> resultList) {
if (chooseCount == 0)
resultList.add(prefix);
else {
for (int i = 0; i < inputList.size(); i++)
combinationNcK(inputList.subList(i + 1, inputList.size()), prefix + "," + inputList.get(i), chooseCount - 1, resultList);
// Finally print once all combinations are done
if (prefix.equalsIgnoreCase("")) {
resultList.stream().map(str -> str.substring(1)).forEach(System.out::println);
}
}
}
public static void main(String[] args) {
List<String> positions = Arrays.asList(new String[] { "1", "2", "3", "4", "5", "6", "7", "8" });
List<String> resultList = new ArrayList<String>();
//combinationNcK(positions, "", 3, resultList);
permNcK(positions, 3, resultList);
}
递归是不必要的，甚至你可以直接计算任何排列，这个解决方案使用泛型来排列任何数组。
这里有关于这个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;
}
}
这里有一个优雅的，非递归的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;
}
基于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")
*/
推荐文章
- 创建正则表达式匹配数组
- 我如何在Java中初始化一个全零的数组列表?
- 主体、使用者和主体之间的意义和区别是什么?
- 将字节转换为十六进制
- HashSet和HashMap的区别?
- 我如何有效地解析HTML与Java?
- Java构造函数继承
- 如何在Java中将int[]转换为Integer[] ?
- 你能解释一下流的概念吗?
- 导致java.lang.VerifyError错误的原因
- 如何在Java中监控计算机的CPU、内存和磁盘使用情况?
- 如何设置超时在改造库?
- java lambda可以有一个以上的参数吗?
- HashMap -获取第一个键值
- 使用Jackson将JSON字符串转换为漂亮的打印JSON输出
