一般的なリストから 5 つのランダムな要素を選択する簡単なアルゴリズムが必要です。たとえば、 a から 5 つのランダムな要素を取得したいと思いList<string>ます。
142844 次
30 に答える
255
リンクの使用:
YourList.OrderBy(x => rnd.Next()).Take(5)
于 2010-02-22T17:53:32.083 に答える
139
反復し、各要素について、選択の確率 = (必要な数)/(残りの数) を作成します。
したがって、40 個のアイテムがある場合、最初のアイテムが選択される可能性は 5/40 になります。そうである場合、次は 4/39 のチャンスがあり、そうでない場合は 5/39 のチャンスがあります。最後にたどり着くまでに 5 つのアイテムがあり、多くの場合、その前にすべてのアイテムがあります。
この手法は、選択サンプリングと呼ばれ、貯水池サンプリングの特殊なケースです。入力をシャッフルするのとパフォーマンスは似ていますが、もちろん、元のデータを変更せずにサンプルを生成できます。
于 2008-09-07T03:16:16.507 に答える
48
public static List<T> GetRandomElements<T>(this IEnumerable<T> list, int elementsCount)
{
return list.OrderBy(arg => Guid.NewGuid()).Take(elementsCount).ToList();
}
于 2012-09-29T16:15:32.803 に答える
29
これは実際には思ったよりも難しい問題です。主な理由は、数学的に正しいソリューションの多くは、実際にはすべての可能性を見つけることができないためです（これについては以下で詳しく説明します）。
まず、実装が簡単で、真に乱数があれば正しいジェネレーターを次に示します。
（0）カイルの答え、それはO（n）です。
（1）nペアのリストを生成し[（0、rand）、（1、rand）、（2、rand）、...]、2番目の座標で並べ替え、最初のkを使用します（あなたにとってはk = 5）ランダムなサブセットを取得するためのインデックス。O（n log n）時間ですが、これは簡単に実装できると思います。
（2）空のリストs = []を初期化します。これは、k個のランダム要素のインデックスになります。{0、1、2、...、n-1}の数rをランダムに選択し、r = rand％nとし、これをsに追加します。次に、r = rand％（n-1）を取り、sに固執します。衝突を避けるために、sの要素よりも少ない＃要素をrに追加します。次に、r = rand％（n-2）を取り、sにk個の異なる要素ができるまで、同じことなどを行います。これには、最悪の場合の実行時間O（k ^ 2）があります。したがって、k << nの場合、これはより高速になる可能性があります。sを並べ替えて、連続する間隔を追跡する場合は、O（k log k）で実装できますが、より手間がかかります。
@カイル-あなたは正しいです、考え直して私はあなたの答えに同意します。私は最初に急いでそれを読み、あなたが固定確率k / nで各要素を順番に選択することを示していると誤って考えましたが、それは間違っていたでしょう-しかしあなたの適応アプローチは私には正しいようです。申し訳ありません。
さて、キッカーの場合：漸近的に（固定k、n成長の場合）、n ^ k / kがあります！n個の要素からのk個の要素サブセットの選択[これは（nはkを選択）の近似値です]。nが大きく、kがそれほど小さくない場合、これらの数は膨大になります。標準の32ビット乱数ジェネレーターで期待できる最適なサイクル長は2^32 = 256^4です。したがって、1000個の要素のリストがあり、ランダムに5個を選択したい場合、標準の乱数ジェネレーターがすべての可能性にぶつかる方法はありません。ただし、小さいセットで正常に機能し、常にランダムに「見える」選択で問題がない限り、これらのアルゴリズムは問題ありません。
補遺：これを書いた後、アイデア（2）を正しく実装するのは難しいことに気づいたので、この答えを明確にしたいと思いました。O（k log k）時間を取得するには、O（log m）の検索と挿入をサポートする配列のような構造が必要です。バランスの取れた二分木がこれを実行できます。このような構造を使用してsと呼ばれる配列を構築すると、次のような疑似Pythonが作成されます。
# Returns a container s with k distinct random numbers from {0, 1, ..., n-1}
def ChooseRandomSubset(n, k):
for i in range(k):
r = UniformRandom(0, n-i) # May be 0, must be < n-i
q = s.FirstIndexSuchThat( s[q] - q > r ) # This is the search.
s.InsertInOrder(q ? r + q : r + len(s)) # Inserts right before q.
return s
いくつかのサンプルケースを実行して、これが上記の英語の説明をどのように効率的に実装するかを確認することをお勧めします。
于 2008-09-07T03:48:10.407 に答える
17
選ばれた答えは正しくてかなり甘いと思います。ただし、結果をランダムな順序で表示したかったので、別の方法で実装しました。
static IEnumerable<SomeType> PickSomeInRandomOrder<SomeType>(
IEnumerable<SomeType> someTypes,
int maxCount)
{
Random random = new Random(DateTime.Now.Millisecond);
Dictionary<double, SomeType> randomSortTable = new Dictionary<double,SomeType>();
foreach(SomeType someType in someTypes)
randomSortTable[random.NextDouble()] = someType;
return randomSortTable.OrderBy(KVP => KVP.Key).Take(maxCount).Select(KVP => KVP.Value);
}
于 2009-01-16T18:57:27.273 に答える
13
私はちょうどこの問題に遭遇し、さらにいくつかのグーグル検索により、リストをランダムにシャッフルするという問題が発生しました: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
リストを (その場で) 完全にランダムにシャッフルするには、次のようにします。
n 要素 (インデックス 0..n-1) の配列 a をシャッフルするには:
for i from n − 1 downto 1 do
j ← random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]
最初の 5 つの要素だけが必要な場合は、i を n-1 から 1 まで実行する代わりに、n-5 まで実行するだけです (つまり、n-5)。
k個のアイテムが必要だとしましょう。
これは次のようになります。
for (i = n − 1; i >= n-k; i--)
{
j = random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]
}
選択された各項目は配列の末尾に向かってスワップされるため、選択された k 個の要素は配列の最後の k 個の要素になります。
これには O(k) の時間がかかります。ここで、k は必要なランダムに選択された要素の数です。
さらに、最初のリストを変更したくない場合は、すべてのスワップを一時リストに書き留め、そのリストを逆にして再度適用すると、スワップの逆セットが実行され、変更せずに最初のリストが返されます。 O(k) 実行時間。
最後に、実際のスティックラーの場合、(n == k) の場合、ランダムに選択された整数は常に 0 になるため、nk ではなく 1 で停止する必要があります。
于 2012-01-16T06:46:58.767 に答える
10
これを使用できますが、注文はクライアント側で行われます
.AsEnumerable().OrderBy(n => Guid.NewGuid()).Take(5);
于 2012-03-23T16:32:25.937 に答える
9
アルゴリズムのドラゴンから、C＃での解釈：
int k = 10; // items to select
var items = new List<int>(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 });
var selected = new List<int>();
double needed = k;
double available = items.Count;
var rand = new Random();
while (selected.Count < k) {
if( rand.NextDouble() < needed / available ) {
selected.Add(items[(int)available-1])
needed--;
}
available--;
}
このアルゴリズムは、アイテムリストの一意のインデックスを選択します。
于 2008-09-07T04:31:41.877 に答える
8
（言い換え）に関する受け入れられた回答に対する@JohnShedletskyによるコメントについて考えていました：
O(originalList.Length) ではなく、O(subset.Length) でこれを実行できるはずです。
subset基本的に、ランダムなインデックスを生成し、元のリストからそれらを抽出できるはずです。
メソッド
public static class EnumerableExtensions {
public static Random randomizer = new Random(); // you'd ideally be able to replace this with whatever makes you comfortable
public static IEnumerable<T> GetRandom<T>(this IEnumerable<T> list, int numItems) {
return (list as T[] ?? list.ToArray()).GetRandom(numItems);
// because ReSharper whined about duplicate enumeration...
/*
items.Add(list.ElementAt(randomizer.Next(list.Count()))) ) numItems--;
*/
}
// just because the parentheses were getting confusing
public static IEnumerable<T> GetRandom<T>(this T[] list, int numItems) {
var items = new HashSet<T>(); // don't want to add the same item twice; otherwise use a list
while (numItems > 0 )
// if we successfully added it, move on
if( items.Add(list[randomizer.Next(list.Length)]) ) numItems--;
return items;
}
// and because it's really fun; note -- you may get repetition
public static IEnumerable<T> PluckRandomly<T>(this IEnumerable<T> list) {
while( true )
yield return list.ElementAt(randomizer.Next(list.Count()));
}
}
さらに効率的にしたい場合は、実際のリスト要素ではなく、おそらくインデックスHashSetの aを使用するでしょう（複雑な型または高価な比較がある場合）。
単体テスト
そして、衝突などがないことを確認します。
[TestClass]
public class RandomizingTests : UnitTestBase {
[TestMethod]
public void GetRandomFromList() {
this.testGetRandomFromList((list, num) => list.GetRandom(num));
}
[TestMethod]
public void PluckRandomly() {
this.testGetRandomFromList((list, num) => list.PluckRandomly().Take(num), requireDistinct:false);
}
private void testGetRandomFromList(Func<IEnumerable<int>, int, IEnumerable<int>> methodToGetRandomItems, int numToTake = 10, int repetitions = 100000, bool requireDistinct = true) {
var items = Enumerable.Range(0, 100);
IEnumerable<int> randomItems = null;
while( repetitions-- > 0 ) {
randomItems = methodToGetRandomItems(items, numToTake);
Assert.AreEqual(numToTake, randomItems.Count(),
"Did not get expected number of items {0}; failed at {1} repetition--", numToTake, repetitions);
if(requireDistinct) Assert.AreEqual(numToTake, randomItems.Distinct().Count(),
"Collisions (non-unique values) found, failed at {0} repetition--", repetitions);
Assert.IsTrue(randomItems.All(o => items.Contains(o)),
"Some unknown values found; failed at {0} repetition--", repetitions);
}
}
}
于 2013-06-21T20:53:48.567 に答える
5
ここでは、John Shedletsky が指摘したように、アルゴリズムの複雑さが O(n) であるFisher-Yates Shuffleに基づく 1 つの実装があります。ここで、n はリスト サイズではなく、サブセットまたはサンプル サイズです。
public static IEnumerable<T> GetRandomSample<T>(this IList<T> list, int sampleSize)
{
if (list == null) throw new ArgumentNullException("list");
if (sampleSize > list.Count) throw new ArgumentException("sampleSize may not be greater than list count", "sampleSize");
var indices = new Dictionary<int, int>(); int index;
var rnd = new Random();
for (int i = 0; i < sampleSize; i++)
{
int j = rnd.Next(i, list.Count);
if (!indices.TryGetValue(j, out index)) index = j;
yield return list[index];
if (!indices.TryGetValue(i, out index)) index = i;
indices[j] = index;
}
}
于 2016-06-15T12:59:49.003 に答える
4
私が使用する簡単な解決策（おそらく大きなリストには適していません）：リストを一時リストにコピーし、ループで一時リストからアイテムをランダムに選択し、一時リストから削除しながら選択したアイテムリストに入れます（したがって、再選択されます)。
例：
List<Object> temp = OriginalList.ToList();
List<Object> selectedItems = new List<Object>();
Random rnd = new Random();
Object o;
int i = 0;
while (i < NumberOfSelectedItems)
{
o = temp[rnd.Next(temp.Count)];
selectedItems.Add(o);
temp.Remove(o);
i++;
}
于 2010-07-20T09:18:48.093 に答える
3
これは私が最初のカットで思いつくことができる最高のものです：
public List<String> getRandomItemsFromList(int returnCount, List<String> list)
{
List<String> returnList = new List<String>();
Dictionary<int, int> randoms = new Dictionary<int, int>();
while (randoms.Count != returnCount)
{
//generate new random between one and total list count
int randomInt = new Random().Next(list.Count);
// store this in dictionary to ensure uniqueness
try
{
randoms.Add(randomInt, randomInt);
}
catch (ArgumentException aex)
{
Console.Write(aex.Message);
} //we can assume this element exists in the dictonary already
//check for randoms length and then iterate through the original list
//adding items we select via random to the return list
if (randoms.Count == returnCount)
{
foreach (int key in randoms.Keys)
returnList.Add(list[randoms[key]]);
break; //break out of _while_ loop
}
}
return returnList;
}
1の範囲内のランダムのリストを使用する-リストの総数-リスト内のそれらのアイテムを単純にプルするのが最善の方法のように見えましたが、辞書を使用して一意性を確保することは、私がまだ検討していることです。
また、文字列リストを使用したことに注意してください。必要に応じて置き換えてください。
于 2008-09-07T04:27:32.200 に答える
2
Kyle の回答に基づいて、これが私の c# 実装です。
/// <summary>
/// Picks random selection of available game ID's
/// </summary>
private static List<int> GetRandomGameIDs(int count)
{
var gameIDs = (int[])HttpContext.Current.Application["NonDeletedArcadeGameIDs"];
var totalGameIDs = gameIDs.Count();
if (count > totalGameIDs) count = totalGameIDs;
var rnd = new Random();
var leftToPick = count;
var itemsLeft = totalGameIDs;
var arrPickIndex = 0;
var returnIDs = new List<int>();
while (leftToPick > 0)
{
if (rnd.Next(0, itemsLeft) < leftToPick)
{
returnIDs .Add(gameIDs[arrPickIndex]);
leftToPick--;
}
arrPickIndex++;
itemsLeft--;
}
return returnIDs ;
}
于 2013-07-11T15:59:06.377 に答える
2
この方法はカイルの方法と同等かもしれません。
リストのサイズが n で、k 個の要素が必要だとします。
Random rand = new Random();
for(int i = 0; k>0; ++i)
{
int r = rand.Next(0, n-i);
if(r<k)
{
//include element i
k--;
}
}
魅力のように機能します:)
-アレックス・ギルバート
于 2015-01-28T07:21:19.690 に答える
1
思ったよりずっと難しいです。ジェフからの素晴らしい記事「シャッフル」を参照してください。
私はC＃コードを含むその主題に関する非常に短い記事を書きました：
与えられた配列のN要素のランダムなサブセットを返します
于 2009-06-25T09:25:02.043 に答える
0
私は最近、タイラーのポイント1に似たアイデアを使用して、自分のプロジェクトでこれを行いました。
私はたくさんの質問をロードし、ランダムに5つを選択していました。並べ替えは、IComparerを使用して行われました。
aすべての質問がQuestionSorterリストに読み込まれ、リストの並べ替え機能と選択された最初のk個の要素を使用して並べ替えられました。
private class QuestionSorter : IComparable<QuestionSorter>
{
public double SortingKey
{
get;
set;
}
public Question QuestionObject
{
get;
set;
}
public QuestionSorter(Question q)
{
this.SortingKey = RandomNumberGenerator.RandomDouble;
this.QuestionObject = q;
}
public int CompareTo(QuestionSorter other)
{
if (this.SortingKey < other.SortingKey)
{
return -1;
}
else if (this.SortingKey > other.SortingKey)
{
return 1;
}
else
{
return 0;
}
}
}
使用法：
List<QuestionSorter> unsortedQuestions = new List<QuestionSorter>();
// add the questions here
unsortedQuestions.Sort(unsortedQuestions as IComparer<QuestionSorter>);
// select the first k elements
于 2008-09-07T06:05:45.460 に答える
0
これが私のアプローチです（全文はこちらhttp://krkadev.blogspot.com/2010/08/random-numbers-without-repetition.html）。
O（N）ではなくO（K）で実行する必要があります。ここで、Kは必要な要素の数であり、Nは選択するリストのサイズです。
public <T> List<T> take(List<T> source, int k) {
int n = source.size();
if (k > n) {
throw new IllegalStateException(
"Can not take " + k +
" elements from a list with " + n +
" elements");
}
List<T> result = new ArrayList<T>(k);
Map<Integer,Integer> used = new HashMap<Integer,Integer>();
int metric = 0;
for (int i = 0; i < k; i++) {
int off = random.nextInt(n - i);
while (true) {
metric++;
Integer redirect = used.put(off, n - i - 1);
if (redirect == null) {
break;
}
off = redirect;
}
result.add(source.get(off));
}
assert metric <= 2*k;
return result;
}
于 2010-08-20T11:44:26.383 に答える
0
大きなリストでLINQを使用する（各要素に触れるのにコストがかかる場合）および重複の可能性に耐えられる場合：
new int[5].Select(o => (int)(rnd.NextDouble() * maxIndex)).Select(i => YourIEnum.ElementAt(i))
私の使用では、100.000 要素のリストがあり、それらが DB からプルされたため、リスト全体の rnd と比較して、時間が約半分 (またはそれ以上) になりました。
リストが大きいと、重複の可能性が大幅に減少します。
于 2015-12-09T23:03:56.160 に答える
0
拡張メソッドを使用します。
public static IEnumerable<T> TakeRandom<T>(this IEnumerable<T> elements, int countToTake)
{
var random = new Random();
var internalList = elements.ToList();
var selected = new List<T>();
for (var i = 0; i < countToTake; ++i)
{
var next = random.Next(0, internalList.Count - selected.Count);
selected.Add(internalList[next]);
internalList[next] = internalList[internalList.Count - selected.Count];
}
return selected;
}
于 2015-08-18T08:08:52.460 に答える
0
これは、受け入れられているソリューションほどエレガントでも効率的でもありませんが、すぐに書き上げることができます。まず、配列をランダムに並べ替えてから、最初の K 個の要素を選択します。パイソンでは、
import numpy
N = 20
K = 5
idx = np.arange(N)
numpy.random.shuffle(idx)
print idx[:K]
于 2013-05-21T05:57:31.417 に答える
0
public static IEnumerable<T> GetRandom<T>(this IList<T> list, int count, Random random)
{
// Probably you should throw exception if count > list.Count
count = Math.Min(list.Count, count);
var selectedIndices = new SortedSet<int>();
// Random upper bound
int randomMax = list.Count - 1;
while (selectedIndices.Count < count)
{
int randomIndex = random.Next(0, randomMax);
// skip over already selected indeces
foreach (var selectedIndex in selectedIndices)
if (selectedIndex <= randomIndex)
++randomIndex;
else
break;
yield return list[randomIndex];
selectedIndices.Add(randomIndex);
--randomMax;
}
}
メモリ: ~count
複雑さ: O(count 2 )
于 2016-01-09T17:08:50.663 に答える
0
なぜこのようなものではありません：
Dim ar As New ArrayList
Dim numToGet As Integer = 5
'hard code just to test
ar.Add("12")
ar.Add("11")
ar.Add("10")
ar.Add("15")
ar.Add("16")
ar.Add("17")
Dim randomListOfProductIds As New ArrayList
Dim toAdd As String = ""
For i = 0 To numToGet - 1
toAdd = ar(CInt((ar.Count - 1) * Rnd()))
randomListOfProductIds.Add(toAdd)
'remove from id list
ar.Remove(toAdd)
Next
'sorry i'm lazy and have to write vb at work :( and didn't feel like converting to c#
于 2008-10-30T17:13:18.490 に答える
0
N が非常に大きい場合、N 個の数値をランダムにシャッフルして、たとえば最初の k 個の数値を選択する通常の方法は、スペースの複雑さのために法外になる可能性があります。次のアルゴリズムは、時間と空間の両方の複雑さに対して O(k) のみを必要とします。
http://arxiv.org/abs/1512.00501
def random_selection_indices(num_samples, N):
modified_entries = {}
seq = []
for n in xrange(num_samples):
i = N - n - 1
j = random.randrange(i)
# swap a[j] and a[i]
a_j = modified_entries[j] if j in modified_entries else j
a_i = modified_entries[i] if i in modified_entries else i
if a_i != j:
modified_entries[j] = a_i
elif j in modified_entries: # no need to store the modified value if it is the same as index
modified_entries.pop(j)
if a_j != i:
modified_entries[i] = a_j
elif i in modified_entries: # no need to store the modified value if it is the same as index
modified_entries.pop(i)
seq.append(a_j)
return seq
于 2016-01-28T00:02:08.350 に答える