none
How to select unique values from a IList randomly?

    Question

  •  

     Hi everybody,

     

     How can I select unique values from a IList randomly? I use IList because I want to support Arrays, Lists and Colelctions. Any idea? 

    Tuesday, April 24, 2007 12:16 PM

Answers

  • IList can be indexed using an integer.

    Therefore, you just need to generate an integer in the range 0 .. list.Count-1

    You can use the Random class for this purpose:

    Random random = new Random();
    int randomIndex = random.Next(myList.Count);
    <whatever> = myList[randomIndex];  // Use random item in list.
    Tuesday, April 24, 2007 1:46 PM
  •  

     Should better look at my code:

     

    public static IList ASelectDistinctRandomly(IList pool, int count, int max_tries)

    {

    int pool_size = pool.Count;

    int cache_size = count;

    Random rand = new Random();

    Dictionary<object, object> d = new Dictionary<object, object>(cache_size);

    int tries = 0;

    while (d.Count < cache_size && tries < max_tries)

    {

    object key = pool[rand.Next(pool_size)];

    if (!d.ContainsKey(key))

    {

    d.Add(key, key);

    tries = 0;

    }

    else

    ++tries;

    }

     

    /* Could not continue further, help needed

    *

    *

    *

    */

    }

    Tuesday, April 24, 2007 2:50 PM

