6
$\begingroup$
  • 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!

Improve this question
$\endgroup$
2
  • $\begingroup$ Select[Tuples[{{a, b, c, d}, {a, b, c, d}, {a, b, c, d}, {a, b, c, d}}], DuplicateFreeQ] /. d -> c $\endgroup$ Commented Feb 7, 2017 at 18:30
  • $\begingroup$ x = {a, b, c, c}; DeleteDuplicates@Select[Tuples[{x, x, x, x}], Sort[#] == Sort[x] &] $\endgroup$ Commented Feb 7, 2017 at 21:57

3 Answers 3

Reset to default
6
$\begingroup$

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}
Improve this answer
$\endgroup$
1
$\begingroup$

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 *)
Improve this answer
$\endgroup$
0
$\begingroup$

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 *)
Improve this answer
$\endgroup$