2

我想在 [1,n] 范围内生成 2n-1 个随机整数，每个元素出现两次，但随机值仅出现一次。
例如：

n = 3  
seq = [1, 2, 3, 1, 3]

在这个例子中 2 只出现一次。

我的算法是使用字典，如下所示：

-------------
| 数 |次|
| 1 | 2 |
| 2 | 1 |
| 3 | 2 |

其中键是从 1 到 n，值表示键的出现次数。我用 2 的值填充字典，并将一个随机键的值减少到 1。

  1. 有没有其他算法？
  2. 如果n很大导致无法存储在内存中怎么办？
4

5 回答 5

9

我不确定我是否 100 确定你在追求什么，但这里是一个尝试：

import random as rn

x = range(3)*2 #generate a list where each number appears twice

rn.shuffle(x) #shuffle it
x.pop()       #remove one number

结果：

>>> x
[2, 0, 2, 1, 0] #the result is a list where every number appears twice, except for
                #one number which was removed at random, also the numbers are 
                #randomly arranged

编辑：

这是对非常大的 n 执行此操作的尝试（该大小的列表无法存储在您的 ram 中的 n）。我看不到如何洗牌整数。但是，我可以随机删除一个。假设您要将列表写入 txt 文件。

drop = rn.range(0,n) #choose a random integer to drop

with open('my_file.txt','w') as f:
    for ind,ele in enumerate(xrange(n)):  
        if ind == drop: #do not write the element to txt file
            pass
        else:
            f.write(str(ele) + '\n') #write every except for one element to txt file

with open('my_file.txt','a') as f:
    for ele in xrange(n):
        f.write(str(ele) + '\n') # write every element to txt file

最后，我们将 n-1 个元素写入 txt 文件两次，一次写入 1 个元素，该元素是随机选择的。

对于 n = 5，txt 文件如下所示：

0
2
3
4
0
1
2
3
4

在上述情况下，1 只出现一次，每隔一个数字出现两次。

于 2012-05-23T04:08:48.853 回答
0

与@Akavall 一样，不确定我是否理解正确。您想生成 2n-1 个在 1 到 n 范围内的数字（包括我假设的 n）。那么这些数字并不是真正随机的，只有出现 1 次的数字。

import random

n=3

# Generate n numbers
numbers = [i for i in range(1,n+1)]
# Concatenate list to itself (now have 2n numbers)
numbers *= 2
# Remove a random element in the list (now have 2n-1 numbers)
numbers.pop( random.randint(0, len(numbers)-1) )

# Print results
from collections import Counter
print( Counter(numbers) )

输出

Counter({1: 2, 3: 2, 2: 1})
于 2012-05-23T04:15:55.323 回答
0

2․ 如果n很大导致无法存储在内存中怎么办？

取决于您想对这些数字做什么以及顺序是否重要。从您呈现表格的方式来看，我会说您不关心顺序，因此即使使用很大n，编码整个表格所需的实际信息量也非常少：n它本身和只有一个的索引入口。

如果您认为内存将成为问题，那么完全改变您的方法可能会更好，但如果没有更多信息，很难说。

于 2012-05-23T04:20:27.083 回答
0

1）我建议使用随机数生成器来选择您的“单个”数字，然后我将使用构建所有数字的集合，然后使用内置的随机播放方法。我推荐使用内置 shuffle 方法，因为内置方法往往是高度优化的。

2）如果 n 非常大，那么您可能希望将数字块写入文件并在任何给定时间仅对部分进行改组。一个类比是试图同时洗牌 5 副牌。这充其量是非常困难的，但是您可以取大集合的一部分并将这些部分混在一起，将这些部分返回到大集合中，然后再选择两个部分进行混洗，重复直到满足您想要的混洗要求。

于 2012-05-23T04:20:54.867 回答
0

结果频率表的生成器，这应该有助于解决内存问题

from random import randint

def generate_counts(n):
    remove_index = randint(1,n+1)
    return ((i+1,2-(remove_index==i)) for i in range(n))

输出

for number, frequency in generate_counts(10):
    print "%i: %i"%(number,frequency)

1: 2
2: 2
3: 2
4: 1
5: 2
6: 2
7: 2
8: 2
9: 2
10: 2
于 2012-05-23T04:53:15.883 回答