[發(fā)明專利]一種不重復(fù)隨機(jī)自然數(shù)的快速生成方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202110680934.4
• 申請(qǐng)日: 2021-06-18
• 公開(kāi)（公告）號(hào): CN113778380A
• 公開(kāi)（公告）日: 2021-12-10
• 發(fā)明（設(shè)計(jì)）人: 王璞;張亮;高舜龍;宋興瑞;羅英;季堯遙;張海豐
• 申請(qǐng)（專利權(quán)）人: 南京國(guó)科軟件有限公司
• 主分類號(hào): G06F7/58
• 分類號(hào): G06F7/58
• 代理公司: 北京化育知識(shí)產(chǎn)權(quán)代理有限公司 11833
• 代理人: 尹均利

本發(fā)明公開(kāi)了一種不重復(fù)隨機(jī)自然數(shù)的快速生成方法，定義兩個(gè)初值為空的集合S和集合T，定義一個(gè)長(zhǎng)度為M的一維數(shù)組F，并將F中每一個(gè)元素的數(shù)值初始化為1，即F[1:M]＝1。循環(huán)N次調(diào)用隨機(jī)生成函數(shù)，第k次調(diào)用隨機(jī)生成函數(shù)的Ω區(qū)域?yàn)棣?Sub>k＝[1,M?k+1]，其中k＝1,2,…,N，將每一個(gè)隨機(jī)生成數(shù)S_k，按順序存儲(chǔ)在S中。依次循環(huán)集合S中的每個(gè)元素S_k(k＝1,2,…,N)，計(jì)算出滿足的第一個(gè)索引J，將索引J添加到集合T中，并令F[J]＝0。返回集合T。此算法解決了在給定的自然數(shù)區(qū)域內(nèi)，能夠快速挑選出一部分不重復(fù)的自然數(shù)序列。

技術(shù)領(lǐng)域

本發(fā)明涉及自然數(shù)生成技術(shù)領(lǐng)域，尤其涉及一種不重復(fù)隨機(jī)自然數(shù)的快速生成方法。

背景技術(shù)

當(dāng)前，在氣象預(yù)報(bào)、油藏勘探、材料力學(xué)、物流交通、生物醫(yī)藥等各個(gè)領(lǐng)域中，計(jì)算機(jī)數(shù)值模擬占有不可比擬的重要性。不重復(fù)隨機(jī)自然數(shù)的生成在計(jì)算機(jī)數(shù)值模擬中又占有重要的地位，例如在模擬某一時(shí)刻的全國(guó)各城市天氣狀態(tài)時(shí)，要求全國(guó)30％的城市為多云，且這些城市在地圖上呈現(xiàn)等概率均勻分布；再例如對(duì)于某種二代基因測(cè)序儀芯片，芯片上共有1300萬(wàn)個(gè)小孔，要求85％的小孔中有微球存在，且存在微球的這些小孔在芯片上的位置呈現(xiàn)等概率均勻分布。具體的算法闡述如下：

給定自然數(shù)區(qū)域?yàn)棣福絒1,M]，要求從Ω中隨機(jī)生成N個(gè)不重復(fù)的數(shù)。需要注意的是，當(dāng)N＞M/2時(shí)，該問(wèn)題等價(jià)于先生成Ω中的所有數(shù)，然后再?gòu)钠渲刑蕹齅-N個(gè)不重復(fù)的數(shù)即可。也就是說(shuō)，只需要考慮從Ω中隨機(jī)生成N個(gè)不重復(fù)的數(shù)，且N≤M/2的情況。

傳統(tǒng)的生成不重復(fù)自然數(shù)的計(jì)算流程如下：

第一步：定義一個(gè)用于存儲(chǔ)不重復(fù)數(shù)字的集合S，并賦值為空。

第二步：在Ω內(nèi)隨機(jī)生成一個(gè)數(shù)α。

第三步：判斷α是否在S內(nèi)，若在，則重新進(jìn)行第二步；若不在，則將α加入S。

第四步：判斷S的個(gè)數(shù)是否不大于N，若是，則進(jìn)行第二步；若不是，則退出。

此計(jì)算流程無(wú)法解決在給定的自然數(shù)區(qū)域內(nèi)，能夠快速挑選出一部分不重復(fù)的自然數(shù)序列。

為此，我們提出一種不重復(fù)隨機(jī)自然數(shù)的快速生成方法來(lái)解決上述問(wèn)題。

發(fā)明內(nèi)容

本發(fā)明的目的是為了解決現(xiàn)有技術(shù)中存在的缺點(diǎn)，在給定的自然數(shù)區(qū)域內(nèi)，無(wú)法快速挑選出一部分不重復(fù)的自然數(shù)序列，而提出的一種不重復(fù)隨機(jī)自然數(shù)的快速生成方法。

為了實(shí)現(xiàn)上述目的，本發(fā)明采用了如下技術(shù)方案：一種不重復(fù)隨機(jī)自然數(shù)的快速生成方法，其特征在于，包括以下步驟：

S1：定義兩個(gè)初值為空的集合S和集合T，定義一個(gè)長(zhǎng)度為M的一維數(shù)組 F，并將F中每一個(gè)元素的數(shù)值初始化為1，即F[1:M]＝1。

S2：循環(huán)N次調(diào)用隨機(jī)生成函數(shù)，第k次調(diào)用隨機(jī)生成函數(shù)的Ω區(qū)域?yàn)棣?Sub>k＝[1,M-k+1]，其中k＝1,2,···,N，將每一個(gè)隨機(jī)生成數(shù)S_k，按順序存儲(chǔ)在S中。

S3：依次循環(huán)集合S中的每個(gè)元素S_k(k＝1,2,···,N)，計(jì)算出滿足的第一個(gè)索引J，將索引J添加到集合T中，并令F[J]＝0。

S4：返回集合T。

優(yōu)選的，所述集合T中的每個(gè)元素即是滿足條件的不重復(fù)的隨機(jī)自然數(shù)。

優(yōu)選的，所述假設(shè)生成一個(gè)隨機(jī)數(shù)的計(jì)算復(fù)雜度為p，比較兩個(gè)數(shù)大小的計(jì)算復(fù)雜度為q，加減法運(yùn)算的計(jì)算復(fù)雜度為r，則本設(shè)計(jì)的算法計(jì)算量可進(jìn)行如下分析：第二步的計(jì)算量為D₂＝Np+(N-1)r，第三步的計(jì)算量為