Calculate a randomized array with some constraints.

Hello, for a psychological experiment I have the following problem. I need to calculate an array containing 70 distinct numbers. From these 70 numbers are 20 pairs (so e.g. two 1s, two 2s, two 3s etc.), all other numbers are zeros. The constraint is now that all pairs shall have a fixed index step-size to each other (e.g. if the step-size=2 and the first 3 lays at index 2, than the second 3 must lay at index 4), but apart from that the array should be completely random. The step-size should be variable between n=2 to n=20. Whether two pairs overlap (e.g. that if the step-size=2, and the first pair lays at index 2 and 4, and the second pair lays at index 3 and 5), doesn’t matter. Also how long Matlab needs, to find such an Array does not really matter, as long it does not take more than an hour or so.

Does anyone have an idea how I can tell Matlab to output me such an array? This is what I tried so far:

    myArray = [zeros(1,40),1:20,1:20]; % the array that shall be randomized,
                                       % under the bespoken constraint. 
    lags = 2;   % variable step-size
    pairs = 20; % number of pairs
    a=0;
    while a==0
        myArray = myArray(randperm(length(myArray))); % new randomization, new chance!
        for i=1:pairs
           tmp = find(myArray==i);
           if tmp(1)+lags~=tmp(2);     % if one pair has not the right index 
                                       %stepsize, interrupt for-loop.
               break;
           elseif i==pairs
               a=1;            % if all numbers are at their right 
                               % place stop the while loop
        end    
    end

However, I have to admit that this is totally bruteforce and in fact does never end (at least not within one hour ;-)).

I would be very very glad if someone could help me out with a smarter approach. Cheers.

[José-Luis]

I am not sure I understand. Couldn't you just pick a random starting pair and then fill your array with a random step size?

[brainybrown]

The steps-size should be an adjustable parameter (ranging from 2 to 20), but will always be the same for all pair lags within one array. An iterative way of filling the area would be of course great. However, the problem that I see with your suggestion is that this would only work for small step-sizes where the pairs do not overlap. However, for the larger step-sizes the pairs necessarily have to overlap in order to all fit into the array. And then I don't know how your suggestion would work?! But thank you for this first reply. Any other suggestions?

[José-Luis]

I am sorry, but I am not sure I understand what you'd like to achieve. Could you provide an example of the desired result?

[brainybrown]

Okay, lets say my Array consisted only of 20 elements, out of which were four pairs (1,1; 2,2; 3,3; 4,4) and the rest were twelve zeros (0,0,0,0,0,0,0,0,0,0,0,0). If I now set my step-size to n=2 I would like that Matlab returns me an array like this:

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

If I now change my step-size to n=4 Matlab shall return me an array like follows:

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

[brainybrown]

Array with step-size n=2:

the second 1 follows the first 1 two elements later, the second 2 follows the first 2 two elements later and so forth...

Array with step-size n=4

the second 1 follows the first 1 four elements later, the second 2 follows the first 2 four elements later, and so forth...

Answer 1

[José-Luis]

pairs = [1 1; 2 2; 3 3; 4 4];
your_array = zeros(1,20);
step_size = 4;

numPairs = size(pairs,1);
pos = 1:numel(your_array);

for ii = 1:numPairs
    %pick a pair
    idx = randi(size(pairs,1));
    current_val = pairs(idx,1);
    %Pick starting position
    posIdx = randperm(numel(pos)-step_size,1);
    your_array([pos(posIdx) pos(posIdx)+step_size]) = current_val;
    %Make it so the same positions cannot be picked again
    pos([posIdx posIdx+step_size]) = [];
    pairs(idx,:) = [];
end

disp(your_array)

Please accept an answer once it has solved your problem.

[brainybrown]

Hey, thank you very very much for this code snippet, this almost works. Tere seems to be only one tiny bug within the code. When I use 15 pairs and set the array to n=70 elements, your code produces for instance the following output:

     0
     0
     0
     0
    19
    20
     0
     0
    19
    20
     0
    14
     *8*
     0
     0
    14
     0
    11
     0
     3
    16
    11
     4
     3
    16
     0
     4
    18
    15
     0
     0
    18
    15
     0
     0
    *13*
     5
     0
     0
     0
     5
     2
     9
     0
     0
     2
     9
    12
     6
     0
     0
    12
     6
     0
    17
     7
     0
    10
    17
     7
     0
    10
     1
     0
     0
     0
     1
     0
     0
     0

So, as you see (see my highlighing) everything seems fine, apart from the fact that there is only one 8 and only one 13 contained in the array. Unfortunately I do not really understand your code. So I would be very glad if you could also fix this small bug?! Any ideas? Thank you again.

[José-Luis]

pairs = (1:15)';
pairs = [pairs pairs];

your_array = zeros(1,70);
step_size = 4;
numPairs = size(pairs,1);
pos = 1:numel(your_array);
for ii = 1:numPairs
    %pick a pair
    idx = randi(size(pairs,1));
    current_val = pairs(idx,1);
    %Pick starting position and check if both numbers can be saved
    condition = false;
    while ~condition
        posIdx = randi(numel(pos)-step_size,1);
        condition = your_array(pos(posIdx) + step_size) == 0;
    end
    your_array([pos(posIdx) pos(posIdx)+step_size]) = current_val;
    %Make it so the same positions cannot be picked again
    pos([posIdx posIdx+step_size]) = [];
    pairs(idx,:) = [];
end
disp(your_array)

Please note that this will become slower and slower the more non-zero values you want to put in. It might also get stuck in an infinite loop.

[José-Luis]

Slightly better, returns control to command prompt if all pairs cannot be placed. Note that this is more likely to happen when there are not that many zeros. Say you have 15 pairs and 30 spaces with a step of five, then the approach should be different.

pairs = (1:15)';
pairs = [pairs pairs];

your_array = zeros(1,35);
step_size = 4;
numPairs = size(pairs,1);

test_array = [your_array; circshift(your_array,[0 -step_size])];
test_array(:,end-step_size:end) = [];

for ii = 1:numPairs
    %pick a pair
    idx = randi(size(pairs,1));
    current_val = pairs(idx,1);
    %Pick starting position and check if both numbers can be saved
    %Finding all possible positions for the new pair:
    valid = find(sum(test_array) == 0);
    if isempty(valid)
       disp('Could not find a position to place pair, please try again');       
       return
    end
    %Selecting position randomly
    posIdx = valid(randi(numel(valid),1));
    your_array([posIdx posIdx+step_size]) = current_val;
    %Make it so the same positions cannot be picked again
    pairs(idx,:) = [];
    test_array = [your_array; circshift(your_array,[0 -step_size])];
    test_array(:,end-step_size:end) = [];
end
disp(your_array)

[brainybrown]

Awesome, thank you very very much for your help. I have currently no Matlab here at home, but I will test it tomorrow. Thank you.