Алгоритм поиска всех перестановок для 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: Я приношу свои извинения людям, которые отреагировали на мой previous post. Я попробую самостоятельно, прежде чем обращаться за помощью.

Answer 1

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

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

Answer 2

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

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

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

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

Answer 3

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

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

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