Генерация случайных матриц типа su doku в MATLAB - PullRequest
Новая
       6

Генерация случайных матриц типа su doku в MATLAB

3 голосов
/ 27 марта 2012

Мне нужно сгенерировать несколько матриц 5x6 в MATLAB.Они должны состоять из случайно сгенерированных целых чисел в диапазоне 1-6, однако целое число не может встречаться более одного раза в определенной строке или столбце.

Вот сценарий, который я в настоящее время использую для генерации случайных матриц 5x6: 

mat=zeros(5,6);

rows=5;
columns=6;
for i=1:rows
  for j=1:columns
      mat(i,j)=round(rand*(high-low)+low);
  end
end
disp(mat)

Но я не знаю, как вставить в это правило о повторениях.

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

Ответы [ 3 ]

4 голосов
/ 27 марта 2012

Попробуйте это: 

    m = zeros(5,6);

    for row = 1:5
        flag = 1;
        while(flag)
            flag = 0;
            R = randperm(6);
            for testRow = 1:row
                flag = flag + sum(m(testRow,:) == R);
            end;
            if (~flag)
                m(row,:) = R;
            end;
        end;

    end;

    m
3 голосов
/ 28 марта 2012

Вот еще один способ сделать это:

Начните с известного допустимого решения, скажем так: 

>> A = mod(meshgrid(1:size) - meshgrid(1:size)', size) + 1

A =

     1     2     3     4     5     6
     6     1     2     3     4     5
     5     6     1     2     3     4
     4     5     6     1     2     3
     3     4     5     6     1     2
     2     3     4     5     6     1

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

Скажем, вы меняете строку 1 и строку 2. Вы не изменили содержимое строк, поэтому «нет»повторяется в каждой строке "свойство остается верным.Точно так же вы не изменили содержимое ни одного из столбцов - только ordering - так что свойство «без повторов в каждом столбце» также остается верным.

Вот то, что я пришелс: 

function arena = gen_arena_2 (size)
    arena = mod(meshgrid(1:size) - meshgrid(1:size)', size) + 1;
    %repeatedly shuffle rows and columns
    for i = 1:10
        arena = arena(:,randperm(size))'; %shuffle columns and transpose
    end
end

Пример использования: 

>> gen_arena_2(6)

ans =

     3     5     4     2     1     6
     6     2     1     5     4     3
     5     1     6     4     3     2
     4     6     5     3     2     1
     1     3     2     6     5     4
     2     4     3     1     6     5

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

3 голосов
/ 27 марта 2012

Не пытайтесь заполнить матрицу совершенно случайными целыми числами сразу. Вероятность того, что он является действительной сеткой головоломки, исчезающе мала.

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

Если у вас есть несколько вариантов выбора, выберите один из них случайным образом.

Вы можете прогрессировать примерно так (пример 4x4 для краткости - допустимые числа 1-4) 

x x x x
x x x x
x x x x
x x x x

Выберите первое число по броску костей: 3. 

3 x x x
x x x x
x x x x
x x x x

Выберите второе число из списка допустимых номеров: [1, 2, 4]. 

3 1 x x
x x x x
x x x x
x x x x

Выберите третье число из списка допустимых чисел, [1, 4]: 

3 1 4 x
x x x x
x x x x
x x x x

и т. Д.

Если ваш «список допустимых чисел» на каком-либо шаге вставки является пустым набором, то ваша матрица не может быть восстановлена, и вам, возможно, придется начать заново.

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

Редактировать: Поскольку это не домашнее задание в традиционном смысле, и поскольку это была интересная проблема ... 

function arena = generate_arena(num_rows, num_cols, num_symbols)
    % Generate an "arena" by repeatedly calling generate_arena_try
    % until it succeeds.
    arena = 0;
    number_of_tries = 0;
    while ~(arena)
        arena = generate_arena_try(num_rows, num_cols, num_symbols);
        number_of_tries = number_of_tries + 1;
    end
    sprintf('Generating this matrix took %i tries.', number_of_tries)
end

function arena = generate_arena_try(num_rows, num_cols, num_symbols)
    % Attempts to generate a num_rows by num_cols matrix of random integers
    % from the range 1:num_symbols, with no symbols repeated in each row or
    % column.
    %
    % returns 0 on failure, or the random matrix if it succeeds.

    arena = zeros(num_rows, num_cols);
    symbols = 1:num_symbols;
    for n = 1:num_rows
        for m = 1:num_cols
           current_row = arena(n,:);
           current_col = arena(:,m);
           % find elements in $symbols that are not in the current row or col
           choices = setdiff ( symbols, [current_row current_col'] );
           if isempty(choices)
               arena = 0;
               return;
           end
           % Pick one of the valid choices at random.
           arena(n,m) = choices(randi(length(choices)));
        end
    end
    return;
end

Вызов и вывод похожи на: 

>> generate_arena(5,6,6)

ans =

Generating this matrix took 5 tries.


ans =

     2     3     6     4     5     1
     6     1     5     3     4     2
     1     5     4     2     6     3
     4     6     2     1     3     5
     3     4     1     5     2     6

Не говори, что я никогда тебе ничего не давал. ;)

...