Pseudo code: Random Permutation

Question

I have a pseudo code that I have translated into java code but anytime I run the code, I get an empty arraylist as a result but it is supposed to give me a random list of integers. Here is the pseudo code:

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

Here is the java code:

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

I don't know what I am doing wrong.

Answer 1

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

... creates an empty list with an initial capacity of n.

All this does is tell the ArrayList what size array to initialise as backing store - most of the time you achieve nothing useful by specifying this.

So your while(p.size() > 0) runs zero times, because p.size() is zero at the start.

In the pseudocode "where pi=i" suggests to me that you want to initialise the list like this:

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

(I have lowercased your variable name - in Java the convention is for variables to startWithALowerCaseLetter -- only class names StartWithUpperCase. It's also the Java convention to give variables descriptive names, so cityIdentifiers perhaps)