使用迭代对字符串进行排列

本文介绍了使用迭代对字符串进行排列的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在尝试查找给定字符串的排列，但是我想使用迭代.我在网上找到的递归解决方案我确实理解，但是将其转换为迭代解决方案实际上是行不通的.下面我附上了我的代码.我非常感谢您的帮助:

I'm trying to find permutation of a given string, but I want to use iteration. The recursive solution I found online and I do understand it, but converting it to an iterative solution is really not working out. Below I have attached my code. I would really appreciate the help:

public static void combString(String s) { char[] a = new char[s.length()]; //String temp = ""; for(int i = 0; i < s.length(); i++) { a[i] = s.charAt(i); } for(int i = 0; i < s.length(); i++) { String temp = "" + a[i]; for(int j = 0; j < s.length();j++) { //int k = j; if(i != j) { System.out.println(j); temp += s.substring(0,j) + s.substring(j+1,s.length()); } } System.out.println(temp); } }

推荐答案

关注我的相关问题注释，这是一个Java实现，可以使用计算QuickPerm算法:

Following up on my related question comment, here's a Java implementation that does what you want using the Counting QuickPerm Algorithm:

public static void combString(String s) { // Print initial string, as only the alterations will be printed later System.out.println(s); char[] a = s.toCharArray(); int n = a.length; int[] p = new int[n]; // Weight index control array initially all zeros. Of course, same size of the char array. int i = 1; //Upper bound index. i.e: if string is "abc" then index i could be at "c" while (i < n) { if (p[i] < i) { //if the weight index is bigger or the same it means that we have already switched between these i,j (one iteration before). int j = ((i % 2) == 0) ? 0 : p[i];//Lower bound index. i.e: if string is "abc" then j index will always be 0. swap(a, i, j); // Print current System.out.println(join(a)); p[i]++; //Adding 1 to the specific weight that relates to the char array. i = 1; //if i was 2 (for example), after the swap we now need to swap for i=1 } else { p[i] = 0;//Weight index will be zero because one iteration before, it was 1 (for example) to indicate that char array a[i] swapped. i++;//i index will have the option to go forward in the char array for "longer swaps" } } } private static String join(char[] a) { StringBuilder builder = new StringBuilder(); builder.append(a); return builder.toString(); } private static void swap(char[] a, int i, int j) { char temp = a[i]; a[i] = a[j]; a[j] = temp; }