CODEWITHSUNDEEP
javapseudocode
Exi-G
Exi-G

Reputation: 33

Pseudo code: Random Permutation

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.

Upvotes: 0

Views: 719

Answers (2)

neurite
neurite

Reputation: 2824

You may want to know that, even if you fix the problem that P is always empty, there are 2 more issues with your implementation.

One is that P.remove(P.get(i)) does not necessarily remove the ith item if the list has equal value items. It scans from the beginning and removes the first occurrence of the item. See ArrayList.remove(Object obj). You should use P.remove(i) instead for the correct results.

Then the performance is O(n^2). The reason is that ArrayList remove an item by shifting all the subsequent items one slot to the left, which is an O(n) operation. To get a much better performance, you can implement your own "remove" operation by swapping the item to the end. When you generate the next random index, generate it within the range [0, beginning index of the removed items at the end). Swapping is O(1) and the overall performance is O(n). This is called Knuth Shuffle by the way.

Upvotes: 0

slim
slim

Reputation: 41271

  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)

Upvotes: 1

Related Questions