Forums > MaxMSP

sieving a list of lists…?


xaf
June 22, 2013 | 1:42 pm

hi,

i’ve built a patch that fills a coll with all possible 8 step-patterns with an equal amount of 1′s and 0′s, but now i need to sieve out the rotations. for example:
there are 8 possible patterns of 4 consecutive 0′s:
0 0 0 0 1 1 1 1
1 0 0 0 0 1 1 1
1 1 0 0 0 0 1 1
1 1 1 0 0 0 0 1
etc.

so out of those 8 patterns i only want to keep the first one and remove the other 7 from the coll. and then apply the same procedure for all patterns until i only have unique patterns left without any rotated versions.

i know that Lmatch will find the rotated versions, but what i can’t get my head around is the actual algorithm and how to implement it in max… any help would be most appreciated!

grtz,
xaf

<code>

– Pasted Max Patch, click to expand. –

</code>


June 22, 2013 | 5:20 pm

A good challenge. I would use [zl rot] and [zl compare]:

Take your first coll entry and run it through [zl rot 1], then store the rotated list in [zl compare]‘s right inlet. Then run *all* the other [coll] entries through it to compare. You need to track the indices with matching lists (if [zl compare] sends out a 1, it matches, so store that index). If you just run one [zl rot] at a time, you’ll only get one possible match…otherwise you’d need to store your matching indices in [zl group] rather than [i].

At the end of comparing your first list, use "delete" on the entry for the [coll], which will auto-renumber the higher indices. (Don’t use "delete" on the entries if you are deleting more than one at a time, because the higher indices will drop by 1 to compensate. In that case, use "remove" on all of them, then "renumber" at the end.) You can then run the first entry with [zl rot 2] etc. up through [zl rot 7] for all possible rotations of each 8-member list.

Sounds like a lot of work, but once it’s set up it’ll do it all for you ;)

Likely there are many other ways to do it as well…you might rotate the list 7 times and compare all 7 to each entry instead of going through the whole [coll] 7 times, for example.



xaf
June 23, 2013 | 3:48 am

thanks for the idea. however, i’m still not really sure how to patch it all up, so in the meantime i’ve resorted to old fashioned pen-and-paper. there were only 70 patterns so i figured it would take less time to go through them manually rather then wrecking my brain on building an algorithm… ended up with 10 unique patterns. in the unlikely case anybody is interested, here they are:
00001111
00010111
00011011
00011101
00100111
00101011
00101101
00110011
00110101
01010101

at some point in the future i’ll probably want to do the same thing with longer series, so getting this algorithm right will probably be bugging me somewhere in the back of my mind, but for now this will do ;-)


June 23, 2013 | 11:30 pm

Wrecking your brain? I thought that’s what Max was for! ;)

I put this together to try things out. It fills a [coll] with all the possible ways you can make an 8-bit list (256 total), all in order by binary number. Then you click on the "compare" button and it grabs each index and checks all the other entries and their rotations against it, and if a match is found, it’s removed. You have the option to auto-renumber at the end of the whole process. I was surprised that it only takes a split second, there’s a LOT of comparisons happening (256 x 256 x 7 = 458782, though as entries get removed, they’re skipped in future comparisons).

Anyway, see what you think. The end result says there are 32 unique patterns out of the original 256. The results aren’t totally correct because I’m missing two of the lists you provided, not sure why it’s doing that, maybe someone has some ideas on how it’s processing and where the mistake might be. Either way, it was definitely a fun challenge and might give some ideas for list generation and comparison in the future…

<code>

– Pasted Max Patch, click to expand. –

</code>


June 24, 2013 | 8:25 pm

Here ya go… I’m sure there is plenty of bloat and redundancy in my solution. But it’s clean.. and it works!

It generates exactly the same order of lists as those you worked out by hand.. so it must process the them similarly.

The way I handled it was to create a secondary coll with decimal conversions of the original lists set as the index with the indices of the original coll set as the values. That way, I was able to process the main lists, convert them to ints, use those ints to grab the index values, generate "remove $1" messages and gradually eliminate redundancy from the main coll. I did it incrementally.. calling a single list, rotating it 7 times, and removing the redundant values. Rinse, repeat. The solution is generated after processing only the first 21 of 70 lists. Pretty cool.

Enjoy..

– Pasted Max Patch, click to expand. –

June 25, 2013 | 12:10 am

bonus:

80 6:6 12-bit rotations:

0 0 0 0 0 0 1 1 1 1 1 1

