按字母顺序对ArrayList进行排序

Question

按字母顺序对ArrayList进行排序

4

我将尝试找出一个字符串的所有排列，并按字母顺序排序。

以下是我的代码：

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) + " ");
               }
       }
}

如果我输入字符串"toys"，我会得到以下结果：

toys tosy tyos tyso tsoy tsyo otys otsy oyts oyst osty osyt ytos ytso yots yost ysto ysot stoy styo soty soyt syto syot

我做错了什么？如何按字母顺序排列它们？谢谢！

- relyt

如果你这样写 permsList = Collections.sort(permsList);，它能正常工作吗？ - Paul Tomblin

Paul，Collections.sort不会返回任何值。 - Matthew Flaschen

@Paul Tomblin：那是无法编译的。它没有返回任何内容。它只是对给定的集合进行排序。集合不像“字符串”一样不可变。 - BalusC

如果在传递给 findPerms 之前对输入字符串 ("osty") 中的字母进行排序，就可以得到一个已排序的列表输出，而无需使用 Collections.sort。 - lins314159

5个回答

2

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

更重要的是，有一个很好的算法可以按字典顺序排列数组。它被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个元素的数组，这样做非常不好。

- Brian

0

你需要对findperms的返回结果进行排序，而不是在递归调用中进行排序。

- DVK

DVK，我觉得我知道你的意思，但你能再详细解释一下吗？ - relyt

@relyt - 我认为Amir的回答已经提供了足够的解释，如果还不清楚，请回复我，我会详细解释。 - DVK

0

看看这个：http://java.sun.com/j2se/1.5.0/docs/api/java/util/Collections.html#sort(java.util.List,%20java.util.Comparator)

- Gabriel Ščerbák

0

你可以将已经获得的所有排列放入一个 TreeSet 或 PriorityQueue 中，这将按顺序排列它们。然后，你需要将它们放回到你的 ArrayList 中。

或者你可以使用 Collections Sort 对你的 ArrayList 进行排序。

我建议选择最后一种选项。这里有一个例子，如果你不理解的话。

- twodayslate

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Amir Afghani · Accepted Answer

在完全填充之前，您正在从查找字符串的所有排列的递归方法中调用排序例程。

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);
            }

       }
}