リストからN個のランダム要素を選択するためのアルゴリズム C＃

Question

ジェネリックリストから4つのランダム要素を選択するための簡単なアルゴリズムが必要です。たとえば、Listから4つのランダムな要素を取得し、要素が有効でないと判断された場合、リストから次の4つの要素を再度選択する必要があります。

Answer 1

Listの長さをNとします。ここで、これらの4つの数字を別のリストに配置するとします。もし次に

List<T> GetRandomElements<T>(List<T> allElements, int randomCount = 4) 
{ 
    if (allElements.Count < randomCount) 
    { 
     return allElements; 
    } 

    List<int> indexes = new List<int>(); 

    // use HashSet if performance is very critical and you need a lot of indexes 
    //HashSet<int> indexes = new HashSet<int>(); 

    List<T> elements = new List<T>(); 

    Random random = new Random(); 
    while (indexes.Count < randomCount) 
    { 
     int index = random.Next(allElements.Count); 
     if (!indexes.Contains(index)) 
     { 
      indexes.Add(index); 
      elements.Add(allElements[index]); 
     } 
    } 

    return elements; 
} 

ことができます。そして、あなたはリストをループして、選択されている上にある要素の確率が

(4 - (out.Count))/(N - currentIndex) 

Answer 2

であるあなたは非繰り返しインデックスを取得するには、いくつかのリスト内のインデックスを格納することができますをすることができますいくつかの計算を行うと、このメソッドを呼び出します。そのような

void Main(String[] args) 
{ 
    do 
    { 
     List<int> elements = GetRandomelements(yourElements); 
     //do some calculations 
    } while (some condition); // while result is not right 
} 

Answer 3

何か：

using System; 
using System.Collections.Generic; 

     public class Program 
     { 
      public static void Main() 
      { 
       var list = new List<int>(); 

       list.Add(1); 
       list.Add(2); 
       list.Add(3); 
       list.Add(4); 
       list.Add(5); 

       int n = 4; 

       var rand = new Random(); 

       var randomObjects = new List<int>(); 

       for (int i = 0; i<n; i++) 
       { 
        var index = rand.Next(list.Count); 

        randomObjects.Add(list[index]); 
       }  

      } 
     } 

Answer 4

funcion (list) 
(
loop i=0 i < 4 
    index = (int) length(list)*random(0 -> 1) 
    element[i] = list[index] 
return element 
) 

while(check == false) 
(
    elements = funcion (list) 

    Do some calculation which returns check == false /true 
) 

これは擬似コードですが、これを自分で考えてください。 は、それが役立ちます:)

Answer 5

あなたは、このように拡張メソッドを使用すると、この

public static class Extensions 
    { 
     public static Dictionary<int, T> GetRandomElements<T>(this IList<T> list, int quantity) 
     { 
      var result = new Dictionary<int, T>(); 
      if (list == null) 
       return result; 
      Random rnd = new Random(DateTime.Now.Millisecond); 
      for (int i = 0; i < quantity; i++) 
      { 
       int idx = rnd.Next(0, list.Count); 
       result.Add(idx, list[idx]); 
      } 
      return result; 
     } 
    } 

のようにそれを行うことを願って：今まで

List<string> list = new List<string>() { "a", "b", "c", "d", "e", "f", "g", "h" }; 
    Dictionary<int, string> randomElements = list.GetRandomElements(3); 
    foreach (KeyValuePair<int, string> elem in randomElements) 
    { 
     Console.WriteLine($"index in original list: {elem.Key} value: {elem.Value}"); 
    } 

Answer 6

すべての答えは1つの根本的な欠陥を持っています。 n要素のランダムな組み合わせを生成するアルゴリズムを要求しています。この組み合わせは、いくつかの論理規則に従って有効であるかどうかはわかりません。そうでない場合は、新しい組み合わせを作成する必要があります。明らかに、この新しい組み合わせは、今までに生産されたことのないものでなければなりません。すべての提案されたアルゴリズムはこれを強制しません。例えば、1000000の可能な組み合わせのうち、有効な組み合わせが1つだけの場合、その特定の固有の組み合わせが生成されるまで、大量のリソースを浪費する可能性があります。

