Convert a list of list of numbers into a matrix of 1s and 0s

Question

I want to take a list of list of integers and convert them to a matrix of 0s and 1s where an element of the matrix is 1 if "the row is in the column". The row corresponds to an integer in the list and should be ordered from 0 to the largest integer in the lists with no skips (i.e. there may be a row of zeroes). The columns corresponds to the inner lists and should be ordered in the order they appear in the list.

Is there a more efficient way to do this for large lists other than doing as I have done below? I want the function to handle ~100 integers, and ~20 inner lists, but the function may run hundreds of thousands of time as part of an optimisation routine, so an obvious time saving would be useful.

Example code:

MakeMatrix[ll_] := 
 Block[{mat = Table[0, Max[Flatten[ll]] + 1, Length[ll]]}, 
  Do[Do[mat[[row + 1, col]] = 1, {row, ll[[col]]}], {col, 1, 
    Length[ll]}]; Return[mat]]
MakeMatrix[{{0}, {0, 1}, {0, 1, 2}}]
MakeMatrix[{{0, 2}, {1, 2, 4}, {0, 1}}]

so the input:

{{0}, {0, 1}, {0, 1, 2}}

gives output:

{{1, 1, 1}, {0, 1, 1}, {0, 0, 1}}

And the input:

{{0, 2}, {1, 2, 4}, {0, 1}}

give output:

{{1, 0, 1}, {0, 1, 1}, {1, 1, 0}, {0, 0, 0}, {0, 1, 0}}

Answer 1

ClearAll[makeMatrix]
makeMatrix = SparseArray[Join @@ MapIndexed[Thread[{#, #2[[1]]}] &, 1 + #] -> 1] &;

or, slightly faster for large inputs,

ClearAll[makeMatrix2]
makeMatrix2 = SparseArray[Join @@ Thread /@ Transpose[{1 + #, Range@Length@#}] -> 1] &

Examples:

l1 = {{0}, {0, 1}, {0, 1, 2}};
makeMatrix[l1] 

Normal @ makeMatrix[l1]

{{1, 1, 1}, {0, 1, 1}, {0, 0, 1}}

l2 = {{0, 2}, {1, 2, 4}, {0, 1}};
makeMatrix[l2] 

Normal @ makeMatrix[l2] 

{{1, 0, 1}, {0, 1, 1}, {1, 1, 0}, {0, 0, 0}, {0, 1, 0}}

Answer 2

You are using zero-based indexes, so including that transformation:

construct[xxs_] := With[{row = ConstantArray[0, 1 + Max@xxs]},
  Transpose[ReplacePart[row, Transpose[{# + 1}] -> 1] & /@ xxs]
  ]

Answer 3

Using your definitions:

input1 = {{0}, {0, 1}, {0, 1, 2}};
input2 = {{0, 2}, {1, 2, 4}, {0, 1}};

here is a test function to construct your output matrices:

ClearAll[test]
test[input_] :=
 Table[
   MemberQ[list, candidate],
   {candidate, Range[0, Max@input]}, {list, input}
 ] /. {True -> 1, False -> 0}

And the results:

test[input1]

{{1, 1, 1}, {0, 1, 1}, {0, 0, 1}}

test[input2]

{{1, 0, 1}, {0, 1, 1}, {1, 1, 0}, {0, 0, 0}, {0, 1, 0}}

Answer 4

The fastest way might be to convert your code to a compilable one. The main trick is to pad your input into a rectangular array and also to pass the lengths of the lists.

mmc = Compile[{{llpad, _Integer, 2}, {lengths, _Integer, 1}},
   Block[{mat = Table[0, {Max[llpad] + 1}, {Length[lengths]}]},
    Do[
     mat[[row + 1, col]] = 1,
     {col, 1, Length[lengths]},
     {row, Take[Compile`GetElement[llpad, col], 
                Compile`GetElement[lengths, col]]}];
    Return[mat]],
   CompilationTarget -> "C", RuntimeOptions -> "Speed"
   ];
makeMatrix[ll_] := mmc[PadRight[ll], Length /@ ll];

makeMatrix[{{0}, {0, 1}, {0, 1, 2}}]
makeMatrix[{{0, 2}, {1, 2, 4}, {0, 1}}]
(*
  {{1, 1, 1}, {0, 1, 1}, {0, 0, 1}}
  {{1, 0, 1}, {0, 1, 1}, {1, 1, 0}, {0, 0, 0}, {0, 1, 0}}
*)