How to randomly permute elements from two lists while respecting a non-consecutive ordering constraint?

Question

I am part of a study where subjects are given input from 4 categories (1, 2, 3, 4) and each category has 4 words (a, b, c, d). The order of the words needs to be randomized for each subject, but consecutive words should be from different categories.

I am fairly new to coding and have been working on an algorithm that can do this, but it is getting pretty long and complicated, and I feel there should be a simpler way to do it that is less prone to errors. Any help would be much appreciated!

Answer 1

Here is a "brute force" (computationally inefficient, but simple) method.

1. Produce a randomized list.
2. Check whether the list meets the criteria.
3. Repeat until you have collected as many valid lists as you need.

    source = ["1a","1b","1c","1d","2a","2b","2c","2d","3a","3b","3c","3d","4a","4b","4c","4d"]
    valid = []
    num_valid = 100
    
    until valid.length >= num_valid do
      candidate = source.shuffle
    
      if candidate.each_cons(2).all? {|a,b| a[0] != b[0] }
        valid |= [candidate]
      end
    end

When the example code above terminates, valid will contain 100 different valid lists.

Answer 2

Decomposing the problem (in one way; there are others):

• Need a list of non-repeating categories
  • TBD: What about [a, b, a, ...]
    • E.g., does each group of words.length combos need a word from each category
  • TBD: Do cats need to be the same order for each group of words
    • E.g., which:
      • [c, b, d, a, c, b, d, a, ...] (same cats each words group) or
      • [c, b, d, a, b, a, c, d, ...] (different cats)
  • Minor tweaks either way
• That list is length cats.length * words.length (num of combos)

Verbosely-but-clear-ishly: it's a flat-map of category shuffles, one per words.length, with re-shuffles (if needed) until the shuffle's first entry is different from the previous shuffle's last entry.

Take that in chunks of words.length and associate each category with a word from a shuffled word list.

Naive implementation, probably, but reasonably clear, and a dozen or two lines of code without trying to be clever (which I definitely didn't :rofl:). In other words: it doesn't need to be super-complicated to meet the requirements--might be worth trying to think about it a different way.

Answer 3

Here is a method that is only slightly different than @user513951's, but may possibly be more efficient with the array is large. Like the earlier method it loops until a random selection has the required property. Both methods produce a statistically random sample (subject to limitations in the production of truly random values in software).

The earlier method extracts the category of each of two string in the block { |a,b| a[0] != b[0] }. This assumes, however, that there are no more than 9 categories. If the category may be comprised of two or more digits the digits would have to be stripped off the front of the string. Probably it would be more efficient to have a pre-processing step that makes a and b in the aforementioned block two-element arrays (which would require some tidying up at the end). That would be a simple change to the earlier method.

If we are given

a = ["1a", "1b", "1c", "1d", "20a", "20b", "20c", "20d",
     "3a", "3b", "3c", "3d", "41a", "41b", "41c", "41d"]

we may start by computing¹

arr = a.map { |s| s.split(/(?<=\d)(?=\D)/) }
  #=> [["1", "a"], ["1", "b"], ["1", "c"], ["1", "d"],
  #    ["20", "a"], ["20", "b"], ["20", "c"], ["20", "d"],
  #    ["3", "a"], ["3", "b"], ["3", "c"], ["3", "d"],
  #    ["41", "a"], ["41", "b"], ["41", "c"], ["41", "d"]]

When compared to the earlier method the only change I am proposing is to first obtain a random sequence of categories that satisfies the desired property. Once found I will convert that to a return value that remains an unbiased sample selection.

In effect I am simplifying the block { |a,b| a[0] != b[0] } to { |x,y| x != y }, where x and y are categories. The improvement in efficiency could be significant for very large arrays.

---

First create a hash that maps categories to an array of their words.

h = arr.each_with_object(Hash.new { |h,k| h[k] = [] }) do |(cat,word),h|
  h[cat] << word
end
  #=> {"1"=>["a", "b", "c", "d"], "20"=>["a", "b", "c", "d"],
  #    "3"=>["a", "b", "c", "d"], "41"=>["a", "b", "c", "d"]}

Next, shuffle the elements of each value to preserve randomness later.

h.transform_values!(&:shuffle)
  #=> {"1"=>["b", "d", "a", "c"], "20"=>["b", "c", "a", "d"],
  #    "3"=>["d", "b", "c", "a"], "41"=>["a", "d", "c", "b"]}

Then select the keys replicated by the sizes of their values (which need not be all the same for all keys).

keys = h.each_with_object([]) { |(k,v),a| a.concat([k]*v.size) }
  #=> ["1", "1", "1", "1", "20", "20", "20", "20",
  #    "3", "3", "3", "3", "41", "41", "41", "41"]

Now find a sequence of categories that satisfies the desired property.

loop do
  n += 1
  keys.shuffle!
  break keys if keys.each_cons(2).all? { |x,y| x != y }
end
  #=> ["1", "41", "3", "20", "41", "20", "1", "20",
       "3", "41", "1", "3", "1", "20", "41", "3"]

(Upon executing this several times it always took under 70 iterations to find a valid sequence.)

Lastly, append the randomized words for each category to produce a random array that satisfies the required property.

keys.map { |k| "#{k}#{h[k].shift}" }
  #=> ["1b", "41a", "3d", "20b", "41d", "20c", "1d", "20a",
  #    "3b", "41c", "1a", "3c", "1c", "20d", "41b", "3a"]

^{1. (?<=\d) is a positive lookbehind that asserts that the match is preceded by a digit. (?=\D) is a positive lookahead that asserts that the match is followed by a character other than a digit. This regular expression therefore matches the zero-width location between the last digit in the string and the first non-digit.}