Calculating number of permutations with exclusion criterion 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 at least, but no more, than one item from each semantic category.

The implementation should be in Matlab

Answer 1

The following procedure will produce a list that satisfies the adjacency requirement. It represents a pseudo-random sample from all such lists due to the the symmetry of the underlying conditional probability calculations.

word_lists = [
  ["couch", "shelf", "table"],
  ["plane", "boat", "truck"],
  ["jacket", "shoes", "sweater"],
  ["lettuce", "carrot", "spinach"]
]

word_lists, and each element (array) thereof, can of course be of any size.

---

We begin by creating an array from word_lists that saves the category offsets with each element of each category:

[[["couch", 0], ["shelf", 0], ["table", 0]],
 [["plane", 1], ["boat", 1], ["truck", 1]],
 [["jacket", 2], ["shoes", 2], ["sweater", 2]],
 [["lettuce", 3], ["carrot", 3], ["spinach", 3]]]

Next, each element (array) of this array can be shuffled:

[[["shelf", 0], ["table", 0], ["couch", 0]],
 [["boat", 1], ["plane", 1], ["truck", 1]],
 [["sweater", 2], ["shoes", 2], ["jacket", 2]],
 [["carrot", 3], ["spinach", 3], ["lettuce", 3]]]3

Now take the transpose of this array:

[[["couch", 0], ["plane", 1], ["jacket", 2], ["lettuce", 3]],
 [["shelf", 0], ["boat", 1], ["shoes", 2], ["carrot", 3]], 
 [["table", 0], ["truck", 1], ["sweater", 2], ["spinach", 3]]]

Next, shuffle the elements in each row:

arr
  #=> [[["lettuce", 3], ["plane", 1], ["jacket", 2], ["couch", 0]],
  #    [["shelf", 0], ["boat", 1], ["carrot", 3], ["shoes", 2]], 
  #    [["truck", 1], ["sweater", 2], ["table", 0], ["spinach", 3]]]

---

If we were to partially flatten this array in preparation to producing the randomized list we would obtain:

[["lettuce", 3], ["plane", 1], ["jacket", 2], ["couch", 0], 
 ["shelf", 0], ["boat", 1], ["carrot", 3], ["shoes", 2],
 ["truck", 1], ["sweater", 2], ["table", 0], ["spinach", 3]]

This does not meet requirements, however, as "shelf" follows "couch", both being in the same category (offset 0 in word_lists).

We need to first compare

(arr[0].last).last #=> ["couch", 0].last => 0

with

(arr[1].first).last #=> ["shelf", 0].last => 0

Since these values are the same we need to randomly reposition ["shelf", 0] in

arr[1]
  #=> [["shelf", 0], ["boat", 1], ["carrot", 3], ["shoes", 2]]

We can do that by randomly selecting an index between 1 and 3 and inserting it after element arr[1][i]. Suppose the random index were 2. We would then have:

[["shelf", 0], ["boat", 1], ["carrot", 3], ["shelf", 0], ["shoes", 2]]

Of course we would have to remove the first element of this array to obtain:

[["boat", 1], ["carrot", 3], ["shelf", 0], ["shoes", 2]]

We then have

arr
  #=> [[["lettuce", 3], ["plane", 1], ["jacket", 2], ["couch", 0]],
  #    [["boat", 1], ["carrot", 3], ["shelf", 0], ["shoes", 2]],
  #    [["truck", 1], ["sweater", 2], ["table", 0], ["spinach", 3]]]

Since

(arr[1].last).last #=> ["shoes", 2].last #=> 2

and

(arr[2].first).last #=> ["truck", 1].last #=> 1

differ, there is no need to reposition ["truck", 1] in arr[2].¹

We can now partially flatten arr to obtain

[["lettuce", 3], ["plane", 1], ["jacket", 2], ["couch", 0],
 ["shelf", 0], ["boat", 1], ["carrot", 3], ["shoes", 2],
 ["truck", 1], ["sweater", 2], ["table", 0], ["spinach", 3]]

and then map each element of this array (an array) into that element's first value, to obtain a pseudo-random list that meets the adjacency requirement:

["lettuce", "plane", "jacket", "couch",
 "shelf", "boat", "carrot", "shoes",
 "truck", "sweater", "table", "spinach"]

^{1. Note that if ["shelf", 0] had been randomly moved to the end of arr[1] in the previous step and the first element of arr[2] had been ["table", 0] (rather than ["truck", 1]), the latter would have had to be moved in arr[2]}.

Answer 2

After thought, I'll just give pseudocode. And make it look Matlab-like enough that you can probably figure out how to make it work.

First, your words can be arranged in an array of arrays. Like this.

word_lists = [
    ["couch", "shelf", "table"],
    ["plane", "boat", "truck"],
    ["jacket", "shoes", "sweater"],
    ["lettuce", "carrot", "spinach"]]

Let's scramble each internal list. I'm guessing the syntax is something like this:

for i = 1:4
    word_lists[i] = word_lists[i](randperm(3))
end

Now let's choose the choices of lists. (Each list is one category.)

list_choices = [randperm(4), randperm(4), randperm(4)]

But there can be a problem. We might have the last list choice in the one group be the same as the first list choice in the next group. Fix that.

while list_choices(1, 4) == listchoices(2, 1)
    list_choices(2) = randperm(4)
end

while list_choices(2, 4) == listchoices(3, 1)
    list_choices(3) = randperm(4)
end

And now extract your wordlist. If I have the indexing rules right it should be something like this:

word_list = cat(1,
                word_lists(list_choices(1), 1),
                word_lists(list_choices(2), 2),
                word_lists(list_choices(3), 3))