Curious if this problem can be solved more elegantly (maybe using recursion?)

Question

I'm a graduate student in biology that encountered a problem that I really struggled solving in my project. I solved it using an iterative approach (will describe more below) but was curious if there was a simpler or more elegant solutions to this.

I wanted to generate a sequence of numbers. Let's assume we have vector v = 1:12. I want to generate a sequence consisting of the vector v = 1:12, with n repetitions. The resulting sequence will be of length v * n. Additionally, for each element of this sequence, I want to add a boolean value (I will explain more below).

I want this sequence to meet several conditions:

1. In each repetitions of vector v, I want the elements 1:12 to appear in random order. (this seems straightforward enough to me)
2. The boolean that is being assigned to each element of the sequence must be balanced within a repetition. That is, for a given nth repetition, I want there to be 6 true and 6 false.
3. Each value in vector v should have the same number of true and false across the entire sequence.

For example if n=10, I have a sequence of length 120. In this sequence, there should be 1 with 5 true and 5 false. 2 with 5 true and 5 false so on and so forth.

I tried to solve this problem by imposing conditions. If we get really unlucky when generating the initial repetitions, by n/2 repetition, we may have a value in v that never gets a true draw. Then, I need to place a condition that this value needs to be drawn for the remainder of the repetitions etc etc. You can apply similar logic for a value that has only been drawn once, twice, etc..

What would be the most easiest way to solve this? I have a code in MATLAB that works but would love to hear more solutions to this. It reminds me of a sudoku problem but honestly I have to admit I spent way too much time trying to figure this out so am reaching out for help. Thanks!

edit: another condition that I didn't think is that the vector v should be of even size so I can have an even number of true and false assignments. So vector of 1:4 and 2 repetitions will look like: 1 3 2 4 2 3 1 4 and 1 1 0 0 1 0 0 1. I would be interested if this can extend to cases like 2/3 true and 1/3 false..

Answer 1

If I've understood your requirements correctly, this can be solved by pairing each numeric value with a shuffled set comprised of equal numbers of binary trues and falses, then shuffling the pairings n times and constructing the output from the current iteration's shuffled value and the corresponding binary value found at the iteration's index.

This is a case where I think code is clearer than an English description. Since you tagged pseudo-code I've chosen to implement it in Ruby, which is essentially pseudo-code that you can actually run.

First, let's create the pairings:

N = 4

# Define a structure containing a value and associated binary values
PairedSet = Struct.new(:value, :binary_values)

# Now create an array with four of the structures. The value is set
# to the current iteration plus 1 (ruby arrays have 0-based indexing).
# The binary values are set to the desired number of trues and false,
# then shuffled.
collection = Array.new(4) do |i|
  PairedSet.new(i+1, [1, 1, 0, 0].shuffle )
end

# Pretty print the collection, followed by a blank line.
pp collection
puts

At this point sample output of the collection looks like:

[#<struct PairedSet value=1, binary_values=[1, 0, 0, 1]>,
 #<struct PairedSet value=2, binary_values=[1, 1, 0, 0]>,
 #<struct PairedSet value=3, binary_values=[1, 0, 0, 1]>,
 #<struct PairedSet value=4, binary_values=[0, 0, 1, 1]>]

Now we create empty arrays to gather the results, then iterate through the collection the desired number of times. The current iterate is indexed by i. For each iteration, we shuffle the collection so the values and associated binary values will occur in a randomized order. We concatenate each pair's value to the values output array, and concatenate the current iteration's associated boolean to the boolean output array. Finally, we print the two sets of outputs. Note that they are vertically aligned to we can easily confirm that each value is associated by index with the desired number of trues/falses.

values = []
bools = []
N.times do |i|
  collection.shuffle.each do |pair|
    values << pair.value
    bools << pair.binary_values[i]
  end
end

puts values.inspect
puts bools.inspect

which produces sample results such as:

[2, 3, 4, 1, 2, 1, 3, 4, 4, 1, 2, 3, 3, 1, 2, 4]
[1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1]

Note that shuffling is random, so you should expect different actual outcomes if you run the provided code.

---

ADDENDUM

In a comment you said "Although I would be interested if this can extend to cases like 2/3 true and 1/3 false .. but not sure if the balancing across elements would work". There's no bar to accomplishing that using the shuffling approach. The only requirement is that N must equal the total number of binary outcomes in the initialization of the collection.

For example:

N = 3

PairedSet = Struct.new(:value, :binary_values)

collection = Array.new(4) do |i|
  PairedSet.new(i+1, [1, 1, 0].shuffle )
end

will produce output such as:

[1, 4, 2, 3, 3, 2, 4, 1, 1, 3, 2, 4]
[1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0]