Алгоритм расстановки позиций чисел в игре «пятнашки» — выводит -1. В чём ошибка?

Question

[D0ct0r_Murder]

в startGameButton_Click выводится все -1. Я до сих пор не заметил в чём ошибка.
Как определить,придумал ли рандом одинаковое число,по-другому не знаю,как,кроме перебора. Почему он выходит из цикла. Он должен перебрать его,пока рандом не выдаст число,отличное от тех чисел,что уже были.

private void startGameButton_Click(object sender, EventArgs e)
        {
            int[] t_numbers;
            MessageBox.Show("Game started...");
            GetRandomLocate(out t_numbers);

            string str = "";

            foreach (var t in t_numbers)
                str += t.ToString() + " ";

            MessageBox.Show(str);
        }

private void GetRandomLocate(out int[] t_numbers)
        {
            Random random = new Random();
            bool flag = true;

            t_numbers = new int[Logic.size];

            for (int i = 0; i < Logic.size; i++)
                t_numbers[i] = -1;

            for(int i = 0;i<Logic.size;i++)
            {
                while(flag)
                {
                    int rnd = random.Next(0, Logic.size + 1);
                    int ind = 0;

                    foreach (var t in t_numbers)
                        if (t == rnd)
                            ind = 1;

                    if (ind == 0)
                    {
                        t_numbers[i] = rnd;
                        flag = !flag;
                    }

                    else
                        flag = true;
                }
            }
        }

Answer 1

[xmoonlight]

1. Сгенерите массив от 1 до 15.
2. Перемешайте его
3. Берите любое из массива и удаляйте (режим очереди или стека - не важно).

Comments

[D0ct0r_Murder]

Они могут повторяться.

Нашёл алгоритм:

for(int i = 0;i<t_numbers.Length - 1;i++)
            {
                int j = random.Next(i + 1);
                var temp = t_numbers[j];
                t_numbers[j] = t_numbers[i];
                t_numbers[i] = temp;
            }

Числа дублируются(

[xmoonlight]

D0ct0r_Murder, п.1 моего ответа - читайте внимательно!

Answer 2

[eRKa]

Самый нормальный способ перемешать, это в готовом массиве в цикле брать порядковый элемент и менять его местами с рандомным. Зачем Вам головняк с двойным циклом?

var rnd = new Random();
var arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 ];
for(var i; i < arr.Length; i++)
{
	var newPosition = rnd.Next(arr.Length);
	var temp = arr[newPosition];
	arr[newPosition] = arr[i];
	arr[i] = temp;
}

PS: А для того, чтобы понять что в массиве есть такое число или нет, можно применить linq
t_numbers.Any(x => x == number)
И никогда не делайте эту штуку внутри метода
Random random = new Random();
Это угрожает созданием одинаковых последовательностей. Объект Random должен быть полем класса, причем статическим.

Answer 3

[Павел]

Способ которым ты контролируешь уникальность цифр на кнопке далеко не оптимальный. Представь сколько итераций потребуется для того, что бы срандомить число 24 если у тебя уже есть числа от 0 до 23 (для поля 5x5); Шанс 1/25, а значит в среднем будет уходить 25 итераций. Это не много, но не оптимально.

Что я предлагаю: создать List, засунуть туда n чисел (от 0 до n). И дальше использовать следующий код:

t_numbers = new int[Logic.size];
List<int> numbers = new List<int>();
int randomIndex = -1;

 for (int i = 0; i < Logic.size; i++)
                numbers.Add(i);
int i = 0;
do
{
  randomIndex = random.Next(0, numbers.Count);
   t_numbers[i++] = numbers[randomIndex];
   numbers.RemoveAt(randomIndex);
} while(numbers.Count > 0);

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

Comments

[eRKa]

Есть несколько ошибок.
1) numbers.Add(i) выдаст эксепшн с нулреференс, т.к. коллекция не создана. Нужно
List<int> numbers = new List<int>()
2) Он не скомпилируется, т.к. до цикла не определена i. И в цикле нет инкремента этой переменной.
3) Попытка оптимизировать ни к чему не приведет на больших массивах, т.к. нужно понимать, что такое List внутри. А внутри это обычный массив и удаление по индексу заставит сдвигать все значения влево. И так в цикле несколько раз. На мой взгляд лучше тогда использовать HashSet или Hashtable.
4) Ну и по мелочи. int randomIndex = -1; лишняя строка, еще и опасная. Если до обращения к массиву забудут ей присвоить значение, будет выход за пределы массива, уж лучше 0 присвоить.

[Павел]

1) Первый пункт должен быть очевиден. Я писал это в спешке и перед выходом, поэтому не обратил внимания.
2) Второй пункт - соглашусь с вами. Не заметил по той же причине.
3) List - не обычный массив. Удаление из списка предполагает что указатель предыдущего перед удаляемым элементом узла указывает на следующий после удаляемого узел. Соответственно перестановок нет.
4) int randomIndex = -1; лишняя строка, еще и опасная. С одной стороны согласен с Вами, однако -1 не должен нигде встречаться. Если я встречу это число - пойму где ошибка. Мне так удобнее и понятнее. Хотя это уже вкусовщина.

Спасибо за замечания, исправил пример.

[eRKa]

Павел, Вы не правы. List это не связанный список, а именно выделенная в памяти цельная область, с автоматическим ресайзом, т.е. когда не хватает места, создается новый массив бОльшего размера, куда копируется источник, а старый уходит в мусорник. Когда происходит удаление, происходит копирование правой части со смещением на единицу влево. Чтобы это увидеть, достаточно посмотреть в исходники

public void RemoveAt(int index)
{
	if ((uint) index >= (uint) this._size)
		ThrowHelper.ThrowArgumentOutOfRangeException();
	this._size = this._size - 1;
	if (index < this._size)
		Array.Copy((Array) this._items, index + 1, (Array) this._items, index, this._size - index);
	this._items[this._size] = default (T);
	this._version = this._version + 1;
}

Обратите внимание на второй if. Если индекс удаляемого элемента меньше размера массива, то происходит копирование правой части массива с положения index + 1, в положение начиная с index.

PS: очень рекомендую к просмотру по поводу коллекций https://www.youtube.com/watch?v=wVZhlsYQkf8&t=2995s

[Павел]

eRKa, спасибо, посмотрю. Я знал о правильной реализации, но о том какая конкретно тут - не знал.