All replies

  • IList can be indexed using an integer.

    Therefore, you just need to generate an integer in the range 0 .. list.Count-1

    You can use the Random class for this purpose:

    Random random = new Random();
    int randomIndex = random.Next(myList.Count);
    <whatever> = myList[randomIndex];  // Use random item in list.
    Tuesday, April 24, 2007 1:46 PM
  •  

     Should better look at my code:

     

    public static IList ASelectDistinctRandomly(IList pool, int count, int max_tries)

    {

    int pool_size = pool.Count;

    int cache_size = count;

    Random rand = new Random();

    Dictionary<object, object> d = new Dictionary<object, object>(cache_size);

    int tries = 0;

    while (d.Count < cache_size && tries < max_tries)

    {

    object key = pool[rand.Next(pool_size)];

    if (!d.ContainsKey(key))

    {

    d.Add(key, key);

    tries = 0;

    }

    else

    ++tries;

    }

     

    /* Could not continue further, help needed

    *

    *

    *

    */

    }

    Tuesday, April 24, 2007 2:50 PM
  • Therefore, you just need to generate an integer in the range 0 .. list.Count-1

     

    That just give us one random item from the IList.  There no guarantee that the next one won't be the same as the last, which means it fails the "unique" part of the assignment.

     

    Tuesday, April 24, 2007 8:03 PM
  • I use IList because I want to support Arrays, Lists and Colelctions.

    Are you sure you want an IList ? --- remember, all ILists are ICollections, but not all ICollections are ILists.

     

    Actually, doing this with anything that doesn't support an indexer is nearly impossible (or ridiculously slow), so We'll stick with an ILIst.

     

    Now, the next problem is that you don't mention if we are allowed to alter the original List.  No Problem, I'll give it to you both ways:

     

    First with modifying:

     

    Code Snippet

    static void ShuffleList(IList list)
     {
       Random rnd = new Random();

      for(int i = list.Count-1; i > 1; --i)
       {

         int n = rnd.Next(i-1); 
           object t = list[i];
           list[i] = list[n];
           list[n] = t;

      }

    }

     

    So, let us say that list has 10 items...list[0] to list[9].   We first pick one of the items in [0] through Music, and swap it with the item in list[9].  Then we pick one from [0] to [7] and swap it with itemMusic, continuing until we swap [0] or [1] with item[2].   At which point, the entire list is in random order.

     

    But what it you can't alter the list.  Well, we could make a copy first, but where's the fun in that?  And let's use a iterator to make it exciting.

     

    Code Snippet

    static IEnumerable InRandomOrder(IList list)
    {

     int[] indexes = new int[list.Count];
      for(int i = 0; i < list.Count; ++i)
             indexes[i] = i;


     

     ShuffleList(indexes);
      foreach(int inx in indexes)
      {

          yield return list[inx];

    }
    }

     

    // :

    // :

    string[] words = new string[] {"quick", "brown", "fox", "lazy", "dog"};
     foreach(string word in InRandomOrder(words))

         Console.WriteLine(word);

     

     

     

     

    Tuesday, April 24, 2007 8:31 PM
  •  

     

     Please read my post and the code I sent before answering and giving new ideas. I want IList because Arrays, Collections and Lists implement it + it has built in support of this[ int index ] which if you look at my code, suits the best where I use object key = pool[rand.Next(pool_size)];

    Second, I don't have any problems with shuffling or randomizing a list. I want to do exactly this:

     

    I have an array, let's say :

    int[ ] pool = new int[ ] { 1, 2, 2, 3, 4, 4, 5, 6, 6 }

     

    and I want to get 2 int arrays each with 3 unique/distinct items such as ret1 =  { 6, 2, 5} and ret2 = { 4, 1, 6 }  BUT NEVER

    invalidRet1 = {  2, 2, 4 } or invalidRet2 = { 6 , 6, 3 }. If the count parameter i use in my code is more than the unique items in my pool which are {1, 2, 3, 4, 5, 6} in a case of count = 10 then my function should return a result with a maximum of 6 items and they are of course {1, 2, 3, 4, 5, 6}. I use max_tries to prevent infinite loop of randomly selecting unique item which can occur if the pool size is very small or there are too many duplicate items in the pool. (pool = {1, 2, 2, 2, 2, 2, 3} and count = 3 where in my code rand.Next(pool_size) may return the index of item 2 {1, 2, 3, 4 or 5} for ever. Dictionary<object, object> I use in my code stores these randomly selected unique items. I hope it is more clear now.

    Wednesday, April 25, 2007 7:24 AM
  •  

     it gives us unique values and does not fail the "unique" part of the assignment if you look at the dictionary object I use in my while loop Smile

    Wednesday, April 25, 2007 7:31 AM
  • Sorry I misunderstood your original request!

    Ok, so you want to randomly select N items from an IList.

    One way to do this is to create an adjunct array of indices that contains all the indices for the collection. Then you randomly shuffle that array and select the first N indices from it.

    However, you could download the excellent (and free) PowerCollections class library (including source) from Wintellect.com. It was written by one of the people who worked on the design of .NET:

    http://www.wintellect.com/PowerCollections.aspx

    One of the useful algorithms they have is Algorithms.RandomSubset<T>().

    A copy of the help page for it follows:

    Algorithms.RandomSubset<T> Method (IEnumerable<T>, Int32)

    Picks a random subset of count items from collection, and places those items into a random order. No item is selected more than once.

    public static T[] RandomSubset<T>(
       IEnumerable<T> collection,
       int count
    );

    Parameters

    collection
    The collection of items to select from. This collection is not changed.
    count
    The number of items in the subset to choose.

    Return Value

    An array of count items, selected at random from collection.

    Remarks

    If the collection implements IList<T>, then this method takes time O(count). Otherwise, this method takes time O(N), where N is the number of items in the collection.

    Exceptions

    Exception Type Condition
    ArgumentOutOfRangeException count is negative or greater than collection.Count.

    See Also

    Algorithms Class | Wintellect.PowerCollections Namespace | Algorithms.RandomSubset<T> Overload List

    Wednesday, April 25, 2007 8:52 AM
  •  

     Good library but still fails to support Array AND List<T> AND Collection<T>

     

     Try below inputs and have the failure Smile

     

    ************ FAILS ***************************************

    List<int> lst = new List<int>(new int[] { 1, 2, 2, 2, 2, 3, 4 });

    List<int> result1 = (List<int>)RandomSubset(lst, 3);

     

    ************* WORKS ***********************************************

    int[] arr = new int[] { 1, 2, 2, 2, 2, 3, 4 };

    int[] result2 = (int[])RandomSubset(lst, 3);

    Wednesday, April 25, 2007 9:13 AM
  • RandomSubset() returns an array. All you need to do is to convert it into what you want.
    In the case of a List, this is as trivial as:

    List<int> lst = new List<int>(new int[] { 1, 2, 2, 2, 2, 3, 4 });
    List<int> result1 = new List<int>(Algorithms.RandomSubset(lst, 3));

    Wednesday, April 25, 2007 9:40 AM
  •  

    Why can't I cast the return value to the type that I sent as a parameter to the function for List<T> type.

     

    I should be able to do this:

     

    List<int> lst = new List(new int[ ] { 1,2,2,3,4,5,6});

    List<int> result = (List<int>)Algorithms.RandomSubset(lst,3); but if fails

    Wednesday, April 25, 2007 10:31 AM
  • You can't because RandomSubset() returns an array, not a list.

    You can't cast from an array of ints to a list<int>.
    Wednesday, April 25, 2007 10:37 AM
  •  

     I see it too, that's why I ask you Smile I want to support IList interface and return a value with the same type (if input is of type array then output should be array, if input is of type List<T> then output should be List<T>...etc) That function you sent me supports not the IList implementers (Array, Collection<T> and List<T>) but only Arrays. I think you are still misunderstanding my question Matthew.

    Wednesday, April 25, 2007 10:44 AM
  • Well it supports those all as parameters, it's just that you'd need to adjust the return type.

    If you wanted to transparently adjust the return type, you only need to write overloaded generic wrapper methods, like so:



    public T[] RandomSubset<T>(T[] list, int count)
    {
        return Algorithms.RandomSubset(list, count);
    }

    public List<T> RandomSubset<T>(List<T> list, int count)
    {
        return new List<T>(Algorithms.RandomSubset(list, count));
    }

    public Collection<T> RandomSubset<T>(Collection<T> list, int count)
    {
        return new Collection<T>(Algorithms.RandomSubset(list, count));
    }

     


    Then code like this works:



    List<int> lst = new List<int>(new int[] { 1, 2, 2, 2, 2, 3, 4 });
    List<int> result1 = RandomSubset(lst, 3);

    int[] arr = new int[] { 1, 2, 2, 2, 2, 3, 4 };
    int[] result2 = RandomSubset(arr, 3);

    Collection<int> coll = new Collection<int>(new int[] { 1, 2, 2, 2, 2, 3, 4 });
    Collection<int> result3 = RandomSubset(coll, 3);

     


    But you'd need to add an override for each type that you wanted to support.


    Wednesday, April 25, 2007 11:26 AM
  •  

     

     I use IList not to write overrides for each type but you offer me use overrides, still no answer to my problem. I want a type independent support for IList implementers in 1 function only.

    Wednesday, April 25, 2007 11:32 AM
  • You're one of those clients who keeps changing the spec after the programmers have delivered code, eh?

    Just as a matter of interest, why must you have only a single method that does it? Why not just have overrides like that? It's not like you ever need to write more than a handful.

    Wednesday, April 25, 2007 11:37 AM
  • Hey Bluehunter,

    Try this code :

                IList lst = new List<Int32>(new Int32[] { 1,2,3,4,5,6,7,8,9,10 });
                // Here lst can be any ICollection
                ArrayList lst2 = new ArrayList(lst);
                Random rnd = new Random((Int32)DateTime.Now.Ticks);
                while (lst2.Count > 0)
                {
                    Int32 RandomIndex = rnd.Next(lst2.Count);
                    Object RandomObject = lst2[RandomIndex];
                    DoSomething(RandomObject);
                    lst2.RemoveAt(RandomIndex);
                }
                MessageBox.Show(lst.Count.ToString());


    This creates another List in memory, but does exactly what you want to do. Better than no way.
    Wednesday, April 25, 2007 11:54 AM
  •  

     If you look at the source code of mine which I've posted you can see that what I want is still the same. Idea behind using an IList is to support Array, Collection<T> and List<T> like IList implementers and because IList has Item, CopyTo and Count members which are easy to use. You are a patient and user-friendly solution provider but I still don't have what i need Smile

     

    Please just fill the steps after  /* Could not continue further, help needed in the source code I've sent if you or anybody can. Then test it with both of the below cases:

     

    //************ CASE 1 *********************

    List<int> lst = new List<int>(new int[] { 1, 2, 2, 2, 2, 3, 4 });

    List<int> result1 = (List<int>)SelectDistinctRandomly(lst, 5, 10);

     

    //************ CASE 2 *********************

    int[] arr = new int[] { 1, 2, 2, 2, 2, 3, 4 };

    int[] result2 = (int[])SelectDistinctRandomly(lst, 5, 10);

     

    If it works, I will stand by your side for ever Smile

    Wednesday, April 25, 2007 12:07 PM
  • it gives us unique values and does not fail the "unique" part of the assignment if you look at the dictionary object I use in my while loop

    My comment was actually in reposnse to Michael Wilson's, directly above yours..

     

    Wednesday, April 25, 2007 7:30 PM
  •  Bluehunter wrote:

    If you look at the source code of mine which I've posted you can see that what I want is still the same. Idea behind using an IList is to support Array, Collection<T> and List<T> like IList implementers and because IList has Item, CopyTo and Count members which are easy to use. You are a patient and user-friendly solution provider but I still don't have what i need

    Please just fill the steps after /* Could not continue further, help needed in the source code I've sent if you or anybody can. Then test it with both of the below cases:

    //************ CASE 1 *********************

    List<int> lst = new List<int>(new int[] { 1, 2, 2, 2, 2, 3, 4 });

    List<int> result1 = (List<int>)SelectDistinctRandomly(lst, 5, 10);

    //************ CASE 2 *********************

    int[] arr = new int[] { 1, 2, 2, 2, 2, 3, 4 };

    int[] result2 = (int[])SelectDistinctRandomly(lst, 5, 10);

    If it works, I will stand by your side for ever



    The solution I posted (last post in this thread) works... Check it out.
    Thursday, April 26, 2007 7:01 AM