伪代码：随机排列

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 命名 - 只有 class 命名为 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) 操作。为了获得更好的性能，您可以通过将项目交换到末尾来实现自己的 "remove" 操作。生成下一个随机索引时，在[0, beginning index of the removed items at the end)范围内生成。交换是 O(1)，整体性能是 O(n)。顺便说一下，这叫做 Knuth Shuffle。

伪代码：随机排列

Pseudo code: Random Permutation

java

pseudocode