6
$\begingroup$

Suppose we have a tensor product basis, say of dimensions lengths={2,3,2}. Every element in such basis can be represented as a triplet of numbers $(i,j,k)$ with $i=1,2$, $j=1,2,3$, and $k=1,2$. The natural way to enumerate all the elements in such basis using a single index is doing a mapping like the following:

1  -> (1, 1, 1),
2  -> (1, 1, 2),
3  -> (1, 2, 1),
4  -> (1, 2, 2),
5  -> (1, 3, 1),
6  -> (1, 3, 2),
7  -> (2, 1, 1),
8  -> (2, 1, 2),
9  -> (2, 2, 1),
10 -> (2, 2, 2),
11 -> (2, 3, 1),
12 -> (2, 3, 2)

My question is: how can we implement such a mapping in Mathematica (for arbitrary dimensions of the basis)?

Two solutions I found for this are the following:

indexToTensorIndices[idx_Integer, lengths_] := Table[
  Mod[idx, Times @@ lengths[[k ;;]], 1] / Apply[
     Times,
     lengths[[k + 1 ;;]]
    ] // Ceiling,
    {k, Length@lengths}
  ]

and

indexToTensorIndices2[idx_Integer, lengths_] := Position[#, idx] &[
   ArrayReshape[Range[Times @@ lengths], lengths]
   ] // First

which do both produce the intended result:

enter image description here

However, I find these methods kind of unsatisfactory: the first one is rather convoluted and not that easy to read, while the second one is slow for larger bases as it computes the mapping of all possible numbers while we may be interested in only a single one.

Is there a better, cleaner way to solve this problem?

Improve this question
$\endgroup$
2
  • $\begingroup$ Flatten[Outer[List, {1, 2}, {1, 2, 3}, {1, 2}], 2]? $\endgroup$
    – Basheer Algohi
    Commented Sep 2, 2016 at 4:02
  • $\begingroup$ @Algohi that is basically the same as yarchik's one $\endgroup$
    – glS
    Commented Sep 2, 2016 at 8:32

4 Answers 4

Reset to default
4
$\begingroup$

An alternative is to use MixedRadix computations, where the radices are the array dimensions, and taking care of displacements to start at 1 instead of 0. This allows handling one index at a time.

In[1]:= radices = MixedRadix[{2, 3, 2}];

In[2]:= PadLeft[IntegerDigits[#, radices], 3] & /@ Range[0, 11] + 1
Out[2]= {{1, 1, 1}, {1, 1, 2}, {1, 2, 1}, {1, 2, 2}, {1, 3, 1}, {1, 3, 2}, {2, 1, 1}, {2, 1, 2}, {2, 2, 1}, {2, 2, 2}, {2, 3, 1}, {2, 3,2}}

In[3]:= FromDigits[# - 1, radices] + 1 & /@ %
Out[3]= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
Improve this answer
$\endgroup$
1
  • $\begingroup$ This is basically the answer I was looking for. Interestingly, looking into the implementation of MixedRadix using GeneralUtilities`PrintDefinitions reveals that the core of the job is done by SymbolicTensors`UtilitiesDump`numberDecompose, that as much as I understand it basically implements the same logic found in JasonB's answer (in a slightly more procedural style) $\endgroup$
    – glS
    Commented Sep 2, 2016 at 17:21
2
$\begingroup$

Your first method seems fine to me. I came up with this without noticing it is similar to yours, 

indexToTensorIndices[idx_Integer, lengths_] := 
 Join[1 + Quotient[idx, #] & /@ (Reverse@
     FoldList[Times, Most@Reverse@lengths]), {Mod[idx, Last@lengths]}]

On extremely large lists of indices it is a bit faster than yours, but yours is pretty fast also.

Improve this answer
$\endgroup$
2
$\begingroup$

You could use TuplesFunction from my answer to Lazy form of Tuples/Outer to loop over list of lists. I won't bother to repeat the definition here as it is a bit long. For the OP example:

tf = TuplesFunction[{Range[2], Range[3], Range[2]}];

tf[Range[12]]

{{1, 1, 1}, {1, 1, 2}, {1, 2, 1}, {1, 2, 2}, {1, 3, 1}, {1, 3, 2}, {2, 1, 1}, {2, 1, 2}, {2, 2, 1}, {2, 2, 2}, {2, 3, 1}, {2, 3, 2}}

Here is a timing comparison of TuplesFunction with the OP solution:

r1 = indexToTensorIndices[#, {1000, 2000, 3000}]& /@ Range[10^6+1, 10^6+1000]; //RepeatedTiming

tf = TuplesFunction[{Range[1000], Range[2000], Range[3000]}];
r2 = tf[10^6+1 ;; 10^6+1000]; //RepeatedTiming

r1 === r2

{0.013, Null}

{0.0001, Null}

True

Quite a bit faster.

Improve this answer
$\endgroup$
1
$\begingroup$ 
ind=Flatten[Array[List, {2, 3, 2}], 2]

yields as expected

{{1,1,1}, {1,1,2}, {1,2,1}, {1,2,2}, {1,3,1}, {1,3,2}, {2,1,1}, {2,1,2}, {2,2,1}, {2,2,2}, {2,3,1}, {2,3,2}}

One can of course make a general function for that. For practical applications I recommend creating the list first and then using it as a function, i.e., ind[[i]].

Improve this answer
$\endgroup$
4
  • $\begingroup$ well this is certainly an improved version of my second proposed method (hadn't though about the super simple Array!), but it bares the same problem: it computes the whole mapping while I may be only interested in a single one. For example, I want to be able to obtain 9 -> {2, 2, 1} without having to compute the indices corresponding to all the other values. $\endgroup$
    – glS
    Commented Sep 1, 2016 at 19:06
  • $\begingroup$ @glS you can certainly derive a formula that gives exactly the requested string of indices. But why bother? You can precompute the whole array and later just use it. It is the fastest way. $\endgroup$
    – yarchik
    Commented Sep 1, 2016 at 19:08
  • $\begingroup$ well, I guess that depends on the application. But if for example one requires to compute the mapping of a number in a basis like {1000,1000,1000}, your method will become extremely expansive (and likely hang the machine for at least a few seconds), while my first proposed method will give the solution on the spot. I'm just curious to know if there are other nice approaches to this problem that I didn't think of. $\endgroup$
    – glS
    Commented Sep 1, 2016 at 19:17
  • $\begingroup$ @glS I see, that is possible. In this case you may be interested in FindInstance command. $\endgroup$
    – yarchik
    Commented Sep 1, 2016 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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