Permutations of a wordlist with criteria in MatLab

Question

I have a wordlist of 12 items, consisting of 4 semantic categories with 3 items in each category. This includes couch, shelf, table (furniture), plane, boat, truck (vehicles), Jacket, shoes, sweater (clothes), lettuce, carrot, spinach (Vegetables). I need to produce a randomised list with these 12 items, however there are some rules.

Firstly, items from the same semantic category cannot neighbour each other in the list (e.g lettuce and spinach). Second, the list is divided into 3 blocks (items 1-4, 5-8 and 9-12). In each block, there must be atleast but no more than one item from each semantic category.

Complete coding noob so I understand how to calculate permutations but I have no idea how to implement the other rules. Any help greatly appreciated.

A previous solver produced a solution but gave the answer for python. I'm sorry but I have no coding ability whatsoever and could not translate it across.

Tried using

% Wordlist
wordlist = {'Carrot', 'Spinach', 'Lettuce', 'Jacket', 'Shoes', 'Sweater', 'Plane', 'Boat', 'Truck', 'Shelf', 'Table', 'Couch'};

% Define semantic categories
categories = {'Vegetables', 'Clothing', 'Vehicles', 'Furniture'};

while true
    
% Shuffle indices

    shuffled_indices = randperm(length(wordlist));
    
    % Check semantic relatedness and ensure no two related items neighbor each other
    no_neighboring_related = all(arrayfun(@(i) ~any(ismember(wordlist(shuffled_indices(i:i+1)), categories)), 1:length(shuffled_indices)-1));
    
    % Check representation in each block
    representation_in_blocks = all(arrayfun(@(a) numel(unique(wordlist(shuffled_indices(a:a+3)))) == 4 && ...
        all(ismember(categories, wordlist(shuffled_indices(a:a+3)))), [1, 5, 9]));
    
    % If both conditions are met, break out of the loop
    if no_neighboring_related && representation_in_blocks
        break;
    end
end

% Display the randomly generated wordlist
disp('Randomly Generated Wordlist:');
disp(wordlist(shuffled_indices));

However this never stops running and has to be paused.

Answer 1

You say

In each block, there must be at least but no more than one item from each semantic category

We can simplify that condition to say there must be exactly one item from each category. You don't specify, but I'm going to assume you don't want any repeats of each item in the whole list - I'll point out where you can change the following code to allow duplicates at the end.

Here is commented code which starts by assigning a 2nd row to wordlist to track the category of each item, then loops through each block and picks a random item from each category in turn, then removes that category as an option for the rest of the block and keeps selecting.

wordlist = {'Carrot', 'Spinach', 'Lettuce', 'Jacket', 'Shoes', 'Sweater', 'Plane', 'Boat', 'Truck', 'Shelf', 'Table', 'Couch'};
cats = {'Vegetables', 'Clothing', 'Vehicles', 'Furniture'};

ncats = numel(cats); % number of categories
nblocks = numel(wordlist)/ncats; % number of blocks
wordlist(2,:) = repelem(cats,1,nblocks); % make 2nd row for categories

% Intialise output and loop var
thisCat = '';
shuffled = cell(1,size(wordlist,2));
% Loop over each block, where each block contains one of each category
for iblk = 1:nblocks
    % Reset "c" to be the list of all categories available to choose from
    c = cats;
    % Loop over the categories
    for ic = 1:ncats
        % Randomly pick a category from the list
        % Avoiding duplicate neighbours
        rc = randi(ncats+1-ic);
        while strcmp(c{rc},thisCat) 
            rc = randi(ncats+1-ic); % keep picking...
        end
        % Update current category
        thisCat = c{rc};
        % Find the indicies of words in this category
        idxcat = find(strcmp(wordlist(2,:),thisCat));
        % Pick a random one of those indicies
        iw = idxcat(randperm(numel(idxcat),1)); 
        % Add this work to the output list
        shuffled{(iblk-1)*ncats+ic} = wordlist{1,iw};
        % remove category from choices for this block
        c(rc) = []; 
        % remove work from choices forever
        wordlist(:,iw) = [];         
    end
end

You could omit the wordlist(:,iw) = [] line if you don't mind having duplicate words, since it will still check against repeated categories at the start of each loop, but can match from more options within wordlist.