Алгоритм нахождения всех перестановок для n алфавитов

Question

Я написал следующий алгоритм для поиска всех возможных перестановок n уникальных алфавитов.

Set<String> results = new HashSet<String>();
    int size = 1;
            //find the total permutations possible
    for(int i=0;i<array.length;i++){
        size*=(i+1);            
    }
    // i is the number of items remaining to be shuffled.
    while(results.size()<size){
        for (int i = array.length; i > 1; i--) {
            // Pick a random element to swap with the i-th element.
            int j = rng.nextInt(i);  // 0 <= j <= i-1 (0-based array)
            // Swap array elements.
            char tmp = array[j];
            array[j] = array[i-1];
            array[i-1] = tmp;
        }
        StringBuffer str = new StringBuffer();          
        for(int i=0;i<array.length;i++)
            str.append(array[i]);
        results.add(str.toString());
    }
    System.out.println(results);

1) Что нужно сделать, чтобы улучшить этот алгоритм?
2) Какова временная сложность этого алгоритма?

PS: Я прошу прощения у людей, которые отреагировали на мой предыдущий пост . Я попробую самостоятельно, прежде чем просить о помощи.

Answer 1

1) Что нужно сделать, чтобы улучшить этот алгоритм?

Да.Просто чтобы дать вам несколько советов, как вы могли бы генерировать перестановки детерминистически:

• представьте лексикографический порядок всех перестановок на N элементах.Представьте себе, как вы могли бы генерировать следующую перестановку в таком порядке, если бы предыдущий

• подумал о том, что будет набор перестановок с общим префиксом (например, 435 126, 435 162 и т. Д.) И как вы могли бы использовать его в алгоритме.

Answer 2

Используя случайную перетасовку, вы будете иметь массивное количество итераций, которые в итоге не добавят новый элемент в набор - вы должны искать подход, который гарантирует, что на каждом итерация: новый элемент помещается в набор (под «новым» я подразумеваю перестановку, которая ранее не была видна).

Мне бы не хотелось догадываться, насколько сложен алгоритм, представленный выше, - он будет большим.

Answer 3

Лучший способ генерировать перестановки - это делать это итеративно: найти схему перехода от одной перестановки к другой, пока вы не увидите их все.Кнут раскрыл такую ​​схему в одной из комбинаторных глав TAOCP, и, не вдаваясь в его псевдокод, подобный сборке, вы можете проверить эти изящные C-реализации этих алгоритмов .Алгоритм, который вы ищете, - это тот, который генерирует перестановки.

Преимущество такого алгоритма в том, что он противостоит (как я понимаю) вашему, состоит в том, что он является детерминированным и будет генерировать различные перестановки каждый раз.

Answer 4

Спасибо за ваш вклад. Я думаю, что у меня есть лучший алгоритм. Пожалуйста, предоставьте комментарии

private static List<String> allPerms(char[] array) {    
  List<String> perms = new ArrayList<String>();
  if(array.length<=1 )
      perms.add(String.valueOf(array[0]));
  else{
      char[] newarray = Arrays.copyOf(array, array.length-1);
      char lastChar = array[array.length-1];
      List<String> soFar = allPerms(newarray);
      for(int i=0; i<soFar.size(); i++) {       
          String curr = soFar.get(i);
          for(int j=0;j<array.length;j++){
              StringBuffer buff = new StringBuffer(curr);
              perms.add(buff.insert(j, lastChar).toString());                 
          }
      }       
    }
return perms; }