0 0 0 0 0 1 0 1 1 1 1 1
0 0 0 0 0 1 1 0 1 1 1 1
0 0 0 0 0 1 1 1 0 1 1 1
0 0 0 0 0 1 1 1 1 0 1 1
0 0 0 0 0 1 1 1 1 1 0 1
0 0 0 0 1 0 0 1 1 1 1 1
0 0 0 0 1 0 1 0 1 1 1 1
0 0 0 0 1 0 1 1 0 1 1 1
0 0 0 0 1 0 1 1 1 0 1 1
0 0 0 0 1 0 1 1 1 1 0 1
0 0 0 0 1 1 0 0 1 1 1 1
0 0 0 0 1 1 0 1 0 1 1 1
0 0 0 0 1 1 0 1 1 0 1 1
0 0 0 0 1 1 0 1 1 1 0 1
0 0 0 0 1 1 1 0 0 1 1 1
0 0 0 0 1 1 1 0 1 0 1 1
0 0 0 0 1 1 1 0 1 1 0 1
0 0 0 0 1 1 1 1 0 0 1 1
0 0 0 0 1 1 1 1 0 1 0 1
0 0 0 0 1 1 1 1 1 0 0 1
0 0 0 1 0 0 0 1 1 1 1 1
0 0 0 1 0 0 1 0 1 1 1 1
0 0 0 1 0 0 1 1 0 1 1 1
0 0 0 1 0 0 1 1 1 0 1 1
0 0 0 1 0 0 1 1 1 1 0 1
0 0 0 1 0 1 0 0 1 1 1 1
0 0 0 1 0 1 0 1 0 1 1 1
0 0 0 1 0 1 0 1 1 0 1 1
0 0 0 1 0 1 0 1 1 1 0 1
0 0 0 1 0 1 1 0 0 1 1 1
0 0 0 1 0 1 1 0 1 0 1 1
0 0 0 1 0 1 1 0 1 1 0 1
0 0 0 1 0 1 1 1 0 0 1 1
0 0 0 1 0 1 1 1 0 1 0 1
0 0 0 1 0 1 1 1 1 0 0 1
0 0 0 1 1 0 0 0 1 1 1 1
0 0 0 1 1 0 0 1 0 1 1 1
0 0 0 1 1 0 0 1 1 0 1 1
0 0 0 1 1 0 0 1 1 1 0 1
0 0 0 1 1 0 1 0 0 1 1 1
0 0 0 1 1 0 1 0 1 0 1 1
0 0 0 1 1 0 1 0 1 1 0 1
0 0 0 1 1 0 1 1 0 0 1 1
0 0 0 1 1 0 1 1 0 1 0 1
0 0 0 1 1 0 1 1 1 0 0 1
0 0 0 1 1 1 0 0 0 1 1 1
0 0 0 1 1 1 0 0 1 0 1 1
0 0 0 1 1 1 0 0 1 1 0 1
0 0 0 1 1 1 0 1 0 0 1 1
0 0 0 1 1 1 0 1 0 1 0 1
0 0 0 1 1 1 0 1 1 0 0 1
0 0 0 1 1 1 1 0 0 1 0 1
0 0 0 1 1 1 1 0 1 0 0 1
0 0 1 0 0 1 0 0 1 1 1 1
0 0 1 0 0 1 0 1 0 1 1 1
0 0 1 0 0 1 0 1 1 0 1 1
0 0 1 0 0 1 0 1 1 1 0 1
0 0 1 0 0 1 1 0 0 1 1 1
0 0 1 0 0 1 1 0 1 0 1 1
0 0 1 0 0 1 1 0 1 1 0 1
0 0 1 0 0 1 1 1 0 0 1 1
0 0 1 0 0 1 1 1 0 1 0 1
0 0 1 0 1 0 0 1 0 1 1 1
0 0 1 0 1 0 0 1 1 0 1 1
0 0 1 0 1 0 0 1 1 1 0 1
0 0 1 0 1 0 1 0 0 1 1 1
0 0 1 0 1 0 1 0 1 0 1 1
0 0 1 0 1 0 1 0 1 1 0 1
0 0 1 0 1 0 1 1 0 0 1 1
0 0 1 0 1 0 1 1 0 1 0 1
0 0 1 0 1 1 0 0 1 0 1 1
0 0 1 0 1 1 0 0 1 1 0 1
0 0 1 0 1 1 0 1 0 0 1 1
0 0 1 0 1 1 0 1 0 1 0 1
0 0 1 1 0 0 1 1 0 0 1 1
0 0 1 1 0 0 1 1 0 1 0 1
0 0 1 1 0 1 0 0 1 1 0 1
0 0 1 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1

– Pasted Max Patch, click to expand. –


xaf
June 27, 2013 | 4:10 am

hahaha, who needs drugs when you have max/msp? and the best part is, you can share the experience here. i’m glad i could assist you guys in cooking your brains a bit further ;-)
thanks everybody!


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