# Tuples with one "joker" digit? [duplicate]

I'd like to create an array of all possible length 11 combinations of 1, 2, and the number 3, BUT with the number 3 only appearing zero or once in each combination.

I tried:

Tuples[{{1, 2}, {3}}, 11]


But that didn't give me anything close to what I wanted.

• Related, possible duplicate: (5036) Commented Jul 11, 2016 at 16:51

The numbers of all 11-tuples of 1,2,3 is not too big so another solution is to simply generate them all and filter them at having at most one 3:

Select[Tuples[{1, 2, 3}, 11], Count[#, 3] <= 1 &]


This takes less than a second on my computer.

However beware of the exponential grow in the tuple length. At 11, this counts as a "quick and dirty" solution, "just" gravely suboptimal. Add a couple more terms and it may become unsustainable.

The right way is always a question of what you are optimizing to. In my case that was input complexity. I doubt you can find an equivalent command that is shorter or more transparent for a reader.

• It should be noted that this numbers grows a lot more quickly though if you want to use for longer tuples. At length 20, you're generating 3 billion tuples and keep only 11 million of them. (For the OPs case of 11, it's 13k out of 177k.) Commented Mar 4, 2016 at 13:48
• @MartinBüttner Thanks! Edited answer to make this clear, and to justify my proposition in this particular case. Commented Mar 4, 2016 at 13:53
• Looks good. +1 for simplicity. :) Commented Mar 4, 2016 at 13:54

Permutations can do this. You just need to give it enough copies of 1 and 2 such that they can appear arbitrarily often (i.e. n times, where n is the length of your tuples), but only one 3:

With[{n = 3},
Permutations[Flatten@{ConstantArray[{1, 2}, n], 3}, {n}]
]
(* {{1, 2, 1}, {1, 2, 2}, {1, 2, 3}, {1, 1, 2}, {1, 1, 1}, {1, 1, 3},
{1, 3, 2}, {1, 3, 1}, {2, 1, 1}, {2, 1, 2}, {2, 1, 3}, {2, 2, 1},
{2, 2, 2}, {2, 2, 3}, {2, 3, 1}, {2, 3, 2}, {3, 1, 2}, {3, 1, 1},
{3, 2, 1}, {3, 2, 2}} *)


If you want them sorted it's sufficient to sort the list of available numbers (so you don't have to sort the potentially massive list of tuples later):

With[{n = 3},
Permutations[Sort@Flatten@{ConstantArray[{1, 2}, n], 3}, {n}]
]

(* {{1, 1, 1}, {1, 1, 2}, {1, 1, 3}, {1, 2, 1}, {1, 2, 2}, {1, 2, 3},
{1, 3, 1}, {1, 3, 2}, {2, 1, 1}, {2, 1, 2}, {2, 1, 3}, {2, 2, 1},
{2, 2, 2}, {2, 2, 3}, {2, 3, 1}, {2, 3, 2}, {3, 1, 1}, {3, 1, 2},
{3, 2, 1}, {3, 2, 2}} *)


Also, as a sanity check:

With[{n = 11},
Print@Length@Permutations[Flatten@{ConstantArray[{1, 2}, n], 3}, {n}];
Print[2^n + 2^(n - 1)*n]
]
(* 13312
13312 *)


There are lots of ways, probably. Here's one (with n==3 rather than n==11 for display purposes):

With[{n = 3},
Join[Tuples[{1, 2}, n], Flatten[ReplaceList[#, {a___, b___} :> {a, 3, b}] & /@ Tuples[{1, 2}, n - 1], 1]]
]
(* {{1, 1, 1}, {1, 1, 2}, {1, 2, 1}, {1, 2, 2}, {2, 1, 1}, {2, 1, 2}, {2, 2, 1}, {2, 2, 2},
{3, 1, 1}, {1, 3, 1}, {1, 1, 3}, {3, 1, 2}, {1, 3, 2}, {1, 2, 3},
{3, 2, 1}, {2, 3, 1}, {2, 1, 3}, {3, 2, 2}, {2, 3,2}, {2, 2, 3}} *)

DeleteCases[Tuples[{1, 2, 3}, 3], {___, 3, ___, 3, ___}]