extending urn-jb

johannes's icon

hello,

i wonder how to create a stream of non-repeating random numbers,
from which i like to get 3 values at a time (using uzi) without repetitions as well.

eg. if this is the result of the 1st stream of urn values:

2 4 3 1 5 7 6

and this the second stream

5 6 1 3 7 2 4

i want to use the values in groups:

2 4 3
1 5 7
6 5 6
1 3 7
2 4 …

as you can see the 6 in the 3rd group of numbers appears twice. the easiest way to handle a situation
like this would be to clear the duplicates. the better and much more advanced technic would be using another number
instead of the 2nd 6 without destroing the the non-repetition of the current stream.

is there an object that obtain non-repeating random number under this circumstances?
and if not, how can i do it in a efficient way in max by myself?

thanks for your help , johannes

Peter Castine's icon

Anyone asking for a stream of random numbers without repetition is essentially looking for a kind of Markov chain. The [prob] object is the standard general Markov chain object. However, it is designed with first-order Markov chains in mind, and what you're looking for would need a second-order Markov chain.

The inestimable Xoaz (aka Richard Dudas) built a an abstraction wrapper around [prob] for higher-order Markov chains. It was called [mchain] and I expect it's now available through the Tools page on this site.

However you try to manage this with factory objects, there will be a bit of work to do, it ain't just settin' a parameter. I did build a custom object doing this sort of thing, once upon a time, but I never polished it up for public consumption. Some day, but it's fairly low down my To-Do list.

Wetterberg's icon

Peter, they're nowhere to be found. Upon googling for Dudas' abstractions it would seem that they're offline from ircam as well.

sounded ideal for one of my capers as well.

Peter Castine's icon

Ouch.

Richard should be on the forum (he certainly used to be). I hope he won't mind me suggesting that someone drop him a line expressing interest in mchain.

I have a copy, but it's really better if you get it directly from the source. Richard may have made some improvements over my (very old) copy.

johannes's icon

thanks for pointing to richards abstraction, peter.
you can now find mchain on his site…
and it seems to work fine for me (under 10.7.5 running max 6.0.8.)

i found a nice intro on markov chains in dodge´s "computer music" book as well as
in roads " the computer music tutorial".
is there also a paper or tutor about using markov chains in max?

j

Wetterberg's icon
johannes's icon

ok, i checked mchain. its a very nice abstraction but not exactly what iam looking for.

from what i understand, with a 2nd order markov chain i can define that the numbers of the first and second state will not appear as a number at the 3rd state. so there will be 0 probability for the first two numbers to be the 3rd and the first to be second value.

what i don´t understand is how to create a markov chain that gives me also a stream of non-repeated numbers from 0 to n-1
(lets say 14). will i have to feed a urn stream into a prob object or how does it work?
as i see in richards patch bitshifting will be needed to get an m c order > 1.

any help would be greatly appreciated, j

Peter Castine's icon

I never promised a rose garden;

With a 2nd order Markov with (to keep things simple) four states (0, 1, 2, 3), you need to set up a transition matrix like the following (the first column gives the previous two states, the following columns are the probability for the next value).

Next: 0   1   2   3
=============
 00: n/a n/a n/a n/a
 01: 0    0    .5   .5
 02: 0    .5   0   .5
 03: 0    .5   .5   0
 10: 0    0    .5   .5
 11: n/a n/a n/a n.a
 12: .5   0    0    .5
 13: .5   0    .5   0
 20: 0    .5   0    .5
 21: .5   0    0    .5
 22: n/a n/a n/a n/a
 23: .5   .5   0    0
 30: 0    .5   .5   0
 31: .5   0    .5   0
 32: .5   .5   0    0
 33: n/a n/a n/a n/a

Extend that for n=whatever: given the previous to states t[-2] = x and t[-1] = y, (x≠y), then the probability of t[0]=z is zero for x and y, otherwise 1/(n-2).

Yes, this turns into masses of typing for large values of n, and this is a special kind of Markov chain where an algorithm can be designed where all you would need to specify is a single parameter. But until someone writes an external object that implements your special case, you're probably going to have to do it the hard way

johannes's icon

thanks peter,

here is my 2nd order markov-chain patch using the ftm-library. inspired my peter elseas paper
"max and chaos" i use the table object for the probabilities and a ftm-dictionary that contains the
transition-table.

i add a function that automatically generates the transition-table (that peter mentioned) according to the selected maximum value.

the aim of this patch is to create groups of 3 numbers with no repetitions in it.

Max Patch
Copy patch and select New From Clipboard in Max.