Поиск количества возможных вариантов расположения книг на полке с использованием метода Монте-Карло

Проблема

Я пытаюсь численно определить, сколькими способами можно расположить несколько книг на полке. В частности, есть x3 категории «физика«,»научно-фантастический«, а также «путешествовать«. Каждый содержит N_phys, N_scifi, а также N_travel номера книг соответственно. Внутри своей категории книги можно размещать в любом порядке, но они должны оставаться в пределах своей категории (т.е. все книги по физике вместе). Затем категории можно расположить в любом порядке (например, я мог бы сначала получить все научно-фантастические книги, затем путешествия, а затем, например, физику).


Моя попытка

Я решил пометить каждую книгу и ее категорию целыми числами: «физика» = 1, «научная фантастика» = 2 и «путешествия» = 3. В таком случае полка представляет собой двумерный массив. Так, например, вся полка может выглядеть следующим образом:

[3   2   1   4   1   2   2   1   3;   % Book ID
 1   1   1   1   3   3   2   2   2]  % Categrory label

где первые 4 книги — это физика (потому что вторая строка — 1), затем 2 книги о путешествиях и, наконец, 3 научно-фантастические книги, например:

введите описание изображения здесь

Эта проблема может быть решена легко и точно перестановкой, и результат N_phys ! x N_scifi ! x N_travel ! x 3 !. Для N_phys = 4, N_scifi = 3, а также N_travel = 2, в результате получается 1728 возможных аранжировок.

Я написал численную попытку «грубой силы», показанную ниже в Matlab, которая, кажется, дает правильный результат:

N_phys = 4;   % Number of physics books
N_scifi = 3;  % Number of sci-fi books
N_travel = 2; % Number of travel books

books_physics = [1:N_phys;...
                 ones(1,N_phys)]; % Collection of physics books

books_scifi = [1:N_scifi;...
               2*ones(1,N_scifi)]; % Collection of sci-fi books

books_travel = [1:N_travel;...
                3*ones(1,N_travel)];  % Collection of travel books

num_samples = 10000; % Number of random shelves to generate
unique_shelves = zeros(num_samples*2,N_phys+N_scifi+N_travel); % Preallocate 

unique_shelves(1:2,:) = [books_physics books_scifi books_travel];
num_unique_shelves = 1;

% Generate "num_samples" permutations of shelves randomly
for sample_num = 1:num_samples
    
books_physics_shuffled = books_physics( :, randperm(N_phys) ); % Shuffle physics books
books_scifi_shuffled = books_scifi( :, randperm(N_scifi) );    % Shuffle sci-fi books
books_travel_shuffled = books_travel( :, randperm(N_travel) ); % Shuffle travel books

category_order = randperm(3,3); % Choose order of categories, e.g. sci-fi/phsycis/travel  = [2 1 3]

shelf = [];

% Arrange the categories in a random order
for k = 1:3
    if category_order(k) == 1
        shelf = [shelf books_physics_shuffled];
    elseif category_order(k) == 2
        shelf = [shelf books_scifi_shuffled];
    elseif category_order(k) == 3
        shelf = [shelf books_travel_shuffled];
    end
end

% Iterate over discovered shelves, and see if we have found a new unique one
shelf_exists = 0;
for k = 1:num_unique_shelves
    if shelf == unique_shelves( (2*k-1):(2*k),:)
        shelf_exists = 1; % Shelf was previously discovered
        break
    end
end

if ~shelf_exists % New shelf was found
    unique_shelves( (2*num_unique_shelves+1):(2*num_unique_shelves+2),:) = shelf; % Add shelf to existing ones
    num_unique_shelves = num_unique_shelves + 1;
end

end

disp(['Number of unique shelves found = ',num2str(num_unique_shelves)])
disp(['Expected = ', num2str(factorial(N_phys)*factorial(N_scifi)*factorial(N_travel)*factorial(3) )])

Как видно, я в основном произвольно генерирую полку, а затем проверяю, была ли она найдена ранее. Если есть, добавляю в список.

Я ищу отзывы о том, как это реализовано, и как его можно улучшить, чтобы сделать его более кратким и эффективным. Есть ли лучшая структура данных для хранения таких «unique_shelves» вместо двумерного массива целых чисел, как указано выше? Мой код также нелегко масштабировать для большего количества категорий, поскольку они жестко запрограммированы.

Советы или альтернативные примеры были бы замечательными! Спасибо.

0

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *