Сформировать последовательность всех перестановок некоторого диапазона чисел части II

Question

Как следовать до Generate a sequence of all permutation of some range of numbers, я написал следующий код внутри класса Пермь:

/** 
* Permute A to its next permutation, if possible. Returns true if there is 
* such a permutation, and false otherwise. 
*/ 
static boolean nextPerm(int[] A) { 
    int N = A.length; 
    int k = N - 1; 
    int v; 
    Set<Integer> S = new HashSet<Integer>(); 

    while (k >= 0) { 
     int max = Collections.max(S); 
     if (max > A[k]) { 
      v = Collections.min(S); 
      S.remove(v); 
      S.add(A[k]); 
      A[k] = v; 
      int [] sArr = convertToArray(S); 
      for (int i = k + 1; i < N - 1; i += 1) { 
       A[i] = sArr[i - k - 1]; 
      } 
      return true;  
     } else { 
      S.add(A[k]); 
      k -= 1; 
     } 
    } 
    return false; 
} 

static int [] convertToArray (Set<Integer> s) { 
    int [] sArr = new int[s.size()]; 
    int index = 0; 
    for(Integer i : s) { 
     sArr[index++] = i; 
    } 
    Arrays.sort(sArr); 
    return sArr; 
} 

В принципе, то, что он делает для генерации последовательность всех перестановок некоторого диапазона чисел, следующим образом:

Let A be a sequence of integers 0 to N-1 in ascending order 
(let's assume its an array of int[N]).  

next_permutation(A): 
    k = N-1 
    S = { } 
    while k >= 0: 
     if S contains a value larger than A[k]: 
      v = the smallest member of S that is larger than A[k] 
      remove v from S 
      insert A[k] in S 
      A[k] = v 
      A[k+1:N-1] = the values in S in ascending order. 
      return true 
     else: 
      insert A[k] in S 
      k -= 1 
    return false 

Мой код не похоже на работу Тхо. Может кто-нибудь пролить некоторые огни, пожалуйста? Благодаря!

ОБНОВЛЕНИЕ: После того, как вы приняли все данные и немного поработали над проблемой, я смог заставить ее работать! Есть несколько вещей, которые я узнал:

1. Как отметил Worakam, TreeSet (по сравнению с HashSet) поставляется в очень удобно в этом вопросе, как сортируется и имеет функцию выше().
2. Первоначально я думал, что превращение TreeSet в массив Integer будет беспокойным, поскольку объекты Integer не совсем int. Однако, оказывается, что (возможно, из-за autoboxing/unboxing post java5), я смог обрабатывать элементы в массиве Integer как обычные int и добавлять к нему объекты int (как показано в цикле for).

Вот рабочий код:

static boolean nextPerm(int[] A) { 
    int N = A.length; 
    int k = N - 1; 
    int v; 
    int max = 0; 

    TreeSet<Integer> S = new TreeSet<Integer>(); 

    while (k >= 0) { 
     if (!S.isEmpty() && S.last() > A[k]) { 
      v = S.higher(A[k]); 
      S.remove(v); 
      S.add(A[k]); 
      A[k] = v; 
      Integer [] sArr = new Integer[S.size()]; 
      S.toArray(sArr); 

      for (int i = k + 1; i < N; i += 1) { 
       A[i] = sArr[i - k - 1]; 
      } 
      return true; 
     } else { 
      S.add(A[k]); 
      k -= 1; 
     } 
    } 
    return false; 
} 

Большое спасибо всем !!

Answer 1

Во-первых, Collections.max(S) throws NoSuchElementException, когда набор пуст.

Во-вторых, выбор наименьшего члена S является неправильным способом реализации «наименьшего члена S, который больше A [k]».

Я предлагаю, чтобы вместо использования HashSet вы должны использовать отсортированную структуру данных, такую ​​как java.util.TreeSet. Это устранит необходимость сортировки самого набора. И метод higher() может быть очень полезен для ваших нужд.