8
$\begingroup$

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.

$\endgroup$

marked as duplicate by Mr.Wizard list-manipulation Jul 17 '17 at 7:16

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Related, possible duplicate: (5036) $\endgroup$ – Mr.Wizard Jul 11 '16 at 16:51
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Martin Ender Mar 4 '16 at 13:48
  • $\begingroup$ @MartinBüttner Thanks! Edited answer to make this clear, and to justify my proposition in this particular case. $\endgroup$ – The Vee Mar 4 '16 at 13:53
  • $\begingroup$ Looks good. +1 for simplicity. :) $\endgroup$ – Martin Ender Mar 4 '16 at 13:54
12
$\begingroup$

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 *)
$\endgroup$
6
$\begingroup$

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}} *)
$\endgroup$
0
$\begingroup$
DeleteCases[Tuples[{1, 2, 3}, 3], {___, 3, ___, 3, ___}]
$\endgroup$

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