Сгенерировать случайное число с моими значениями массива без повторения

Я новичок в C # и создаю приложение с массивами. У меня есть массив с числами, показанными ниже:

int[] array2 = new int[] { 1, 3, 5, 7, 9 };

Что мне нужно сделать, так это изменить порядок этих чисел в массиве без повторений, потому что, когда я использую случайную функцию, это показывает мне повторяющиеся числа.

Я видел этот метод, но не знаю, как его применять с числами: http://www.dotnetperls.com/shuffle


person user1974277    schedule 13.01.2013    source источник
comment
что вы пытаетесь достичь здесь, в вашем массиве примеров нет повторений?   -  person Nasmi Sabeer    schedule 13.01.2013
comment
Разве var array2 = new int[] { 1, 3, 5, 7, 9 }.OrderBy(_ => rnd.Next()) недостаточно?   -  person I4V    schedule 13.01.2013
comment
Требуется ли гарантия, что все возможные заказы одинаково вероятны? И нужна ли вам гарантия того, что невозможно вывести будущие перемешивания на основе прошлых перемешиваний? (Последнее требование необходимо для азартных игр; если вы можете вывести будущие колоды из текущих, тогда онлайн-покер станет намного проще.) Если ответ на любой вопрос - да, то ни один из представленных здесь ответов не является правильным. Если вас не волнует небольшая предвзятость или способность злоумышленников предсказать ваше внутреннее состояние, тогда ответы, размещенные здесь, являются разумными.   -  person Eric Lippert    schedule 13.01.2013


Ответы (4)


Вы можете использовать следующую цепочку LINQ:

int[] array2 = new int[] { 1, 3, 5, 7, 9 };
var random = new Random();
var total = (int)array2.
    OrderBy(digit => random.Next()).
    Select((digit, index) => digit*Math.Pow(10, index)).
    Sum();

Сначала он случайным образом упорядочивает элементы, затем выбирает каждый элемент, умноженный на 10 в степени его индекса, затем суммирует их вместе и преобразует результат в целое число. Также обратите внимание, что я не предоставил полезного начального числа для вашего Random экземпляра. Возможно, вы захотите сделать это для получения псевдослучайных результатов.

Вы также можете использовать метод возведения в степень, описанный здесь , чтобы избежать преобразования в целое число.

РЕДАКТИРОВАТЬ: Как указал Румборл, вам может просто понадобиться перетасованный массив. В этом случае:

var shuffledArray = array2.OrderBy(n => random.Next()).
   ToArray();

Должен работать на вас.

person Mir    schedule 13.01.2013
comment
Я думаю, что OP хочет, чтобы в конце был массив, и в этом случае подойдет только var random = new Random(); array2 = array2.OrderBy(n => random.Next()).ToArray();. - person Rhumborl; 13.01.2013
comment
@Rhumborl Я основывал свой ответ на заголовке вопроса, но, судя по его содержанию, то, что вы говорите, может быть правдой. Отредактирую свой пост. - person Mir; 13.01.2013
comment
Тем не менее, отличный пост, сохраняйте детали в - person Rhumborl; 13.01.2013
comment
Обратите внимание, что этот алгоритм, хотя и правильный, как показано здесь, имеет две проблемы. Во-первых, если список очень длинный, то это операция O (n lg n), а не операция O (n), как тасование Кнута. Во-вторых, это зависит от того факта, что реализация orderby оценивает последовательность элементов упорядочивания ровно один раз. Реализация, которая повторно оценивает предложение о порядке, очевидно, приведет к двум совершенно различным случайным результатам, что может вызвать проблемы с алгоритмом сортировки. Я хочу сказать, что будьте предельно осторожны при использовании случайности для перемешивания. - person Eric Lippert; 13.01.2013
comment
Однако большое преимущество этого метода состоит в том, что он не уничтожает исходный список, как это делает перетасовка Кнута. - person Eric Lippert; 13.01.2013
comment
@EricLippert Спасибо за ваш комментарий. Я не знал о проблеме, вызванной реализацией OrderBy. - person Mir; 13.01.2013
comment
Просто чтобы уточнить: ваше решение правильное, и реализация OrderBy, предоставляемая фреймворком, хороша. Я хочу сказать, что люди, которые пытаются использовать случайность, чтобы превратить сортировку в перемешивание, часто ошибаются, потому что в конечном итоге они попадают в ситуацию, когда случайная функция дает непоследовательные инструкции алгоритму сортировки. Ваш код правильный, но этот код myList.Sort((x, y) => random.Next(-1, 2)); в корне неверен. Вы понимаете почему? - person Eric Lippert; 13.01.2013
comment
@EricLippert Я действительно вижу, что создание нового экземпляра Random с тем же (неуказанным) начальным значением даст одинаковые результаты для каждой оценки, делая сортировку неслучайной. Однако что-то заставило меня прямо сейчас задуматься, не происходит ли это и с OrderBy, если новый экземпляр создается внутри лямбда, а не передается через закрытие? Если я изменю свой метод в соответствии с вашим примером, он вернет исходный массив без перетасовки (при этом все еще используется OrderBy). - person Mir; 13.01.2013
comment
@Eve: В самом деле, если вы скажете OrderBy(digit => (new Random()).Next()), то вы получите те же самые случайные числа, отсортированные по текущему времени, если для сортировки потребуется меньшая степень детализации по тикам, и сортировка станет бесполезной. Проблема с myList.Sort((x, y) => random.Next(-1, 2)); заключается в том, что сравнение может сказать вам, что элемент A больше, чем элемент B, элемент B больше, чем элемент C, и элемент C больше, чем элемент A, и алгоритм сортировки может дать сбой или цикл навсегда, если вы дайте ему такое некорректное сравнение. - person Eric Lippert; 13.01.2013
comment
@EricLippert Я думаю, теперь я лучше понимаю. Перед вашим последним сообщением я понял совершенно противоположное - я проигнорировал тот факт, что Sort не вернется, пока элементы коллекции не будут соответствовать заданному предикату. Спасибо за полезное объяснение. - person Mir; 13.01.2013

