none
генерация массива из неповторяющихся элементов (некорректно работает System.Array.Сontains ?) RRS feed

  • Вопрос

  • Здравствуйте. Существует след. задача: сгенерировать массив из неповторяющихся элементов, но с использованием Random. На одном из форумов нашел метод, суть которого предсталена мной на скриншоте, но хотелось бы что-нибудь получше.  Приведите, пожалуйста, другой способ.


    • Изменено Gargulie 14 февраля 2012 г. 19:57
    14 февраля 2012 г. 17:52

Ответы

  • Похоже там после if() точку с запятой нужно убрать.

    А вообще код - УГ :(

    • Помечено в качестве ответа Abolmasov Dmitry 15 февраля 2012 г. 8:48
    14 февраля 2012 г. 18:23
    Отвечающий
  • > сгенерировать массив из неповторяющихся элементов, но с использованием Random.

     

    var res = Random(3, 1, 20).ToArray();
    ...
    public IEnumerable Random(int count, int min, int max)
    {
        var set = new HashSet();
        var rnd = new Random();
        while (set.Count != count)
        {
            var v = rnd.Next(min, max);
            if (set.Contains(v) == false)
            {
                yield return v;
                set.Add(v);
            }
        }
    }
     

    см. другие способы здесь
     
     
    • Изменено Malobukv 14 февраля 2012 г. 20:43
    • Помечено в качестве ответа Gargulie 14 февраля 2012 г. 22:16
    14 февраля 2012 г. 20:42
  • > есть массив типа string, необходимо "перемешать" элементы массива с использованием Random.
     
       

    using System.Linq;
    using System.Collections.Generic;
    ...
    var res = Random(new [] { "1", "2", "3", "4", "5" }).ToArray();
    ...
    IEnumerable<T> Random<T>(IEnumerable<T> src)
    {
        var rnd = new Random();
        return src.OrderBy(x => rnd.Next());
    }
       
     
    см. другой способ здесь (реализация Fisher-Yates algorithm)
     
       
    • Предложено в качестве ответа Malobukv 14 февраля 2012 г. 23:26
    • Помечено в качестве ответа Abolmasov Dmitry 15 февраля 2012 г. 8:47
    14 февраля 2012 г. 23:25

Все ответы

  • Похоже там после if() точку с запятой нужно убрать.

    А вообще код - УГ :(

    • Помечено в качестве ответа Abolmasov Dmitry 15 февраля 2012 г. 8:48
    14 февраля 2012 г. 18:23
    Отвечающий
  • и в правду, проблема с ";" , спасибо, не заметил. Но только вот все равно хотелось бы другой способ.
    • Изменено Gargulie 14 февраля 2012 г. 19:58
    14 февраля 2012 г. 18:41
  • >Но только вот все равно хотелось бы другой способ

    Сформулируйте задачу. Если задача "сгенерировать массив из неповторяющихся элементов" то она имеет тривиальное решение:

    for(int i=0;i<arr.Length;i++) arr[i] = i;

    14 февраля 2012 г. 19:46
    Отвечающий
  • > сгенерировать массив из неповторяющихся элементов, но с использованием Random.

     

    var res = Random(3, 1, 20).ToArray();
    ...
    public IEnumerable Random(int count, int min, int max)
    {
        var set = new HashSet();
        var rnd = new Random();
        while (set.Count != count)
        {
            var v = rnd.Next(min, max);
            if (set.Contains(v) == false)
            {
                yield return v;
                set.Add(v);
            }
        }
    }
     

    см. другие способы здесь
     
     
    • Изменено Malobukv 14 февраля 2012 г. 20:43
    • Помечено в качестве ответа Gargulie 14 февраля 2012 г. 22:16
    14 февраля 2012 г. 20:42
  • Большое спасибо, а что делать, если расмотреть ту же задачу, но только для строкового массива?

    У нас есть массив типа string, необходимо "перемешать" элементы массива с использованием Random.


    • Изменено Gargulie 14 февраля 2012 г. 22:23
    14 февраля 2012 г. 22:23
  • > есть массив типа string, необходимо "перемешать" элементы массива с использованием Random.
     
       

    using System.Linq;
    using System.Collections.Generic;
    ...
    var res = Random(new [] { "1", "2", "3", "4", "5" }).ToArray();
    ...
    IEnumerable<T> Random<T>(IEnumerable<T> src)
    {
        var rnd = new Random();
        return src.OrderBy(x => rnd.Next());
    }
       
     
    см. другой способ здесь (реализация Fisher-Yates algorithm)
     
       
    • Предложено в качестве ответа Malobukv 14 февраля 2012 г. 23:26
    • Помечено в качестве ответа Abolmasov Dmitry 15 февраля 2012 г. 8:47
    14 февраля 2012 г. 23:25
  • Спасибо
    15 февраля 2012 г. 21:01
  • >return src.OrderBy(x => rnd.Next());


    Ммм.. это рискованный способ, такая сортировка может не сойтись... Или по крайней мере, будет работать дольше чем могла бы.

    16 февраля 2012 г. 9:56
    Отвечающий
  • @Algol36

    > .OrderBy(x=>rnd.Next()); [...] это рискованный способ, такая сортировка может не сойтись... Или по крайней мере, будет работать дольше чем могла бы.
       
     
    для коллекций из тысяч и более элементов можно использовать Guid.NewGuid() вместо Random.Next(), но в остальных случаях - оставить как есть.
    см. здесь: ".OrderBy(x=>rand.Next());, and you're done. [...] really, it's fine to order by a random key." -- Eric Lippert, a principal developer on the Microsoft Visual C# compiler team.
      
     


    • Изменено Malobukv 16 февраля 2012 г. 12:16
    16 февраля 2012 г. 12:00
  • Ну с Эриком Липретом я конечно спорить не буду.

    НО все таки я бы поостерегся использовать такой алгоритм. Дело в том, что невозможно отсортировать массив, обртившись к каждому ключу сортировки только один раз. Если бы это было так, тогда бы алгоритмы сортировки имели бы линейную сложность. А это не так.  Значит, к ключу сортировки алгоритм будет обращаться несколько раз. И вот тут наступает проблема, потому что ключ то меняется, он генерится при каждом обращении - заново, даже для одного и того же элемента. А это может привести к зацикливанию алгоритма. Я на такое уже натыкался на практике :)

    Это все касается сортировки List.Sort(). Но вот в LINQ все работает немного не так. Я проверил ваш код, и он обращается к лямбде лишь один раз для каждого элемента. Это хорошо, потому что в таком случае не возникает вышеописанная проблема. Но это же и означает, что линк где-то кеширует прочитанные ключи. А это значит что сортировка линком потребляет больше памяти, чем List.Sort().

    В общем, как ни крути, OrderBy(x=>rand.Next()) - не лучший вариант, хотя подкупает простотой. Это да :)

    17 февраля 2012 г. 0:37
    Отвечающий
  • А что касается алгоритма Fisher–Yates , то да, он лучше сортировки и не потребляет памяти.

    Но у него есть другая проблема. У него хромает функция перемешивания. Из-за "парадокса дней рождений" у него почти гарантированно случается ситуация, когда некоторые элементы останутся на своих местах.

    17 февраля 2012 г. 0:46
    Отвечающий