找出弦的所有排列的优雅方法是什么。例如,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;
}
}
其他回答
使用Set操作建模“依赖于其他选择的选择”更容易理解相关排列 使用依赖排列,可用的选择减少,因为位置被从左到右的选定字符填充。递归调用的终端条件是测试可用选择集是否为空。当满足终端条件时,置换完成,并存储到“结果”列表中。
public static List<String> stringPermutation(String s) {
List<String> results = new ArrayList<>();
Set<Character> charSet = s.chars().mapToObj(m -> (char) m).collect(Collectors.toSet());
stringPermutation(charSet, "", results);
return results;
}
private static void stringPermutation(Set<Character> charSet,
String prefix, List<String> results) {
if (charSet.isEmpty()) {
results.add(prefix);
return;
}
for (Character c : charSet) {
Set<Character> newSet = new HashSet<>(charSet);
newSet.remove(c);
stringPermutation(newSet, prefix + c, results);
}
}
该代码可以泛化为一组对象查找排列。在本例中,我使用了一组颜色。
public enum Color{
ORANGE,RED,BULE,GREEN,YELLOW;
}
public static List<List<Color>> colorPermutation(Set<Color> colors) {
List<List<Color>> results = new ArrayList<>();
List<Color> prefix = new ArrayList<>();
permutation(colors, prefix, results);
return results;
}
private static <T> void permutation(Set<T> set, List<T> prefix, List<List<T>> results) {
if (set.isEmpty()) {
results.add(prefix);
return;
}
for (T t : set) {
Set<T> newSet = new HashSet<>(set);
List<T> newPrefix = new ArrayList<>(prefix);
newSet.remove(t);
newPrefix.add(t);
permutation(newSet, newPrefix, results);
}
}
测试代码。
public static void main(String[] args) {
List<String> stringPerm = stringPermutation("abcde");
System.out.println("# of permutations:" + stringPerm.size());
stringPerm.stream().forEach(e -> System.out.println(e));
Set<Color> colorSet = Arrays.stream(Color.values()).collect(Collectors.toSet());
List<List<Color>> colorPerm = colorPermutation(colorSet);
System.out.println("# of permutations:" + colorPerm.size());
colorPerm.stream().forEach(e -> System.out.println(e));
}
所有之前的贡献者都很好地解释和提供了代码。我想我也应该分享这个方法,因为它可能也会帮助到别人。解决方案基于(堆算法)
一些事情:
注意excel中最后一项的描述只是为了帮助你更好地可视化逻辑。因此,最后一列的实际值将是2,1,0(如果我们要运行代码,因为我们处理的是数组,而数组以0开头)。 交换算法基于当前位置的偶数或奇数值发生。如果你看一下swap方法被调用的位置,你就会明白这一点。你可以看到发生了什么。
事情是这样的:
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);
}
}
}
}
基于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)为空间复杂度。
我的实现基于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;
}
}
使用递归。
依次尝试每个字母作为第一个字母,然后使用递归调用找到剩余字母的所有排列。 基本情况是,当输入是空字符串时,唯一的排列就是空字符串。
推荐文章
- 在流中使用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