Forums > MaxMSP

Math terminology question… Non redundant ordered pairs in a list.


Sep 18 2010 | 1:26 pm

I’m trying to mathematically produce non redundant, sequential pairs in a list, so if the number is 2 it outputs the list: 1 2 (it would NOT output 1 1 1 2 2 1 2 2). If the incoming number is 3 it outputs: 1 2 1 3 2 3. If 4 output 1 2 1 3 1 4 2 3 2 4 3 4. See the pattern? I need to be able to do this to an incoming number of 52. For prototyping I’ve just been using coll and did the first 8 or so manually.

I just don’t know enough math to understand what this is called, specifically so I can recognize the correct formula. I can build the external (or perhaps there’s one or two objects that do the same), no problem. I’m just stuck on the math.

Thanks, would really appreciate any help.

Sep 18 2010 | 2:15 pm

try this

-- Pasted Max Patch, click to expand. --

edit: btw if there's an easier way to do this I'd like to know...

Sep 18 2010 | 4:07 pm

Think you are on the right track, still wish I knew what this was called and how to express it mathmatically.

Thanks for the suggestion! It’s quite the contraption! :)

Sep 18 2010 | 5:35 pm

I am not sure there is a mathematical name for that kind of sequence, but I guess you could describe it as a subsequence of the natural numbers interleaved with its lowest element or something like that.

Here is a js version:

seq = function (start, n) {
  if (start >= n)
    return [];
  var i, res = [];
  for (i = start + 1; i < = n; i++) {
    res.push(start);
    res.push(i);
  }
  return res.concat(seq(start + 1, n));
}
Sep 19 2010 | 12:09 am

hey, those are great… interesting stuff!

Sep 19 2010 | 6:53 pm

You don’t say what you want to do with the result, but that might influence how you manage the result. For example, the number 52 results in 1,326 possible unique pairings (i.e. 2,652 numbers), which makes it impractical to output the result in Max as a single list (as you described in your question). You’d probably want to store the result in a Jitter matrix (or a coll, as Terry did).

Sep 20 2010 | 11:52 am

Yep, it becomes pretty big fast. That’s the wonder of exponential growth ;).

Sep 20 2010 | 12:02 pm

the number of pairs will be n*(n-1)/2, given a maximum n and combining from 1 to n
I think they’re called combinations as (distinct from permutations)
and that’s as far as my maths knowledge allows me to go

and as Hans has eloquently illustrated, much easier to do in a text-based language rather than in max

Sep 28 2010 | 1:34 am

Hmmm… Might have to start rethinking my approach. I knew the order was close to 1000 pairs, but you are right that would be impractical.

You know, I really need to read up on this more. I’m doing 2D collision detection between objects, with 52 possible objects on screen at any point. I was using a "good enough" approach for up to 8 possible collisions but trying to go higher is just proving a headache.

Perhaps I need to find a more efficient approach to this and code it in an external.

Viewing 9 posts - 1 through 9 (of 9 total)

Forums > MaxMSP