Help finding max number of combinations of letters and numbers with constraints and create a list

Questions
1

Hi forum members

With some set constraints, I’d like to be able select a number between 1-5, combine it with a letter between a-e, find the maximum number of unique variations and generate a list.

The constraints are:
In a combination, the order of letters must be unique for every person 1-5.
Every new combination should be unique for every person.

Combination 1
Person 1: a, b, c, d, e
Person 2: b, a, d, e, c
Person 3: c, d, e, a, b
Person 4: d, e, b, c, a
Person 5: e, c, a, b, d

Combination 2
Person 1: a, b, c, e, d
Person 2: b, a, d, c, e
Person 3: c, d, e, b, a
Person 4: d, e, b, a, c
Person 5: e, c, a, d, b

Combination 3
Person 1: a, b, d, c, e
Person 2: b, a, c, e, d
Person 3: c, e, a, d, b
Person 4: d, c, e, b, a
Person 5: e, d, b, a, c

Combination 4
Person 1: a, b, d, e, c
Person 2: b, a, c, d, e
Person 3: c, e, a, b, d
Person 4: d, c, e, a, b
Person 5: e, d, b, c, a

etc…

Is this possible to make somehow?

I cross my fingers :slight_smile:

Praveer

2

The number of permutations of {a,b,c,d,e} is 120. So, there is a theoretical max for the number of combinations (because you want uniqueness of the permutations for a particular person across all combinations). Can we achieve that theoretical maximum. It seems to me that if we start with some list of all permutations, rotate that list by an appropriate amount for each person, then each combination will be unique.

To demonstrate, I’ll use three letters to save space:

perms = Permutations[Take[Alphabet[], 3]]
(* {{"a", "b", "c"}, {"a", "c", "b"}, {"b", "a", "c"}, {"b", "c", "a"}, {"c", "a", "b"}, {"c", "b", "a"}} *)

TableForm[
  Map[StringJoin, NestList[RotateRight, perms, 4], {-2}], 
  TableDirections -> Row, 
  TableHeadings -> {{"Person 1", "Person 2", "Person 3", "Person 4", "Person 5"}, {"Combinations", "\[VerticalEllipsis]"}}]

Screenshot2025-04-08at17.22.14.png
Screenshot2025-04-08at17.22.14.png918×388 30.9 KB

Now, I’m not totally sure I understood your constraints. Maybe you meant that no permutation should show up more than once anywhere. Or maybe your comment about “order of letters” being unique means something different than what I thought. If so, please clarify your constraints, and maybe provide a sample output for a smaller set of permutations.

3

It sounds like you want to generate all possible Latin Squares of size 5 x 5. Take a look at https://mathematica.stackexchange.com/questions/246114/finding-all-latin-squares-of-order-5.

There are 161,280 unique Latin Squares of order 5. Using the code in that link we have

