Проблема
Я пытаюсь численно определить, сколькими способами можно расположить несколько книг на полке. В частности, есть 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» вместо двумерного массива целых чисел, как указано выше? Мой код также нелегко масштабировать для большего количества категорий, поскольку они жестко запрограммированы.
Советы или альтернативные примеры были бы замечательными! Спасибо.