Java

Question

我这里有一个简单的程序，用于查找一组字母或一组单词的所有排列。据我所知，该程序确实可以找到存在的排列数，但是它只会打印空行来代替可能的排列。（注意，UI.println() 在打印大纲的所有其他情况下都有效，但由于某些原因在这里不起作用:( )

我在这里包含了我的方法，它应该按照我所描述的那样进行，以及一个应该能够打印出排列的方法。

有人对我在这里做错了什么有什么想法吗？


public class Permutations {

    public List<List<String>> findPermutations(Set<String> items){

        Set<String> copyOfItems = new HashSet<String>(items);   // a copy of the set of items that can be modified
        List<List<String>> ans = new ArrayList<List<String>>(); // where we will collect the answer
        counter=0;
        //suggested approach:
        extendPermutation(copyOfItems, new Stack<String>(), ans);   

        return ans;
    }

   
    public void extendPermutation(Set<String> remainingItems, Stack<String> permutationSoFar, List<List<String>> allPermutations){
        /*# YOUR CODE HERE */
        Set<String> alternateSet = new HashSet<String>(remainingItems);
        if (remainingItems.isEmpty()) {
            allPermutations.add(permutationSoFar);
            this.counter = counter + 1;
        } 
        for (String str : remainingItems) {
            alternateSet.remove(str);
            permutationSoFar.push(str);
            extendPermutation(alternateSet,permutationSoFar,allPermutations);
            permutationSoFar.pop();
        }
    
        

    }

  
    public void setupGUI(){
        UI.addButton("A B C D E", ()->{printAll(findPermutations(Set.of("A","B","C","D","E")));});
        UI.addTextField("Letters", (String v)->{printAll(findPermutations(makeSetOfLetters(v)));});
        UI.addTextField("Words", (String v)->{printAll(findPermutations(makeSetOfWords(v)));});
        UI.addButton("Quit", UI::quit);
        UI.setDivider(1.0);
    }

    public void printAll(List<List<String>> permutations){
        UI.clearText();
        for (int i=0; i<permutations.size(); i++){
            for (String str : permutations.get(i)){UI.print(str+" ");}
            UI.println();
        }
        UI.println("----------------------");
        UI.printf("%d items:\n", permutations.get(0).size());
        UI.printf("%,d permutations:\n", counter);
        UI.println("----------------------");
    }

   
    public Set<String> makeSetOfLetters(String str){
        Set<String> ans = new HashSet<String>();
        for (int i=0; i<str.length(); i++){
            if (str.charAt(i)!=' '){
                ans.add(""+str.charAt(i));
            }
        }
        return Collections.unmodifiableSet(ans);
    }

   
    public Set<String> makeSetOfWords(String str){
        Set<String> ans = new HashSet<String>();
        for (String v : str.split(" ")){ans.add(v);}
        return Collections.unmodifiableSet(ans);
    }

    // Counter for the number of complete permutations found
    private long counter = 0;  

    
    public void reportCounter(){
        if ((counter<<54)==0) {UI.printMessage((counter>10000000)?((counter>>>20)+"M"):((counter>>>10)+"K"));}
    }

    // Main
    public static void main(String[] arguments) {
        Permutations p = new Permutations();
        p.setupGUI();
    }
}

Answer 1

您的代码

permutationSoFar.push(str);
extendPermutation(alternateSet, permutationSoFar, allPermutations);
permutationSoFar.pop();

您首先向 permutationSoFar 添加一个项目，然后您将 permutationSoFar 的引用（不是深拷贝）添加到您的 allPermutations，仅用于弹出 permutationSoFar。确保您的 permutationSoFar 从不包含任何元素。

当您打印 permutationSoFars 的列表时，即 allPermutations，您将打印一个空列表的列表。

看看你的问题，这可能会解决问题：

allPermutations.add(List.copyOf(permutationSoFar));

但是，坦率地说，它就像您的其余代码，不是最干净的解决方案。

Java - HashSet 的打印值

Java - printing values of HashSet

hashset