addline[lines_] := Select[Append[lines, #] & /@ Permutations[Range[Length[Transpose[lines]]]], 
  AllTrue[DuplicateFreeQ]@*Transpose]
latinsquares[n_] := Nest[Join @@ addline /@ # &, Transpose[{Permutations[Range[n]]}], 
  n - 1]
g = latinsquares[5] /. {1 -> "a", 2 -> "b", 3 -> "c", 4 -> "d", 5 -> "e"}
Length[g]
(* 161280 *)

Now suppose we restrict the Latin Squares to have the first row and first column equal to a, b, c, d, e. There are 56 such unique Latin Squares.

Select[g, #[[1, 1]] == "a" && #[[2, 1]] == "b" && #[[3, 1]] == "c" && #[[4, 1]] == "d" && #[[5, 1]] == "e" &];
g2 = Select[ g2, #[[1, 1]] == "a" && #[[1, 2]] == "b" && #[[1, 3]] == "c" && #[[1, 4]] == "d" && #[[1, 5]] == "e" &];
(# // MatrixForm) & /@ g2

g2.png
g2.png985×1028 26.9 KB

So if you are interested in a subset of the 161,280 unique Latin Squares of order 5, you need to be more specific with the restrictions you have in mind.

4

We first start by generating all 5! permutations of the 5 letters:

letters = Take[Alphabet[], 5];
perms = Permutations[letters];

And now we create a relation graph, the vertices of which indicate if two permutations share no common letters in the same position as each other:

relationTest = FreeQ[#1 - #2, 0] &;
graph = RelationGraph[relationTest, perms];

We now find all cliques of the graphs with exactly 5 vertices, these correspond to the valid 5x5 letter matrices

pass = FindClique[graph, {5}, All] ;

And now we require that in each letter matrix, each person is a given a new 5-letter string. So we create another relation graph among the letter matrices, where the vertices indicate whether the two matrices give new strings to each person. This took about 1 min on my laptop:

cliquesAreDistinct = FreeQ[Total /@ Abs[#1 - #2], 0] &;
cliqueGraph = RelationGraph[cliquesAreDistinct, pass];

And find the maximal clique, which has 24 5x5 combinations satisfying the constraints

best = FindClique[cliqueGraph][[1]] // Sort;
best//Length
(*24*)

Here they are

a	b	c	d	e
b	a	d	e	c
c	d	e	a	b
d	e	b	c	a
e	c	a	b	d


a	b	c	e	d
b	a	d	c	e
c	d	e	b	a
d	e	b	a	c
e	c	a	d	b


a	b	d	c	e
b	a	e	d	c
c	d	a	e	b
d	e	c	b	a
e	c	b	a	d


a	b	d	e	c
b	a	e	c	d
c	d	a	b	e
d	e	c	a	b
e	c	b	d	a


a	b	e	c	d
b	c	a	d	e
c	e	d	a	b
d	a	b	e	c
e	d	c	b	a


a	b	e	d	c
b	c	a	e	d
c	e	d	b	a
d	a	b	c	e
e	d	c	a	b


a	c	b	d	e
b	d	c	e	a
c	a	e	b	d
d	e	a	c	b
e	b	d	a	c


a	c	b	e	d
b	d	c	a	e
c	a	e	d	b
d	e	a	b	c
e	b	d	c	a


a	c	d	b	e
b	d	a	e	c
c	e	b	a	d
d	a	e	c	b
e	b	c	d	a


a	c	d	e	b
b	d	a	c	e
c	e	b	d	a
d	a	e	b	c
e	b	c	a	d


a	c	e	b	d
b	e	a	d	c
c	d	b	a	e
d	b	c	e	a
e	a	d	c	b


a	c	e	d	b
b	e	a	c	d
c	d	b	e	a
d	b	c	a	e
e	a	d	b	c


a	d	b	c	e
b	c	d	e	a
c	e	a	b	d
d	b	e	a	c
e	a	c	d	b


a	d	b	e	c
b	c	d	a	e
c	e	a	d	b
d	b	e	c	a
e	a	c	b	d


a	d	c	b	e
b	e	d	a	c
c	b	e	d	a
d	c	a	e	b
e	a	b	c	d


a	d	c	e	b
b	e	d	c	a
c	b	e	a	d
d	c	a	b	e
e	a	b	d	c


a	d	e	b	c
b	e	c	d	a
c	a	b	e	d
d	b	a	c	e
e	c	d	a	b


a	d	e	c	b
b	e	c	a	d
c	a	b	d	e
d	b	a	e	c
e	c	d	b	a


a	e	b	c	d
b	c	e	d	a
c	b	d	a	e
d	a	c	e	b
e	d	a	b	c


a	e	b	d	c
b	c	e	a	d
c	b	d	e	a
d	a	c	b	e
e	d	a	c	b


a	e	c	b	d
b	d	e	c	a
c	a	d	e	b
d	c	b	a	e
e	b	a	d	c


a	e	c	d	b
b	d	e	a	c
c	a	d	b	e
d	c	b	e	a
e	b	a	c	d


a	e	d	b	c
b	a	c	e	d
c	b	a	d	e
d	c	e	a	b
e	d	b	c	a


a	e	d	c	b
b	a	c	d	e
c	b	a	e	d
d	c	e	b	a
e	d	b	a	c
5

Sorry about the formatting, when I show the post in preview it looks perfectly fine, but then the formatting becomes jumbled once I post.

6

Thanks so much for all your replies :slight_smile:

Eric asked:
“Now, I’m not totally sure I understood your constraints. Maybe you meant that no permutation should show up more than once anywhere.”

This is exactly what I meant :slight_smile:
I’m not expecting many combinations, especially with fewer persons and letters.

Perhaps this is constructing a Latin square or a disjoint set of permutations where each person’s sequence is unique both within and across combinations?

Here’s the first 4 combinations for 5 persons and 5 letters.

Combination 1
Person 1: a, b, c, d, e
Person 2: b, a, d, e, c
Person 3: c, d, e, a, b
Person 4: d, e, b, c, a
Person 5: e, c, a, b, d

Combination 2
Person 1: a, b, c, e, d
Person 2: b, a, d, c, e
Person 3: c, d, e, b, a
Person 4: d, e, b, a, c
Person 5: e, c, a, d, b

Combination 3
Person 1: a, b, d, c, e
Person 2: b, a, c, e, d
Person 3: c, e, a, d, b
Person 4: d, c, e, b, a
Person 5: e, d, b, a, c

Combination 4
Person 1: a, b, d, e, c
Person 2: b, a, c, d, e
Person 3: c, e, a, b, d
Person 4: d, c, e, a, b
Person 5: e, d, b, c, a

Ideally, whenever possible the valid combinations would be moved around between the persons so that the same beginning letter for a person is only used as little as possible.

Combination 1
Person 1: a, b, c, d, e
Person 2: b, a, d, e, c
Person 3: c, d, e, a, b
Person 4: d, e, b, c, a
Person 5: e, c, a, b, d

Combination 2
Person 1: b, a, d, c, e (actually person 2 result)
Person 2: a, b, c, e, d (actually person 1 result)
Person 3: d, e, b, a, c (actually person 4 result)
Person 4: c, d, e, b, a (actually person 3 result)
Person 5: e, c, a, d, b (not possible to move to another person)

Thank you.

7

Formatting should look better now.