4
$\begingroup$

What is the correct (optimal) way of generating all possible ordered k-tuples of digits from 0 to 9 in which no elements repeat and the first element is nonzero?

My current code

k=3; Digs = Select[Tuples[Prepend[Table[Range[0, 9], k - 1], Range[1, 9]]], CountDistinct[#] == k &]

works only for small k but then runs out of memory because it generates too many unnecessary tuples.

I found a related answer here which provides a uniqueTuples function but it only works for a pair of lists and not for an arbitrary number of lists. Can that be generalized to an arbitrary number of lists somehow in a way to avoid the Select applied to a huge wasteful set?

In the special case k=10 it should just return the permutations of Range[0, 9] excluding those that start with 0, which is still a manageable number.

Improve this question
$\endgroup$
2
  • $\begingroup$ I think you mean "ordered", as in "ordering matters". $\endgroup$ Commented Dec 12, 2024 at 18:54
  • $\begingroup$ Indeed. I meant that the digits can appear in any order, but now I see the ambiguity. $\endgroup$ Commented Dec 12, 2024 at 18:57

3 Answers 3

Reset to default
4
$\begingroup$ 
func[n_] := Module[{r = Range[0, 9]}, Sort[Join @@ (Permutations /@ Subsets[r, {n}])][[FactorialPower[9, n - 1] + 1 ;;]]] Grid[{#, Length[func[#]]} & /@ Range[2, 10], Frame -> All, Alignment -> Right] ListPlot[Table[{j, AbsoluteTiming[func[j]][[1]]}, {j, 10}], Frame -> True, FrameLabel -> {"Input", "Absolute Timing (s)"}]

enter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ Huh, very clever to sort those zeros. $\endgroup$ Commented Dec 14, 2024 at 19:40
6
$\begingroup$

Subsets instead of Tuples:

k = 3; uTs = Delete[ f = Flatten[ Permutations/@ Subsets[{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, {k}], 1], Position[f[[All, 1]], 0]]

Works for all k up to 10.

Improve this answer
$\endgroup$
3
$\begingroup$

Instead you can check an integer with these characteristics and convert to a tuple using IntegerDigits, if required.

validQ[n_ /; n \[Element] PositiveIntegers, k_ /; k \[Element] PositiveIntegers] := If[ContainsOnly[DigitCount[n, 10], {0, 1}] && IntegerPart[RealExponent[n]] > k - 2, True, False]

Usage:

Table[Select[Range[10^(k - 1), 10^k - 1], validQ[#, k] &], {k, 2, 4}]

This will suffer from memory allocation failure at k=10 but you can rephrase your problem so this generation of tuples is not required in the first place. Each of these tuples represents an integer and there is no need to ever store integers.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.