21
$\begingroup$

I have some list

{1,2,3}

How do I generate nested pairs such that I get

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

That is, I'd like a way to generate upper triangular indices.

Bonus: a way to deal with the related problem of generating lower triangular indices as well.

$\endgroup$
25
$\begingroup$

The solution is straightforward: Subsets, specifically

Subsets[{1,2,3}, {2}]

gives

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

To generate the lower indices, just Reverse them

Reverse /@ Subsets[{1,2,3}, {2}]

which gives

{{2, 1}, {3, 1}, {3, 2}}
$\endgroup$
14
$\begingroup$

Just for the sake of functional programming here is a solution which is neither in speed nor memory comparable to Subsets but which only uses basic list operations and pattern matching:

makePairs[{e_, es__}] := Join[{e, #} & /@ {es}, makePairs[{es}]];
makePairs[{e_}] := {};

It grabs the first element of the list and makes pairs with the other elements. Then it calls itself with the list where the first element is removed and joins all results when the recursion finishes.

In[37]:= makePairs[{1, 2, 3}]

(*
  Out[37]= {{1, 2}, {1, 3}, {2, 3}}
*)

Your bonus question can be implemented by simply reversing {e,#} and changing the order of the arguments to Join.

$\endgroup$
7
$\begingroup$

Combinations in combinatorics have a special meaning. Accordingly, you can calculate the combinations for more dimensions. Note that these always contain the indices of diagonal elements. See threads on StackOverflow here (combinations) and here (combinations with repetition).

This solution is the function version of the answer provided by Yaroslav Bulatov (link above):

Combinations[elem_List] := Combinations[elem, All];
Combinations[elem_List, All | Full] := Combinations[elem, Length@Union@elem];
Combinations[elem_List, n_Integer] := Module[{coef2vars, coefs, set},
   set = Union@elem;
   coef2vars[list_] := Join @@ (MapIndexed[Table[set[[First@#2]], {#1}] &, list]);
   coefs = Flatten[Permutations /@ IntegerPartitions[n, {Length@set}, Range[0, n]], 1];
   Sort@(coef2vars /@ coefs)
   ];

Combinations[{1, 2, 3, 4}, 3]
{{1, 1, 1}, {1, 1, 2}, {1, 1, 3}, {1, 1, 4}, {1, 2, 2}, {1, 2, 3}, {1,
   2, 4}, {1, 3, 3}, {1, 3, 4}, {1, 4, 4}, {2, 2, 2}, {2, 2, 3}, {2, 
  2, 4}, {2, 3, 3}, {2, 3, 4}, {2, 4, 4}, {3, 3, 3}, {3, 3, 4}, {3, 4,
   4}, {4, 4, 4}}
$\endgroup$
6
$\begingroup$

Could do this procedurally by constructing iterator lists.

indices[n_, max_] := Module[
  {jj = Array[j, n], starts, ends},
  starts = Prepend[Most[jj] + 1, 1];
  ends = max - Range[n - 1, 0, -1];
  Flatten[
   Table[jj, Evaluate[Sequence @@ Transpose[{jj, starts, ends}]]], 
   n - 1]
  ]

Example:

In[28]:= indices[4, 6]

Out[28]= {{1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 3, 6}, {1, 2, 4, 5}, {1, 
  2, 4, 6}, {1, 2, 5, 6}, {1, 3, 4, 5}, {1, 3, 4, 6}, {1, 3, 5, 
  6}, {1, 4, 5, 6}, {2, 3, 4, 5}, {2, 3, 4, 6}, {2, 3, 5, 6}, {2, 4, 
  5, 6}, {3, 4, 5, 6}}

It should be straightforward to modify this to handle the lower triangular case.

$\endgroup$
1
$\begingroup$

A fast implementation of combinations_with_replacement:

combinWithRep[list_List, k_Integer] :=
  Block[{F, it, cf},
   F = Symbol["" <> ToString /@ {##}] &;
   it = Table[{F[x, i], If[i == 1, 1, F[x, i - 1]], Length@list}, {i, 
      k}];
   cf = Hold@Block[{bag = Internal`Bag@Rest@{0}},
         Do[Internal`StuffBag[bag, #1, 1], ##2];
         bag~Internal`BagPart~All] &[First /@ it, Sequence @@ it] /. 
     Hold[x_] :> Compile[{}, x];
   Part[list, cf[]]~Partition~k];

combinWithRep[{1, 2, 3}, 3]

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

combinWithRep[Range@10, 10] // Hash // AbsoluteTiming

{0.049003, 900505471}

For comparison, @István Zachar's Combinations[Range@10, 10] // Hash // AbsoluteTiming returns

{4.617264, 900505471}

$\endgroup$
1
$\begingroup$
ClearAll[upperTriangularIndices, lowerTriangularIndices]
upperTriangularIndices = UpperTriangularize[
     SparseArray[ConstantArray[1, {#, #}]], 1]@"NonzeroPositions" &;
lowerTriangularIndices = LowerTriangularize[
     SparseArray[ConstantArray[1, {#, #}]], -1]@"NonzeroPositions" &;

upperTriangularIndices@4

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

lowerTriangularIndices@4

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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