4
\$\begingroup\$

The Problem

I am trying to determine numerically how many possible ways a number of books can be arranged on a shelf. Specifically, there are x3 categories "physics", "sci-fi", and "travel". Each contains N_phys, N_scifi, and N_travel numbers of books respectively. Within their category, the books can be placed in any order, but they must stay within their respective category (i.e all the physics books together). The categories can then be arranged in any order (i.e I could have all the sci-fi books first, followed by travel, followed by physics, for example).


My Attempt

I have decided to label each book and its category by integers, with "physics" = 1, "sci-fi" = 2, and "travel" = 3. The shelf is then a 2D array. So for example, a whole shelf could look like the following:

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

where the the first 4 books are physics (because the second row is 1), followed by 2 travel books, and finally 3 sci-fi books, like this:

enter image description here

This problem can be solved easily and exactly as a permutation, and the result is N_phys ! x N_scifi ! x N_travel ! x 3 !. For N_phys = 4, N_scifi = 3, and N_travel = 2, the result is 1728 possible arrangements.

I have written a "brute-force" numerical attempt, shown below in Matlab, which seems to give the correct result:

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) )])

As can be seen, I am basically randomly generating a shelf, and then checking if it has been previously found. If it has, I add it to the list.

I am looking for feedback on the way this is implemented, and how it can be improved to make it more concise and efficient. Is there a better data structure for storing such "unique_shelves", instead of the 2D array of integers as above? My code also doesn't scale easily for more categories, since they are hardcoded.

Tips or alternative examples would be great! Thanks.

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

I don't really understand your question. So I'll take things to the extreme and assume there are n1 books, n2 categories, n3 super categories... etc.

This whole hierarchy can be represented as a rooted tree, and the number of valid permutations would be the number of postorder traversals of the tree (or equivalently, preorder).

(I don't expect this will answer your question, I just thought it was interesting)

Also, if you'd like to find some middle ground between your specific example and my extremely overgeneralised... whatever this is... it might be easier to come up with a reasonable answer.

(edit...)

Some more points

This is not specific to matlab, just DSA in general

I still maintain that randomness is not the way to go for this problem.

As far as data structures go using arrays is fine, but for generality/scalability I suggest encoding the categories into the lists as well.

tree = {{1,2,3},{1,2},{1,2,3,4}} <- a cell array lets you structure data

Also, it's inefficient to check each new permutation against every saved entry. The usual thing to do is to use a set (a hashmap or a hashtable). But this adds the problem of computing a hash of the array (or finding some succinct unique id)

\$\endgroup\$
5
  • \$\begingroup\$ Thanks - what do you feel is unclear? I am trying to solve a very general permutation problem (which is easy to do by hand) but do it numerically. My approach is to random choose different arrangements, and to check if they have been previously found. Eventually for enough random samples, I end up with a list of all unique arrangements. I am wondering if there is a cleaner way to represent the data, instead of this 2 x 9 array of integers that I have used. \$\endgroup\$
    – teeeeee
    Commented May 5, 2021 at 11:23
  • \$\begingroup\$ In that case, is there really any major difference between your example and say just finding all permutations of n items (a 1 level problem, your's is a 2 level, the tree one is n level) \$\endgroup\$
    – user993732
    Commented May 5, 2021 at 11:27
  • \$\begingroup\$ Also, I don't really agree with using numerical methods to find this out. Usually numerical methods are used to find approximate solutions. eg approximating pi by generating random points in a unit square and seeing what percentage falls within a unit circle (both centered at origin), or newton-raphson, etc. For exact solutions like this, your question, rather than being "count the number" is closer to "generate all permutations". if you want to list out all permutations then there are better, non-random algorithms for that \$\endgroup\$
    – user993732
    Commented May 5, 2021 at 11:30
  • \$\begingroup\$ If you, for eg. wanted to know what percentage of random permutations of n books also leaves books of different categories together, then your approach would make sense (although you could still find the exact answer with factorials, even that exact answer would involve a division that would introduce some precision limits) \$\endgroup\$
    – user993732
    Commented May 5, 2021 at 11:34
  • \$\begingroup\$ Ofcourse there are better ways to solve this specific problem. The main reason for this is because I wanted to learn some of the techniques in Matlab such as generating random samples, choosing a suitable data structure to store the results in, and finding matches. That's why I called it a "brute-force" approach, but yes I agree that it can be described as "generate all unique permutations". \$\endgroup\$
    – teeeeee
    Commented May 5, 2021 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.