找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
这是一个具有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);
}
}
其他回答
递归是不必要的,甚至你可以直接计算任何排列,这个解决方案使用泛型来排列任何数组。
这里有关于这个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;
}
}
//循环'整个字符数组,并保持'i'作为你的排列的基础,并像你交换[ab, ba]一样继续寻找组合
public class Permutation {
//Act as a queue
private List<Character> list;
//To remove the duplicates
private Set<String> set = new HashSet<String>();
public Permutation(String s) {
list = new LinkedList<Character>();
int len = s.length();
for(int i = 0; i < len; i++) {
list.add(s.charAt(i));
}
}
public List<String> getStack(Character c, List<Character> list) {
LinkedList<String> stack = new LinkedList<String>();
stack.add(""+c);
for(Character ch: list) {
stack.add(""+ch);
}
return stack;
}
public String printCombination(String s1, String s2) {
//S1 will be a single character
StringBuilder sb = new StringBuilder();
String[] strArr = s2.split(",");
for(String s: strArr) {
sb.append(s).append(s1);
sb.append(",");
}
for(String s: strArr) {
sb.append(s1).append(s);
sb.append(",");
}
return sb.toString();
}
public void printPerumtation() {
int cnt = list.size();
for(int i = 0; i < cnt; i++) {
Character c = list.get(0);
list.remove(0);
List<String> stack = getStack(c, list);
while(stack.size() > 1) {
//Remove the top two elements
String s2 = stack.remove(stack.size() - 1);
String s1 = stack.remove(stack.size() - 1);
String comS = printCombination(s1, s2);
stack.add(comS);
}
String[] perms = (stack.remove(0)).split(",");
for(String perm: perms) {
set.add(perm);
}
list.add(c);
}
for(String s: set) {
System.out.println(s);
}
}
}
这对我很有效。
import java.util.Arrays;
public class StringPermutations{
public static void main(String args[]) {
String inputString = "ABC";
permute(inputString.toCharArray(), 0, inputString.length()-1);
}
public static void permute(char[] ary, int startIndex, int endIndex) {
if(startIndex == endIndex){
System.out.println(String.valueOf(ary));
}else{
for(int i=startIndex;i<=endIndex;i++) {
swap(ary, startIndex, i );
permute(ary, startIndex+1, endIndex);
swap(ary, startIndex, i );
}
}
}
public static void swap(char[] ary, int x, int y) {
char temp = ary[x];
ary[x] = ary[y];
ary[y] = temp;
}
}
使用位操作可以很容易地做到这一点。“我们都知道,任何给定的有N个元素的集合有2N个可能的子集。如果我们用一个位来表示子集中的每个元素呢?位可以是0或1,因此我们可以用它来表示对应的元素是否属于这个给定的子集。所以每个位模式代表一个子集。”(复制文本)
private void getPermutation(String str)
{
if(str==null)
return;
Set<String> StrList = new HashSet<String>();
StringBuilder strB= new StringBuilder();
for(int i = 0;i < (1 << str.length()); ++i)
{
strB.setLength(0); //clear the StringBuilder
for(int j = 0;j < str.length() ;++j){
if((i & (1 << j))>0){ // to check whether jth bit is set
strB.append(str.charAt(j));
}
}
if(!strB.toString().isEmpty())
StrList.add(strB.toString());
}
System.out.println(Arrays.toString(StrList.toArray()));
}
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