2
$\begingroup$

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}}
$\endgroup$
3
$\begingroup$
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] 

enter image description here

Normal @ makeMatrix[l1]

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

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

enter image description here

Normal @ makeMatrix[l2] 

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

$\endgroup$
2
$\begingroup$

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]
  ]
$\endgroup$
2
$\begingroup$

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}}

$\endgroup$
1
$\begingroup$

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}}
*)
$\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.