# Duplicate Permutations with Tuples

• Permutations without repetition

(in Italian: simple dispositions)

Permutations[{a, b, c, d}, {3}]


or

Select[Tuples[{{a, b, c, d}, {a, b, c, d}, {a, b, c, d}}], DuplicateFreeQ]

• Permutations with repetition

(in Italian: dispositions with repetition)

Tuples[{a, b, c, d}, 3]


or

Tuples[{{a, b, c, d}, {a, b, c, d}, {a, b, c, d}}]

• Combinations without repetition

(in Italian: simple combinations)

DeleteDuplicates[Map[Sort, Permutations[{a, b, c, d}, {3}]]]


or

DeleteDuplicates[Map[Sort, Select[Tuples[{{a, b, c, d}, {a, b, c, d}, {a, b, c, d}}], DuplicateFreeQ]]]

• Combinations with repetition

(in Italian: combinations with repetition)

DeleteDuplicates[Map[Sort, Tuples[{a, b, c, d}, 3]]]


or

DeleteDuplicates[Map[Sort, Tuples[{{a, b, c, d}, {a, b, c, d}, {a, b, c, d}}]]]

• Permutations of n distinct elements

(in Italian: idem)

Permutations[{a, b, c, d}, {4}]


or

Select[Tuples[{{a, b, c, d}, {a, b, c, d}, {a, b, c, d}, {a, b, c, d}}], DuplicateFreeQ]

• Permutations of n elements with a element repeating twice

(in Italian: idem)

Permutations[{a, b, c, c}, {4}] =

= {{a, b, c, c}, {a, c, b, c}, {a, c, c, b}, {b, a, c, c}, {b, c, a, c}, {b, c, c, a},
{c, a, b, c}, {c, a, c, b}, {c, b, a, c}, {c, b, c, a}, {c, c, a, b}, {c, c, b, a}}


or

?????????

Can you tell me a way to duplicate this command with the use of "Tuples[matrix]"?

Thank you!

• Select[Tuples[{{a, b, c, d}, {a, b, c, d}, {a, b, c, d}, {a, b, c, d}}], DuplicateFreeQ] /. d -> c – Feyre Feb 7 '17 at 18:30
• @Feyre: perhaps you mean to write ... DeleteDuplicates[Select[Tuples[{{a, b, c, d}, {a, b, c, d}, {a, b, c, d}, {a, b, c, d}}], DuplicateFreeQ] /. d -> c] ... Anyways good idea, I had not thought. Perhaps there is some command more general? Without having to change the letters each time. – TeM Feb 7 '17 at 18:38
• x = {a, b, c, c}; DeleteDuplicates@Select[Tuples[{x, x, x, x}], Sort[#] == Sort[x] &] – Simon Woods Feb 7 '17 at 21:57

I recommend not generating more tuples than you need, then filtering output, as that method "blows up" very easily.

Instead I would draw your attention to the similarity between this problem and a shuffle product:

Using the f function from my answer there:

f[u : {a_, x___}, v : {b_, y___}, c___] := f[{x}, v, c, a] ~Join~ f[u, {y}, c, b]

f[{x___}, {y___}, c___] := {{c, x, y}}


Compare the outputs of:

f[{1}, {2, 2, 2}]

Permutations[{1, 2, 2, 2}]

{{1, 2, 2, 2}, {2, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 1}}

{{1, 2, 2, 2}, {2, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 1}}


So we can implement a duplicate-aware permutation function using f as follows:

f2[a_, b_] := Join @@ (f[#, b] & /@ a)

perms[a_List] := Fold[f2, {{}}, Gather[a]]


Test:

Sort @ perms[{1, 2, 2, 2, 3, 3}] === Sort @ Permutations[{1, 2, 2, 2, 3, 3}]

True


A simplification(?) to making f work on multiple lists using f2 and Fold is to write a multiple-list shuffle product directly using ReplaceList.

f3[in_, out___] :=
Join @@ ReplaceList[in, {x___, {a_, b___}, y___} :> f3[{x, {b}, y}, out, a]]

f3[{{} ..}, out__] := {{out}}


Example:

Sort @ f3 @ Gather @ {1, 2, 3, 2, 3, 2} === Sort @ Permutations @ {1, 2, 3, 2, 3, 2}

True


f3 is not nearly as efficient as perms however,

x = {1, 1, 1, 1, 2, 2, 3, 4, 4, 5};

perms[x]       // Length // RepeatedTiming
f3[Gather @ x] // Length // RepeatedTiming

{0.131, 37800}

{1.03, 37800}


Perhaps not quite as direct:

Clear[pnreptwice]
pnreptwice[list_List, {n_}] :=
Module[{tally},
tally = SortBy[First]@Tally[list];
DeleteDuplicates@Select[Tuples[list, n], SortBy[First]@Tally[#] == tally &]
]

pnreptwice[{a, b, c, c}, {4}] == Permutations[{a, b, c, c}, {4}]
(* Out: True *)


Using Counts with Select and KeySort is one possibility, albeit a clunky one.

Select[Tuples[{a, b, c}, 4],
KeySort@Counts@# == <|a -> 1, b -> 1, c -> 2|> &] === Permutations[{a, b, c, c}]
(* True *)