Псевдокод: случайная перестановка

Question

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

Algorithm 1. RandPerm(N)
Input: Number of cities N
1) Let P = list of length N, (|P|=N) where pi=i
2) Let T = an empty list
3) While |P| > 0
4)    Let i = UI(1,|P|)
5)    Add pi to the end of T
6)    Delete the ith element (pi) from P
7) End While
Output: Random tour T

Вот код Java:

public static ArrayList<Integer> RandPerm(int n)
    {
        ArrayList<Integer> P = new ArrayList<>(n);
        ArrayList<Integer> T = new ArrayList<>();
        int i;

        while(P.size() > 0)
        {
            i = CS2004.UI(1, P.size());// generate random numbers between 1 and the size of P
            T.add(P.get(i));
            P.remove(P.get(i));
        }   
        return T;
    }

Я не знаю, что я делаю не так.

Answer 1

  ArrayList<Integer> p = new ArrayList<>(n);

... создает пустой список с начальной емкостью n,

Все это говорит ArrayList какой размер массива инициализировать в качестве резервного хранилища - большую часть времени вы не получите ничего полезного, указав это.

Так что ваши while(p.size() > 0) работает ноль раз, потому что p.size() это ноль в начале.

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

  for(int i=0;i<n;i++) {
     p.add(i)
  }

(Я поместил в нижний регистр имя вашей переменной - в Java существует соглашение для переменных startWithALowerCaseLetter - только имена классов StartWithUpperCase. Это также соглашение Java, которое дает переменным описательные имена, поэтому cityIdentifiers возможно)

Answer 2

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

Во-первых P.remove(P.get(i)) не обязательно удаляет i-й элемент, если список имеет элементы с одинаковым значением. Сканирует с начала и удаляет первое вхождение предмета. Смотрите ArrayList.remove (Object obj). Вы должны использовать P.remove(i) вместо правильных результатов.

Тогда производительность O(n^2). Причина в том, что ArrayList удаляет элемент, сдвигая все последующие элементы на один слот влево, что является операцией O(n). Чтобы получить гораздо лучшую производительность, вы можете реализовать свою собственную операцию удаления, поменяв элемент до конца. Когда вы генерируете следующий случайный индекс, генерируйте его в пределах диапазона [0, beginning index of the removed items at the end), Замена - это O(1), а общая производительность - O(n). Кстати, это называется Кнут Шаффл.