これはどのように解決するのですか？答えは簡単ですが、すべての可能な独自のソリューションを作成してから、ランダムな順序で単純に生成してください。注意：入力ストリームに反復要素がないと仮定します。ある場合、一部の組み合わせは一意ではありません。再帰によってすべての組み合わせを生成しながらこれが私たちの生活が楽になります

class ImmutableStack<T> : IEnumerable<T> 
{ 
    public static readonly ImmutableStack<T> Empty = new ImmutableStack<T>(); 
    private readonly T head; 
    private readonly ImmutableStack<T> tail; 
    public int Count { get; } 

    private ImmutableStack() 
    { 
     Count = 0; 
    } 

    private ImmutableStack(T head, ImmutableStack<T> tail) 
    { 
     this.head = head; 
     this.tail = tail; 
     Count = tail.Count + 1; 
    } 

    public T Peek() 
    { 
     if (this == Empty) 
      throw new InvalidOperationException("Can not peek a empty stack."); 

     return head; 
    } 

    public ImmutableStack<T> Pop() 
    { 
     if (this == Empty) 
      throw new InvalidOperationException("Can not pop a empty stack."); 

     return tail; 
    } 

    public ImmutableStack<T> Push(T item) => new ImmutableStack<T>(item, this); 

    public IEnumerator<T> GetEnumerator() 
    { 
     var current = this; 

     while (current != Empty) 
     { 
      yield return current.head; 
      current = current.tail; 
     } 
    } 

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); 
} 

：

まず、自分自身の便利な不変のスタックを書き込むことができます。次に、主な方法の権利の署名を取得しましょう：

public static IEnumerable<IEnumerable<T>> GetAllPossibleCombinationsInRandomOrder<T>(
    IEnumerable<T> data, int combinationLength) 

これは正しく表示されます。それでは、この事実装してみましょう：

var allCombinations = GetAllPossibleCombinations(data, combinationLength).ToArray(); 
    var rnd = new Random(); 
    var producedIndexes = new HashSet<int>(); 

    while (producedIndexes.Count < allCombinations.Length) 
    { 
     while (true) 
     { 
      var index = rnd.Next(allCombinations.Length); 

      if (!producedIndexes.Contains(index)) 
      { 
       producedIndexes.Add(index); 
       yield return allCombinations[index]; 
       break; 
      } 
     } 
    } 

[OK]を、我々はまだそれを生産していない確認し、ランダムindexeesを生産している、ここでやっているすべては、（我々はこのためHashSet<int>を使用）、およびそのインデックスの組み合わせを返します。

シンプルなので、今はGetAllPossibleCombinations(data, combinationLength)の世話をするだけです。

簡単に、私たちは再帰を使用します。私たちの保釈アウト条件は、私たちの現在の組み合わせが指定された長さである場合です。もう一つの注意点：私は、コード全体で引数の検証を省略しています。nullをチェックするか、指定された長さが入力の長さを超えていないかどうかなどを考慮する必要があります。

ちょっと楽しいので、ここではネストされた関数のマイナーなC＃7構文を使用します。私たちが行く

public static IEnumerable<IEnumerable<T>> GetAllPossibleCombinations<T>(
    IEnumerable<T> stream, int length) 
{ 
    return getAllCombinations(stream, ImmutableStack<T>.Empty); 

    IEnumerable<IEnumerable<T>> getAllCombinations<T>(IEnumerable<T> currentData, ImmutableStack<T> combination) 
    { 
     if (combination.Count == length) 
      yield return combination; 

     foreach (var d in currentData) 
     { 
      var newCombination = combination.Push(d); 

      foreach (var c in getAllCombinations(currentData.Except(new[] { d }), newCombination)) 
      { 
       yield return c; 
      } 
     } 
    } 
} 

そしてそこに、今、私たちはこれを使用することができます：

var data = "abc"; 
var random = GetAllPossibleCombinationsInRandomOrder(data, 2); 

foreach (var r in random) 
{ 
    Console.WriteLine(string.Join("", r)); 
} 

そして案の定、出力は次のとおりです。

bc 
cb 
ab 
ac 
ba 
ca