если вы работаете на C #, вам лучше использовать структуры C #.

Вы можете использовать эту универсальную функцию

using System;
using System.Collections.Generic;

public static class ListExtensions
{
    public static void Shuffle<T>(this IList<T> list)
    {
        var randomNumber = new Random(DateTime.Now.Millisecond);
        var n = list.Count;
        while (n > 1)
        {
            n--;
            var k = randomNumber.Next(n + 1);
            var value = list[k];
            list[k] = list[n];
            list[n] = value;
        }
    }
}

и тогда ваш код должен выглядеть так:

List<int> list2 = new List<int>(){1, 3, 5, 7, 9};
Shuffle(list2);
person Roee Gavirel    schedule 13.01.2013
comment
Хорошая реализация Knuth shuffle. Я отмечаю, что массивы int уже конвертируются в IList<int>, поэтому нет необходимости использовать List<int>, если вы этого не хотите. - person Eric Lippert; 13.01.2013
comment
Разве это не должно быть list2.Shuffle()? Поскольку вы создаете метод расширения. - person comecme; 13.01.2013

Я не совсем понимаю, что вы имеете в виду, говоря об изменении порядка без повторения. Если вы просто хотите сгенерировать случайное число, которое никогда не повторяется, вы можете сделать что-то вроде этого

private Random rand = new Random();
private List<int> used = new List<int>;
protected int randomNonrepeating() {
   int i = rand.next();
   while(used.contains(i))
       i = rand.next();
   used.add(i);
   return i;
}

Я предполагаю, что это не совсем то, что вы ищете. Если вы просто хотите изменить алгоритм по предоставленной ссылке для работы с массивом целых чисел, а не со строками. Вам просто нужно изменить типы. Что-то вроде этого

using System;

using System.Collections.Generic; using System.Linq;

статический класс RandomStringArrayTool {static Random _random = new Random ();

public static string[] RandomizeStrings(int[] arr)
{
List<KeyValuePair<int, int>> list = new List<KeyValuePair<int, int>>();
// Add all strings from array
// Add new random int each time
foreach (var s in arr)
{
    list.Add(new KeyValuePair<int, int>(_random.Next(), s));
}
// Sort the list by the random number
var sorted = from item in list
         orderby item.Key
         select item;
// Allocate new string array
int[] result = new string[arr.Length];
// Copy values to array
int index = 0;
foreach (KeyValuePair<int, int> pair in sorted)
{
    result[index] = pair.Value;
    index++;
}
// Return copied array
return result;
}

}

Надеюсь это поможет.

person Chris Wininger    schedule 13.01.2013
comment
Ваш первый алгоритм неэффективен, если список большой. Поучительно выяснить, как долго ваш алгоритм будет работать, если в списке есть тысяча элементов. - person Eric Lippert; 13.01.2013
comment
Ваш второй алгоритм хорош, но вы написали его примерно в пятнадцать раз длиннее, чем нужно. return (from item in list orderby _random.Next() select item).ToArray(); подойдет. - person Eric Lippert; 13.01.2013

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

Вот как вы перемешиваете свой массив.

  1. Выясните, как вы можете генерировать случайные числа от 0 до длины вашего массива.
  2. Напишите цикл, который идет от length_of_the_array-1 до 0. (Используйте этот индекс как idx1)

Внутри цикла сделайте следующее:

а. Сгенерируйте случайное число от 0 до idx1 (включительно), используя метод из шага 1. (Пусть случайное число будет idx2.)
b. Поменяйте местами элементы в вашем массиве на idx1 и idx2.

Простую замену можно сделать примерно так:

int tmp = массив [idx1];
массив [idx1] = массив [idx2];
массив [idx2] = tmp;

Цикл заканчивается, и у вас остается перемешанный массив.

person Sanchit    schedule 13.01.2013
comment
Алгоритм перемешивания, который вы описываете, вносит предвзятость; это наиболее распространенный способ описания неправильного тасования Кнута Фишера Йетса. У Джеффа есть хороший анализ, объясняющий, почему этот алгоритм неправильный: codinghorror.com/blog /2007/12/shuffling.html - person Eric Lippert; 13.01.2013
comment
Ответ Рои Гаверила дает правильную реализацию алгоритма перемешивания. - person Eric Lippert; 13.01.2013
comment
Я хотел использовать одно случайное число, а не два. Тогда он идентичен тому, что был у Roee. Я собираюсь игнорировать все сгенерированные случайные числа, часть которых можно легко вычислить из статьи Джеффа, но это все генераторы псевдослучайных чисел, которые используют программы. Отредактирую и свой ответ для правильности. - person Sanchit; 13.01.2013