2

[1,n] の範囲で 2n-1 のランダムな整数を生成したいのですが、各要素は 1 回しか現れないランダムな値を除いて 2 回現れます。
例えば：

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

この例では、2 は 1 回だけ表示されます。

私のアルゴリズムは、次のように辞書を使用することです。

-------------
| | 数 |回|
| | 1 | 2 |
| | 2 | 1 |
| | 3 | 2 |

ここで、キーは 1 ～ n で、値はキーの出現回数を表します。ディクショナリに 2 の値を入力し、1 つのランダム キーの値を 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) に対してこれを実行しようとしています。整数をシャッフルする方法がわかりません。ただし、ランダムに 1 つ削除できます。リストを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 ファイルに 2 回書き込まれ、1 要素が 1 回書き込まれ、その要素はランダムに選択されました。

n = 5 の場合、txt ファイルは次のようになります。

0
2
3
4
0
1
2
3
4

上記の場合、1 は 1 回だけ表示され、1 つおきの数字は 2 回表示されます。

于 2012-05-23T04:08:48.853 に答える
0

2。nが非常に大きい場合、どのようにすればメモリに保存できませんか？

これらの番号で何をしたいか、および順序が重要かどうかによって異なります。テーブルの表示方法から判断すると、順序は気にしないと思います。したがってn、テーブル全体をエンコードするために必要な実際の情報量は、nそれ自体とインデックスが1つしかない場合でも非常に少なくなります。エントリ。

記憶が問題になると思われる場合は、アプローチを完全に変更する方がよいかもしれませんが、それ以上の情報がなければ、言うのは難しいです。

于 2012-05-23T04:20:27.083 に答える
0

1）乱数ジェネレーターを使用して「単一の」番号を選択することをお勧めします。次に、すべての番号のコレクションを作成してから、組み込みのシャッフル方法を使用します。組み込みメソッドは高度に最適化される傾向があるため、組み込みシャッフルメソッドを使用することをお勧めします。

2）nが非常に大きい場合は、数値のチャンクをファイルに書き込み、いつでも一部のみをシャッフルすることができます。これの例えは、5枚のカードを同時にシャッフルしようとすることです。せいぜい非常に難しいでしょうが、大規模なコレクションの一部を取り、それらの部分を一緒にシャッフルし、その部分を大規模なコレクションに戻し、さらに2つの部分を選択してシャッフルし、目的のシャッフル要件を満たすまで繰り返します。

于 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 に答える
0

@Akavallと同様に、私があなたを正しく理解しているかどうかはわかりません. 1からnの範囲で2n-1の数値を生成したい（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 に答える