Creating a random matrix of no duplicates in both row and column from a given set list of elements

With the conditions that each row must not contain duplicates and each column must not contain duplicates, construct a random solution matrix by rows. The first row is a random sample of the permutations of gps. The following rows are selected at random from the remaining permutations that satisfy the conditions.

There are two questions to consider from comments: 1) does the first row determine the rest of the matrix, and 2) is the resulting matrix truly random or does it contain structure and pattern.

Question 1: The first row determines the rest of the solution matrix because each row after the first must be a member of a subset of the permutations of gps, such that no column can match the corresponding column of the previous rows.

To demonstrate the method, consider the set {A,B,C,D,E}. Here's a graph that shows how selecting rows at random proceeds from row 1 to row 4.

Starting with {A,B,C,D,E}, there are 44 possibilities for row 2. Selecting {D,A,B,E,C} leaves 13 possibilities for row 3. Selecting {E,C,D,A,B} leaves 4 possibilities for row 4. Choosing {C,E,A,B,D} completes the solution matrix.

{A,B,C,D,E}
{D,A,B,E,C}
{E,C,D,A,B}
{C,E,A,B,D}

Question 2: The solution matrix cannot be truly random because of the conditions that no row or column contain matches. Rows 2,3,4 are generated from row 1, but row 1 is random. There must be structure and pattern for the following rows because of the condition that there are no matching columns. However, rows 2,3,4 are randomly selected from every possible row that satisfies the conditions given the previous rows. The solution matrix is as random as it can be while satisfying the conditions.

Here's a revised method that replaces my original attempt.

perms = StringJoin[#] & /@ Permutations[gps];
rows = {StringJoin[RandomSample[gps]]};
Do[
 regex = StringRiffle[Characters[Last@rows], {"^[^", "][^", "]$"}];
 perms = Flatten@
   DeleteCases[StringCases[perms, RegularExpression[regex]], {}];
 AppendTo[rows, RandomChoice[perms]];
 , 3]
(matrix = Characters[rows]) // MatrixForm

The permutations, perms, rows are saved as strings. Use a regular expression to remove permutations that match any column of the current row. Select a new row from the remaining permutations.