Сортировать ArrayList по алфавиту

Question

Я пытаюсь найти все перестановки строки и отсортировать их по алфавиту.

Это то, что я имею до сих пор:

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

ЕСЛИ я ввожу строку "игрушки", я получаю:

игрушки тосы тёс тысо цой цё оты отсы ойц ойст осты осыт итос йсо йотс йост исто йсот стой стай соты сой сыт сыто сьот

Что я делаю не так. Как я могу получить их в алфавитном порядке? Спасибо!

Answer 1

Вы вызываете свою процедуру сортировки из рекурсивного метода, который находит все перестановки вашей строки, до того, как она будет полностью заполнена

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

       }
}

Answer 2

Некоторые комментарии уже указывают на то, что ваша рекурсивная процедура не может выполнить сортировку в конечных узлах и ожидает сортировки всего списка. Вам нужно будет вернуть накопленные строки в коллекцию, а затем отсортировать и распечатать их один раз в конце.

Что еще более важно, есть хороший алгоритм для перестановки массива в лексическом порядке. Она используется библиотечной функцией next_permutation в C ++ (которую вы можете найти для объяснений), но ее достаточно легко перевести на 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 или около того элементов.

Answer 3

Вы можете поместить все перестановки, которые вы уже получили, и поместить их в TreeSet или PriorityQueue, которые приведут их в порядок.Затем вам нужно будет положить их обратно в ваш ArrayList.

Или вы можете использовать Сортировку коллекций , которая сортирует ваш ArrayList.

Я рекомендую последний вариант. Вот пример , если вы этого не понимаете.

Answer 4

Проверьте это: http://java.sun.com/j2se/1.5.0/docs/api/java/util/Collections.html#sort(java.util.List,%20java.util.Comparator)

Answer 5

Вам нужно отсортировать результаты вызова findperms, а не внутри рекурсивного вызова.