Shuffle order of cell array without repeating rows

I have a cell array of duplicated strings (filenames, in my application) the order of which I would like to pseudo-randomise, such that it is shuffled but without having repeated neighbouring entries.

For example, I can get a completely randomised ordering by using...

A = {"string1"; "string2"; "string3"; "string1"; "string2"; "string3"; "string1"; "string2"; "string3"; "string1"; "string2"; "string3"};
A = A(randperm(size(A, 1)), :)

...but this will often result in some entries repeating in adjacent rows, eg:

{["string2"]}
{["string3"]}
{["string2"]}
{["string2"]}
{["string2"]}
{["string3"]}
{["string1"]}
{["string3"]}
{["string3"]}
{["string1"]}
{["string1"]}
{["string1"]}

Is there a way I can ensure each row entry is always different to both its adjacent rows? Eg:

{["string3"]}
{["string1"]}
{["string2"]}
{["string1"]}
{["string2"]}
{["string3"]}
{["string1"]}
{["string2"]}
{["string1"]}
{["string3"]}
{["string2"]}
{["string3"]}

I guess I could use a while loop to keep randomising, but how would I terminate that loop by checking if the output is pseudo-random in the desired way?

[Michael]

(I realise I don't need to use 'size' here, but in my application my array has multiple columns - I only want to randomise the row ordering)

Answer 1

[Dyuman Joshi]

A brute force approach tailored to the example you have posted -

A = {"string1"; "string2"; "string3"; "string1"; "string2"; "string3"; "string1"; "string2"; "string3"; "string1"; "string2"; "string3"};

s = size(A,1);
r = numel(unique([A{:}]));
idx = randperm(s);
while any(diff(rem(idx,r))==0)
    idx = randperm(s);
end
idx

idx = 1×12

11 9 1 2 6 10 5 12 7 8 4 3

A(idx)

ans = 12×1 cell array
    {["string2"]}
    {["string3"]}
    {["string1"]}
    {["string2"]}
    {["string3"]}
    {["string1"]}
    {["string2"]}
    {["string3"]}
    {["string1"]}
    {["string2"]}
    {["string1"]}
    {["string3"]}

Answer 2

[Bruno Luong]

This does not require any special structure of the input (such as number of elements; or groups, or cardinal of groups, or the order)

% I change to string array rather than cell of strings
list = ["string2"
"string3"
"string2"
"string2"
"string2"
"string3"
"string1"
"string3"
"string4"
"string1"
"string1"
"string1"
"string1"
"string2"];

randperm_nrc(list)

ans = 14×1 string array
    "string4"
    "string2"
    "string1"
    "string2"
    "string3"
    "string1"
    "string2"
    "string1"
    "string3"
    "string1"
    "string2"
    "string3"
    "string2"
    "string1"

function listperm = randperm_nrc(list)
n = length(list);
[u,~,J]=unique(list);
cref = accumarray(J,1);
succeed = false;
while ~succeed
    c = cref;
    y = zeros(1,n);
    x = [];
    for i = 1:n
        cn = c;
        cn(x) = 0;
        cc = cumsum(cn);
        s = cc(end);
        succeed = s > 0;
        if ~succeed
            break
        end
        x = discretize(rand(), [0; cc/s]);
        c(x) = c(x)-1;
        y(i) = x;
    end
end
listperm = u(y);
end