2017-02-19 71 views
0

我需要找到給定的n(用戶輸入)沒有回溯的所有排列。Java設置/ setElementAt沒有設置正確的值

我的嘗試是:

import java.util.Scanner; 
import java.util.Vector; 

class Main { 

    private static int n; 
    private static Vector<Vector<Integer>> permutations = new Vector<>(); 



    private static void get_n() { 

     Scanner user = new Scanner(System.in); 

     System.out.print("n = "); 

     n = user.nextInt(); 
    } 
    private static void display(Vector<Vector<Integer>> permutations) { 

     for (int i = 0; i < factorial(n) - 1; ++i) { 
      for (int j = 0; j < n; ++j) { 
       System.out.print(permutations.elementAt(i).elementAt(j) + " "); 
      } 
      System.out.println(); 
     } 
    } 



    private static int factorial(int n) { 

     int result = 1; 

     for (int i = 1; i <= n; ++i) { 

      result *= i; 
     } 

     return result; 
    } 
    private static int max(Vector<Integer> permutation) { 

     int max = permutation.elementAt(0); 

     for (int i = 1; i < permutation.size(); ++i) 
      if (permutation.elementAt(i) > max) 
       max = permutation.elementAt(i); 

     return max; 
    } 



    // CHECKS FOR ELEMENT COUNT AND 0 - (n-1) APPARITION 
    public static int validate_permutation(Vector<Integer> permutation) { 

     // GOOD NUMBER OF ELEMENTS 
     if (max(permutation) != permutation.size() - 1) 
      return 0; 

     // PROPER ELEMENTS APPEAR 
     for (int i = 0; i < permutation.size(); ++i) 
      if (!permutation.contains(i)) 
       return 0; 

     return 1; 
    } 

    private static Vector<Integer> next_permutation(Vector<Integer> permutation) { 

     int i; 

     do { 
      i = 1; 

      // INCREMENT LAST ELEMENT 
      permutation.set(permutation.size() - i, permutation.elementAt(permutation.size() - i) + 1); 

      // IN A P(n-1) PERMUTATION FOUND n. "OVERFLOW" 
      while (permutation.elementAt(permutation.size() - i) == permutation.size()) { 

       // RESET CURRENT POSITION 
       permutation.set(permutation.size() - i, 0); 

       // INCREMENT THE NEXT ONE 
       ++i; 
       permutation.set(permutation.size() - i, permutation.elementAt(permutation.size() - i) + 1); 
      } 
     } while (validate_permutation(permutation) == 0); 


     // OUTPUT 
     System.out.print("output of next_permutation:\t\t"); 
     for (int j = 0; j < permutation.size(); ++j) 
      System.out.print(permutation.elementAt(j) + " "); 
     System.out.println(); 

     return permutation; 
    } 

    private static Vector<Vector<Integer>> permutations_of(int n) { 

     Vector<Vector<Integer>> permutations = new Vector<>(); 

     // INITIALIZE PERMUTATION SET WITH 0 
     for (int i = 0; i < factorial(n); ++i) { 

      permutations.addElement(new Vector<>()); 

      for(int j = 0; j < n; ++j) 
       permutations.elementAt(i).addElement(0); 
     } 


     for (int i = 0; i < n; ++i) 
      permutations.elementAt(0).set(i, i); 

     for (int i = 1; i < factorial(n); ++i) { 

      // ADD THE NEXT PERMUTATION TO THE SET 
      permutations.setElementAt(next_permutation(permutations.elementAt(i - 1)), i); 

      System.out.print("values set by permutations_of:\t"); 
      for (int j = 0; j < permutations.elementAt(i).size(); ++j) 
       System.out.print(permutations.elementAt(i).elementAt(j) + " "); 
      System.out.println("\n"); 
     } 

     System.out.print("\nFinal output of permutations_of:\n\n"); 
     display(permutations); 

     return permutations; 
    } 



    public static void main(String[] args) { 

     get_n(); 

     permutations.addAll(permutations_of(n)); 
    } 
} 

現在,當運行代碼時的問題是顯而易見的。 next_permutation在被調用時輸出正確的排列,這些值被正確設置爲相應的排列向量,但最終結果是最後排列的質量副本,這導致我相信每次通過next_permutation輸出新的排列並且設置成排列向量,以某種方式排列也被複制到全部的其他排列。而我無法弄清楚爲什麼我的生活。

我嘗試了set,​​setElementAt和一個實現,其中我沒有初始化排列矢量拳頭,但添加了排列,因爲他們是由next_permutation與add()輸出的,我碰到了完全相同的問題。 Java處理內存有一些奇怪的方法嗎?或者這是什麼原因?

預先感謝您!

回答

0
permutations.setElementAt(next_permutation(permutations.elementAt(i - 1)), i); 

這是字面上設置在矢量permutations(i)同一對象作爲permutations[i-1]。不同的價值 - 完全相同的對象。我認爲這是你問題的根源。您需要複製矢量中的值。