java - 伪代码: Random Permutation

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() 在开始时为零。

在伪代码“where pi=i”中，我建议您要像这样初始化列表:

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

(我已经小写了你的变量名 - 在 Java 中，变量的约定是 startWithALowerCaseLetter - 仅限类名 StartWithUpperCase。这也是 Java 约定给变量提供描述性名称，所以也许是城市标识符)