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!

$\endgroup$
  • $\begingroup$ Select[Tuples[{{a, b, c, d}, {a, b, c, d}, {a, b, c, d}, {a, b, c, d}}], DuplicateFreeQ] /. d -> c $\endgroup$ – Feyre Feb 7 '17 at 18:30
  • $\begingroup$ @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. $\endgroup$ – TeM Feb 7 '17 at 18:38
  • $\begingroup$ x = {a, b, c, c}; DeleteDuplicates@Select[Tuples[{x, x, x, x}], Sort[#] == Sort[x] &] $\endgroup$ – Simon Woods Feb 7 '17 at 21:57
5
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.