按字母顺序排列ArrayList

问题描述：

我试图找到字符串的所有排列并按字母顺序对它们进行排序。按字母顺序排列ArrayList

这是我到目前为止有：

public class permutations { 

     public static void main(String args[]) { 
      Scanner s = new Scanner(System.in); 
      System.out.print("Enter String: "); 
      String chars = s.next(); 
      findPerms("", chars); 
     } 

     public static void findPerms(String mystr, String chars) { 

      List<String> permsList = new ArrayList<String>(); 

       if (chars.length() <= 1) 
         permsList.add(mystr + chars); 
         //System.out.print(mystr + chars + " "); 

       else 
         for (int i = 0; i < chars.length(); i++) { 
          String newString = chars.substring(0, i) + chars.substring(i + 1); 
          findPerms(mystr + chars.charAt(i), newString); 
         } 

       Collections.sort(permsList); 

       for(int i=0; i<permsList.size(); i++) { 
        System.out.print(permsList.get(i) + " "); 
       } 
     } 
}

如果我输入一个字符串 “玩具”，我得到：

玩具甲苯磺酰tyos tyso tsoy tsyo otys otsy oyts oyst osty osyt YTOS YouTube交响乐团yots约斯特ysto ysot stoy styo soty soyt syto syot

我在做什么错。我怎样才能按字母顺序排列他们？谢谢！

它是否工作，如果你让它'permsList = Collections.sort（permsList）;' – 2010-03-23 01:05:18

Paul，Collections.sort不会返回一个值。 – 2010-03-23 01:09:04

@Paul Tomblin：那不会编译。它不会返回任何东西。它只是对给定的集合进行排序。集合不是像String一样不可变的。 – BalusC 2010-03-23 01:09:30

答

你从找到你的字符串的所有排列的递归方法中调用你的排序过程，之前它已经完全填充

import java.util.*; 

public class permutations { 

     public static void main(String args[]) { 
      Scanner s = new Scanner(System.in); 
      System.out.print("Enter String: "); 
      String chars = s.next(); 
      List<String> myList = new ArrayList<String>(); 
      findPerms(myList, "", chars); 

      Collections.sort(myList); 

      for(int i=0; i<myList.size(); i++) { 
       System.out.print(myList.get(i) + " "); 
      } 

     } 

     public static void findPerms(List<String> permsList, String mystr, String chars) { 

      if (chars.length() <= 1) 
       permsList.add(mystr + chars);  
      else 
      for (int i = 0; i < chars.length(); i++) { 
       String newString = chars.substring(0, i) + chars.substring(i + 1); 
       findPerms(permsList, mystr + chars.charAt(i), newString); 
      } 

     } 
}

该列表还应该递归传递（而不是不断重新初始化）。打印件应该移出探针。 – 2010-03-23 01:11:13

同意 - 我打算在第二个帖子中发帖 – 2010-03-23 01:14:59

，您发布的代码不会按原样编译。你应该解决这个问题。如果我可以，我会但我没有2000代表尚未;） – 2010-03-23 01:19:56

答

您需要findperms的调用的结果进行排序，而不是内部召回呼吁。

DVK我想我知道你的意思，但是你能扩大一点吗？ – relyt 2010-03-23 01:10:14

@relyt - 我认为Amir的答案提供了足够的解释，如果不是，请回复，我会详细说明 – DVK 2010-03-23 01:22:33

答

检查了这一点：http://java.sun.com/j2se/1.5.0/docs/api/java/util/Collections.html#sort(java.util.List,%20java.util.Comparator)

答

你可以把所有你已经得到了置换，把他们在一个TreeSet或PriorityQueue将整理好。您将不得不将它们放回到ArrayList中。

或者你可以使用一个Collections Sort排序你的ArrayList。

我推荐最后一个选项。 Here is an example如果你不明白。

答

一些评论已经指出，递归例程不能在叶节点上进行排序，并期望排序整个列表。您必须将集合的字符串返回到集合中，然后在最后对它们进行排序和打印。

更重要的是，有一个很好的算法用于以词法顺序排列数组。它被C++中的next_permutation库函数使用（你可以查找解释），但是它很容易翻译成java。你提取一个char[]数组，也许使用getCharArray，用Arrays.sort对它进行排序，并运行它直到它返回false。

/** Helper function */ 
void reverse(char[] a, int f, int l) 
    { 
    while(l>f) 
    { 
    char tmp = a[l]; 
    a[l] = a[f]; 
    a[f] = tmp; 
    l--; f++; 
    } 
    } 

/** actual permutation function */ 
boolean next_permutation(char[] a) 
    { 
    if(a.length < 2) return false; 
    for(int i = a.length-1; i-->0;) 
    if(a[i] < a[i+1]) 
    { 
    int j=a.length-1; 
    while(!(a[i] < a[j])) 
     j--; 
    char tmp=a[i]; 
    a[i]=a[j]; 
    a[j]=tmp; 
    reverse(a, i+1, a.length-1); 
    return true; 
    } 
    reverse(a, 0, a.length-1); 
    return false; 
    }

一旦你明白了它的作用，只需运行while(next_permutation(array)) {println(array);}，你做得很好。请注意，这对于超过13个元素的数组非常不利。

+1用于排序字符，而不是排列。 – msandiford 2010-03-23 02:18:22

按字母顺序排列ArrayList

相关推荐