# How to arrange a list on a triangular pattern?

I've made a multiplication table with this:

Then I removed the repeated permutations with:

gg = Range[1, 10]; Subsets[gg, {2}] // TableForm


Now, when the multiplication table has the repeated permutations removed, this table is now similar to a triangle:

(1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (1,8) (1,9) (1,10) - 10 multiplications

(2,3) (2,4) (2,5) (2,6) (2,7) (2,8) (2,9) (2,10) - 9 multiplications

...

(9,10) - 1 multiplication

How can I build a triangular table based on this? I'm trying to use arithmetical progression precedure like:

gg = Range[1, 10]; x = 1; gb = {};
While[x <= 9, AppendTo[gb, Take[Subsets[gg, {2}], {H, J}]]; x++]


I was thinking on doing

gg = Range[1, 10]; x = 1; gb = {};
H=0;J=0;
While[x <= 9, AppendTo[gb, Take[Subsets[gg, {2}], {H=H+1, J=J-1}]]; x++]


You can create your triangular table in a far simpler manner as follows:

Table[{i, j}, {i, 10}, {j, i + 1, 10}]
(* {
{{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}, {1, 9}, {1, 10}},
{{2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 7}, {2, 8}, {2, 9}, {2, 10}},
{{3, 4}, {3, 5}, {3, 6}, {3, 7}, {3, 8}, {3, 9}, {3, 10}},
{{4, 5}, {4, 6}, {4, 7}, {4, 8}, {4, 9}, {4, 10}},
{{5, 6}, {5, 7}, {5, 8}, {5, 9}, {5, 10}},
{{6, 7}, {6, 8}, {6, 9}, {6, 10}},
{{7, 8}, {7, 9}, {7, 10}},
{{8, 9}, {8, 10}},
{{9, 10}}
} *)


If this was just a simple example and your real application requires you to partition some arbitrary list of length $N(N+1)/2$ into a triangular list with sublists of length $\{N, N-1, ..., 1\}$, then you can use Mr.Wizard's dynP from here:

dynP[Subsets[gg, {2}], Range[9, 1, -1]] // TableForm


I think R.M covered your actual application, but here is some tangential thinking that may interest you or someone who finds this question.

n = 10;

UpperTriangularize@Array[Times, {n, n}]


$\begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 0 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 \\ 0 & 0 & 9 & 12 & 15 & 18 & 21 & 24 & 27 & 30 \\ 0 & 0 & 0 & 16 & 20 & 24 & 28 & 32 & 36 & 40 \\ 0 & 0 & 0 & 0 & 25 & 30 & 35 & 40 & 45 & 50 \\ 0 & 0 & 0 & 0 & 0 & 36 & 42 & 48 & 54 & 60 \\ 0 & 0 & 0 & 0 & 0 & 0 & 49 & 56 & 63 & 70 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 64 & 72 & 80 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 81 & 90 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 100 \end{array}$

(i = 1; NestList[Rest@# + Range[++i, n] &, Range@n, n - 1])


$\begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 \\ & & 9 & 12 & 15 & 18 & 21 & 24 & 27 & 30 \\ & & & 16 & 20 & 24 & 28 & 32 & 36 & 40 \\ & & & & 25 & 30 & 35 & 40 & 45 & 50 \\ & & & & & 36 & 42 & 48 & 54 & 60 \\ & & & & & & 49 & 56 & 63 & 70 \\ & & & & & & & 64 & 72 & 80 \\ & & & & & & & & 81 & 90 \\ & & & & & & & & & 100 \end{array}$

Table[i j, {i, n}, {j, i, n}]


$\begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 \\ & & 9 & 12 & 15 & 18 & 21 & 24 & 27 & 30 \\ & & & 16 & 20 & 24 & 28 & 32 & 36 & 40 \\ & & & & 25 & 30 & 35 & 40 & 45 & 50 \\ & & & & & 36 & 42 & 48 & 54 & 60 \\ & & & & & & 49 & 56 & 63 & 70 \\ & & & & & & & 64 & 72 & 80 \\ & & & & & & & & 81 & 90 \\ & & & & & & & & & 100 \end{array}$

n = 5000;

UpperTriangularize@Array[Times, {n, n}]; // Timing

(i = 1; NestList[Rest@# + Range[++i, n] &, Range@n, n - 1]); // Timing

Table[i j, {i, n}, {j, i, n}]; // Timing


{0.047, Null}

{0.047, Null}

{3.12, Null}

n = 5000;
UpperTriangularize@Array[Times, {n, n}];
MaxMemoryUsed[]
Quit[]


214923080

n = 5000;
(i = 1; NestList[Rest@# + Range[++i, n] &, Range@n, n - 1]);
MaxMemoryUsed[]
Quit[]


65867144

n = 5000;
Table[i j, {i, n}, {j, i, n}];
MaxMemoryUsed[]
Quit[]


315167560

• Yes. Your answer is also very useful. Aug 27, 2012 at 19:44