重复排列 [英] Permutations with duplicates

问题描述

在我开始之前，我必须为提出另一个重复排列的案例道歉.我浏览了大部分搜索结果，并不能真正找到我要找的东西.我已阅读有关词典顺序并已实施.对于这个问题，我假设实现一个递归方法，该方法打印出所有长度为 n 的字符串，这些字符串仅由具有相同数量的 a 和 b 的字符 a 和 b 组成.字符串必须按词法顺序一次打印出一行.例如，一个电话:

Before I start, I have to apologize for bringing up another case of permutations with duplicates. I have gone through most of the search results and can't really find what I am looking for. I have read about the Lexicographical order and have implemented it. For this question, I am suppose to implement a recursion method that prints out the all the strings of length n consisting of just the characters a and b that have an equal number of a and b’s. The strings must be printed out one line at a time in lexical order. So, for example, a call:

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"，则不会发生重复.我已经阅读了关于使用数组列表并存储所有结果，然后循环遍历 N 个元素以检查重复项，然后将其删除.这似乎不是最好的方法.有人可以分享有关此问题的其他更好的解决方案吗?=)

As you can see, I get a lot of duplicates. This is partly due to the requirement to use only characters 'a' and 'b'. The duplicates will not happen if it was "abcd" or "0123". I have read about using an arraylist and store all the results and then loop through N elements to check for duplicates and then removing it. This does not seem to be the best way to do it. Can someone share about other better solutions for this problem? =)

我使用 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;

        }
    }

}

推荐答案

您可以使用 Set 并将结果存储在其中(最好是 SortedSet) 这将消除重复并在遍历时保持排序顺序.

You can use a Set and store the results in it (preferably SortedSet) this will eliminate duplicates and maintain a sorted order as well while traversal.

这篇关于重复排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！