伪代码：随机排列

我有一个伪代码，我已经翻译成java代码，但任何时候我运行代码，我得到一个空arraylist作为结果，但它应该给我一个随机的整数列表。这里是伪代码：伪代码：随机排列

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

我不知道我做错了。

来源

2017-04-20 Exi-G

从你的代码中，'P'总是空的，你永远不会添加任何东西。还要注意，你传递的'n'是初始容量，但列表的大小是'0'。 – Berger

while循环从不执行，因为P开始空。通过给它“n”，你只是在它的后备阵列中分配了那么多的初始空间。 – satnam

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

...有初始容量的n创建空列表。

所有这一切都告诉ArrayList什么大小的数组初始化为后备存储 - 大多数情况下，您通过指定这些数据没有用处。

因此，您的while(p.size() > 0)运行零次，因为p.size()在开始时为零。

在伪“其中pi =我”要初始化列表这样的建议对我说：

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

（我小写的变量名 - 在Java中的惯例是变量startWithALowerCaseLetter - 只有类名称StartWithUpperCase。这也是Java惯例给变量描述性名称，所以cityIdentifiers也许）

来源

2017-04-20 15:40:29 slim

如果我尝试使用for循环填充P这个错误：线程“main”java.lang.IndexOutOfBoundsException中的异常：索引：9，大小：9 \t at java.util.ArrayList.rangeCheck（Unknown Source） \t at java.util.ArrayList.get（来源不明） \t在Lab15.Lab15.RandPerm（Lab15.java:54） \t在Lab15.Lab15.main（Lab15.java:28） –

的消息告诉你到底是什么错误是'IndexOutOfBoundsException：Index：9，Size：9' - 你试图'get'索引9.列表的大小是9，所以你只能从0到8获得索引。你或者需要确保那'CS2004。UI（）'返回一个范围内的索引，或者操作它返回的内容以使其处于范围内。 – slim

我可以通过从随机数'i = CS2004.UI（1，P.size（）） - 1'中减去1来得到它的工作;'现在显示随机数 –

你可能想知道，即使你解决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）。顺便说一下，这叫做Knuth Shuffle。

来源

2017-04-20 16:03:47 neurite

伪代码：随机排列

回答

相关问题