是否存在一种算法，可以在O(n)时间内生成一个与原列表{a1, a2, a3, ..., ak}中符号相同但随机顺序的新列表而不带有偏见？ “没有偏见”意味着任何符号s以1/k的概率出现在列表的某个位置p中。
假设可以在O(1)时间内生成1-k之间的非有偏整数。还假设可以进行O(1)元素访问/修改，并且可以在O(k)时间内创建大小为k的新列表。
特别是对于“生成性”算法感兴趣。也就是说，我对一种算法感兴趣，它具有O(1)的初始开销，并且然后每个插槽产生一个新元素，每个插槽需要O(1)的时间。
如果问题的描述中不存在解决方案，则仍然想了解以下不满足我的约束条件（和/或其他必要方式）的解决方案：
- 时间复杂度差于O(n)。 - 算法对于符号的最终位置存在偏差。 - 算法不具备生成性。
应该指出，这个问题似乎与从1-k随机排序整数的问题相同，因为我们可以对1-k的整数列表进行排序，然后对于新列表中的每个整数i，我们可以生成符号ai。
假设可以在O(1)时间内生成1-k之间的非有偏整数。还假设可以进行O(1)元素访问/修改，并且可以在O(k)时间内创建大小为k的新列表。
特别是对于“生成性”算法感兴趣。也就是说，我对一种算法感兴趣，它具有O(1)的初始开销，并且然后每个插槽产生一个新元素，每个插槽需要O(1)的时间。
如果问题的描述中不存在解决方案，则仍然想了解以下不满足我的约束条件（和/或其他必要方式）的解决方案：
- 时间复杂度差于O(n)。 - 算法对于符号的最终位置存在偏差。 - 算法不具备生成性。
应该指出，这个问题似乎与从1-k随机排序整数的问题相同，因为我们可以对1-k的整数列表进行排序，然后对于新列表中的每个整数i，我们可以生成符号ai。