算法/功能，在O（1）返回数组中的随机数，并创建一个排列 [英] Algorithm/function that returns random number in array in O(1) and creates single permutation

问题描述

简介：这是一个面试问题我有，我没能解决。一个code解决方案将是（在任何语言）好，但​​算法/伪code也很大。

Intro: This is an interview question I had which I couldn't solve. A code solution will be good (in any language), but an algorithm/pseudocode is also great.

问题：这个问题是有关设计，解决了以下问题的算法：结果
您将得到一个函数 INT getRand（INT X），获取一个 INT X 并返回 INT 的范围为 0 到 X 随机（独家 - > [0，K））。到每个呼叫getRand（）中的 0（1）执行 的时间。
您也给予尺寸阵列 INT []改编 K 包含整数。

The problem: This problem is about designing an algorithm that solves the following problem:
You are given a function int getRand(int x) that gets an int x and returns an int in the range from 0 to x randomly (exclusively -> [0, k) ). Each call to getRand() is performed in O(1) time. You are also given an array int[] arr of size k containing integers.

写一个函数 getRandUnique（）调用返回时的从随机的成员改编这样，经过 K 请求正是你将有成员改编（这实际上意味着， getRandUnique（）将返回的不同的 的改编为每次调用成员）。
到每个呼叫getRandUnique（）在 0要进行（1） 的时间。结果
你被允许使用/存储全局变量等等...

Write a function getRandUnique() that when called will return a random member from arr such that after k requests exactly you will have a full permutation of the members of arr (this actually means that getRandUnique() will return a different member of arr for each call). Each call to getRandUnique() has to be performed in O(1) time.
You are allowed to use/store global variables etc...

例如：假设 ARR = [2，3，5，1] 。调用到 getRandUnique（）将返回要么 2，3，5，1 在 1 / 4 概率。随之调用 getRandUnique（）将在返回上剩余的 3 成员的1 / 3 概率等等...

E.g.: Assume arr = [2, 3, 5 , 1]. A call to getRandUnique() will return either 2, 3, 5, 1 in 1/4 probability. A consequent call to getRandUnique() will return on of the remaining 3 members in 1/3 probability and so on...

尝试：其实我这个解决自己并发布（多试错之后）该解决方案Q＆安培; A型。我很想得到一些其他可能的想法/解决方案。我会接受，它作为正确答案的任何解决方案（我不想接受我自己）！

Attempt: I actually solved this myself (after much trial and error) and posted the solution "Q&A Style". I would love to get some other possible ideas/solutions. I will accept any solution that works as the correct answer (I don't want to accept my own)!

问：如何可以在此与所有上述限制实现

Question: How can this be achieved with all the above restrictions?

编辑：现在我知道，这个问题对应于费雪耶茨洗牌，即使规格有一点点不同的/更加严格这里。

Now I am aware that this problem corresponds to the Fisher–Yates shuffle, even though the specifications are a little different/more strict here.

推荐答案

我的解决方案如下：

• 定义指数= 0 。

呼叫并分配指数= getRand（K）（记住， K 是大小改编）。

Call and assign index = getRand(k) (remember that k is the size of arr).

交换改编[指数] 与改编[K] 。

现在你有一个数组改编这是其自身的随机置换的要求（甚至不需要额外的数组）。

Now you have an array arr that is a random permutation of itself as requested (don't even need an additional array).

这篇关于算法/功能，在O（1）返回数组中的随机数，并创建一个排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！