在我开始之前，我不得不为重复提出另一个排列的情况而道歉。我已经浏览了大部分搜索结果，无法找到我想要的内容。我已阅读有关Lexicographical命令并已实施它。对于这个问题，我想要实现一个递归方法，它打印出长度为n的所有字符串，其中只包含a和b等于a和b的字符a和b。字符串必须按词汇顺序一次打印出一行。所以，例如，一个电话：
printBalanced(4);
将打印字符串：
aabb
abab
abba
baab
baba
bbaa
这是代码
public static void main(String[] args){
printBalanced(4);
}
public static void printBalanced(int n){
String letters = "";
//string to be duplicates of "ab" depending the number of times the user wants it
for(int i =0; i<n/2;i++){
letters += "ab";
}
balanced("",letters);
}
private static void balanced(String prefix, String s){
int len = s.length();
//base case
if (len ==0){
System.out.println(prefix);
}
else{
for(int i = 0; i<len; i++){
balanced(prefix + s.charAt(i),s.substring(0,i)+s.substring(i+1,len));
}
}
}
我的打印结果：
abab
abba
aabb
aabb
abba
abab
baab
baba
baab
baba
bbaa
bbaa
aabb
aabb
abab
abba
abab
abba
baba
baab
bbaa
bbaa
baab
baba
如你所见，我得到了很多重复。这部分是由于要求仅使用字符'a'和'b'。如果是“abcd”或“0123”，则不会发生重复。我已阅读有关使用arraylist并存储所有结果，然后循环遍历N个元素以检查重复项然后将其删除。这似乎不是最好的方法。有人可以分享其他更好的解决方案吗？ =）
我使用SortedSet的解决方案：
import java.util.Iterator;
import java.util.SortedSet;
import java.util.TreeSet;
public class BalancedStrings {
public static void main(String[] args){
printBalanced(4);
}
public static void printBalanced(int n){
String letters = "";
for(int i =0; i<n/2;i++){
letters += "ab";
}
SortedSet<String> results = balanced("",letters);
Iterator<String> it = results.iterator();
while (it.hasNext()) {
// Get element and print
Object element = it.next();
System.out.println(element);
}
}
//This method returns a SortedSet with permutation results. SortedSet was chosen for its sorting and not allowing
//duplicates properties.
private static SortedSet<String> balanced(String prefix, String s){
SortedSet<String> set = new TreeSet<String>();
int len = s.length();
//base case
if (len == 0){
//return the new SortedSet with just the prefix
set.add(prefix);
return set;
}
else{
SortedSet<String> rest = new TreeSet<String>();
for(int i = 0; i<len; i++){
//get all permutations and store in a SortedSet, rest
rest = balanced(prefix + s.charAt(i),s.substring(0,i)+s.substring(i+1,len));
//put each permutation into the new SortedSet
set.addAll(rest);
}
return set;
}
}
}
学分-http://k2code.blogspot.in/2011/09/permutation-of-string-in-java-efficient.html
public class Permutation {
public static void printDuplicates(String str,String prefix)
{
if(str.length()==0)
{
System.out.println(prefix);
}
else
{
for (int i = 0; i<str.length();i++)
{
if(i>0)
{
if(str.charAt(i)==str.charAt(i-1))
{
continue;
}
}
printDuplicates(str.substring(0, i)+str.substring(i+1, str.length()),prefix+str.charAt(i));
}
}
}
public String sort(string str){
// Please Implement the sorting function, I was lazy enough to do so
}
public static void main(String [] args)
{
String test="asdadsa";
test = sort(test);
printDuplicates(test,"");
}
}
您可以使用最常见的排列实现（使用第一个元素交换元素并将其余元素置换）。首先构建字符串，对其进行排序，然后生成所有可能的排列。不要重复。
实施可以是：
static String swap(String s, int i, int j) {
char [] c = s.toCharArray();
char tmp = c[i];
c[i] = c[j];
c[j] = tmp;
return String.copyValueOf(c);
}
static void permute(String s, int start) {
int end = s.length();
if(start == end) {
System.out.println(s);
return;
}
permute(s, start + 1);
for(int i = start + 1; i < end; i++) {
if(s.charAt(start) == s.charAt(i)) continue;
s = swap(s, start, i);
permute(s, start + 1);
}
}
public static void main(String [] args) {
String s = "aabb";
permute(s, 0);
}
产生输出：
aabb
abab
abba
baab
baba
bbaa
根据@ 0605002的代码，我修改了一下。在permute的for循环中，我们需要在permute方法调用之后再次交换。这就像回溯。我们需要将它交换回下一次迭代。
static void permute(String s, int start) {
int end = s.length();
if(start == end) {
System.out.println(s);
return;
}
permute(s, start + 1);
for(int i = start + 1; i < end; i++) {
if(s.charAt(start) == s.charAt(i)) continue;
s = swap(s, start, i);
permute(s, start + 1);
s = swap(s, start, i);
}
}