4
$\begingroup$

My title is probably worded horribly, let me explain what I mean. So I essentially have a list of lists, and I want to go through and mark which list indices have a certain property. This is how I have it written out:

For[j = 1, j <= Length[list], j++,
 For[k = j + 1, k <= Length[list], k++,
  If[list[[j]][[1]] < list[[k]][[1]] && 
  list[[j]][[2]] < list[[k]][[2]] && 
  list[[j]][[2]] > list[[k]][[1]], Append[bad, j]]]]

"bad" is supposed to be an empty list, which afterwards will have a list of the indices I care about. However, after I run this function, "bad" is still an empty list. It works fine if instead of appending, I simply print the indices j, k. Is there a reason for this?

Maybe I should also mention this is what a typical "list" looks like:

list = {{1, 2}, {3, 5}, {4, 6}}
$\endgroup$
  • 1
    $\begingroup$ The simple answer is that Append does not rewrite bad; you need AppendTo. But I will follow up with a longer answer (in a couple of hours when it's lunchtime) to suggest a better approach than the loop-and-append approach. Are you by chance a new Mathematica user coming from Matlab or Fortran? I've noticed that people coming from those languages tend to use that approach a lot. $\endgroup$ – Verbeia Oct 1 '15 at 0:06
  • $\begingroup$ Could you express the criterion to select the "bad" components in words? And possibly provide a longer input sample, and the corresponding output you expect? As @Verbeia mentioned, AppendTo instead of Append is a quick fix, however there are certainly better ways than loops and AppendTo, but I have a hard time deciding exactly what your program is intended to do. Consider also that e.g. list[[j]] [[1]] can always be written as list[[j,1]], which appears more readable. $\endgroup$ – MarcoB Oct 1 '15 at 0:44
  • $\begingroup$ Also consider the possibility of returning elements instead of indices. Mathematica functions are prone to do that. $\endgroup$ – Dr. belisarius Oct 1 '15 at 0:49
  • $\begingroup$ How big are the lists you're planning to run this against? Is speed important? Your code will be slow, but will handle long lists, the only answer so far will be slow, and will blow chunks on long lists (you'll chew up RAM). Other than mistakenly using Append when you should use AppendTo (or directly update bad via Append), there's nothing intrinsically wrong with your code. $\endgroup$ – ciao Oct 1 '15 at 5:28
  • 1
    $\begingroup$ @Szabolcs I think, it's rather this answer: mathematica.stackexchange.com/a/19804/26956 $\endgroup$ – LLlAMnYP Oct 1 '15 at 12:24
7
$\begingroup$

I noted in comments that the simple answer to your question is that Append does not rewrite bad; you need AppendTo.

But here is a more "Mathematica"-like way to consider. Its main disadvantage is that it actually calculates the test for j >= k as well as j < k, and then throws away the result you don't need.

Position[UpperTriangularize[
  Outer[(#1[[1]] < #2[[1]] && #1[[2]] < #2[[2]] && #1[[2]] > #2[[
        1]]) &, list, list, 1], 1], True, {2}]

(*  {{1, 2}, {2, 3}}  *)

Some things to note about this solution:

  • I have used the optional fourth argument of Outer to get Mathematica to see list as a vector of elements (that just happen to be lists) rather than treating it as a matrix. The result of the Outer function is a matrix of True and False values.

  • I then zero out the ones we don't need using UpperTriangularize, including its second argument, which makes sure the lead diagonal is also zeros.

  • Finally, I extract the indices (your j and k) for which the value is True using Position. Again note that I've used an option (third) argument to tell Mathematica at what level of the list I should be looking for the True values.

I'm sure there are other solutions that other members could provide.


Follow-up

I suspect the Outer construct is the one you are having trouble understanding, so here are some examples to build up to the version I used.

list=Range[5];

