Duplicate Permutations with Tuples

Question

• 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!

Answer 1

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:

• Shuffle product of two lists

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}

Answer 2

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 *)

Answer 3

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 *)