Outer[(#1<#2)&,list,list]//TableForm

False   True    True    True    True
False   False   True    True    True
False   False   False   True    True
False   False   False   False   True
False   False   False   False   False

Now try a matrix

list2=RandomInteger[{0,10},{5,2}]
(*{{8,8},{2,0},{5,0},{3,4},{10,6}} *)

Here's an example using the fourth argument of Outer, to show how it knits together each row, not each element, to create a n-by-n matrix, where n is the length of list2.

Outer[(#1[[1]]<#2[[2]])&,list2,list2,1]//TableForm
False   False   False   False   False
True    False   False   True    True
True    False   False   False   True
True    False   False   True    True
False   False   False   False   False

If I just removed that fourth argument, the command above would record an error because it would then be working on the lowest-level elements of the list list2. So instead I would need to write the following.

Outer[(#1<#2)&,list2,list2]
{{{{False,False},{False,False},{False,False},{False,False},{True,False}},
 {{False,False},{False,False},{False,False},{False,False},{True,False}}},
 {{{True,True},{False,False},{True,False},{True,True},{True,True}},
 {{True,True},{True,False},{True,False},{True,True},{True,True}}},
 {{{True,True},{False,False},{False,False},{False,False},{True,True}},
 {{True,True},{True,False},{True,False},{True,True},{True,True}}}, 
 {{{True,True},{False,False},{True,False},{False,True},{True,True}}, 
 {{True,True},{False,False},{True,False},{False,False},{True,True}}}, 
 {{{False,False},{False,False},{False,False},{False,False},{False,False}}, 
 {{True,True},{False,False},{False,False},{False,False},{True,False}}}}

The result in that case is a tensor with Dimensions {5, 2, 5, 2}.

$\endgroup$
  • $\begingroup$ To answer your question, yeah I'm a new Mathematica user. I haven't really used a math-based programming language before, just Python and C++. To be honest I really don't understand what's happening in this solution, but I'll look it over more and see if I can figure it out $\endgroup$ – Alex Mathers Oct 1 '15 at 2:52
6
$\begingroup$

My take, assuming speed matters:

fnrO = Module[{r = Range@Length@#, lt = #, p1, c, rr,ll=Length@#},
    rr = Reap[For[j = 1, j < ll, j++,
       lt = Rest@lt;
       p1 = Pick[r[[j + 1 ;;]], BitOr @@ UnitStep[Subtract[#[[j]], Transpose@lt]], 0];
       If[p1 =!= {},c = Tr[BitXor[1, UnitStep[Subtract[lt[[p1 - j, 1]], #[[j, 2]]]]]];
        If[c =!= 0, Sow[{j, c}]]];]];
    If[rr[[2]] === {}, {}, rr[[2, 1]]]] &;

On your tiny example:

list = {{1, 2}, {3, 5}, {4, 6}};
result = fnrO@list
Join @@ ConstantArray @@@ result

{{2,1}}

{2}

I took the liberty of condensing the output into pairs, first element the index in the list, second element the count found. Using Join @@ ConstantArray @@@... on the result returns the same format as your code (i.e., repeated indices when there's more than one "hit").

Quick performance comparison against your code and existing answers (on the cigar lounge squirrel-book, so expect 5-10X faster for all on real hardware), using RandomInteger[10, {len, 2}] to generate test cases:

enter image description here

This is just a quick-n-dirty first pop, my gut tells me there's a clever bottom-up approach that s/b much faster, pondering now...

$\endgroup$
  • $\begingroup$ You're smoking too much +1 $\endgroup$ – Dr. belisarius Oct 1 '15 at 8:33
5
$\begingroup$

This seems twice as fast as your loop. I don't doubt faster solutions are out there.

list = RandomInteger[{1, 10}, {400, 2}];
f[l1_, l2_, idx_] := Catch[Scan[If[l1[[1]] < #[[1]] < l1[[2]] < #[[2]], Throw[idx]] &, 
                                l2]; Sequence @@ {}]

MapIndexed[f[#1, list[[#2[[1]] + 1 ;;]], #2[[1]]] &, list]
$\endgroup$
  • $\begingroup$ Appears to get different results from OP? His returns repeated indices for multiple "hits" (perhaps to later count or something...) $\endgroup$ – ciao Oct 1 '15 at 7:54
  • $\begingroup$ @ciao Perhaps. Posting a faster If[ ] right now $\endgroup$ – Dr. belisarius Oct 1 '15 at 8:03
  • $\begingroup$ Well, +1 in any case, clean... $\endgroup$ – ciao Oct 1 '15 at 8:28

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.