Permutations program with very large integers problem...
Hi all,
I'm working on a patch that takes 39 audio samples and randomly orders them to play. I'm currently using [urn] to randomly cycle through each of the samples uniquely. This is working great. However, I'd like to have the patch work through each of the permutations of the 39 samples without the possibility of repeating. Right now [urn] will randomly work through a set of 39 fine, but once I repeat the process there is the possibility that [urn] will pick the same random combination of 39.
A factorial of 39 is: 39! = 20397882081197443358640281739902897356800000000
So that's the total possible permutations. This integer is beyond the [int] range for Max. My first thought was to store all possible permutations in a jitter array and then have [urn] randomly pick a plane of 39 values each time to make sure there are no repeats. But the limitation on max values seems to make this problematic.
Anyone have any ideas on this?
Here is the patch I'm playing with:
Thanks!
its called non-repeating urn and can be found e.g. here:
https://cycling74.com/tutorials/week-36-non-repeating-urn/
and other places.
hth
hans
That's not quite going to work because he wants every possible permutation, not just not repeating successive numbers. (In fact, you probably will end up repeating successive numbers at some point!)
Instead, use mxj list.Permutation. It will return the nth permutation for a list. Granted, you'll probably not actually be able to get to all possible values given the very large size of it, but this is an improvement.
Anyways, there is an upside to the astronomical numbers you cited: the odds of it repeating the exact sequence are 1 / 20397882081197443358640281739902897356800000000, or not-in-your-life-likely-to-happen. This presumes a true RNG (not what we have here...), but still, fairly unlikely and absolutely unnoticeable. (And if for some reason it is noticeable, check your implementation, or treat it like seeing a supernova) You can also mess with the seed. (Using UNIX time is a good starting point)
Other things:
Use sflist~ to set up cues for your sfplay~ objects. Then you can just send a number (cues start numbering at 2).
but even if he uses every possible permutation of his 39 set, chances are big, that of 2 consecutive permutations one ends with a number the second one is starting with. (someone more mathematically talented than me could probably calculate this number and i am certain it is huge).
so the main focus still is the boundaries between two adjacent permutations, to have no repeating numbers there.
thats what i was aiming at.
but thanks for reminding me of mxj list.Permutation. had forgotten, that it exists.
hans
Chance of repeat at the sequence boundary is 1/39, since the probability is not affected by previous results there.
I read it that he doesn't want the same set to repeat, not the same number. Can OP clarify? If it's both, then you have a more fun problem...
surely you can iterate through the mxj list.Permutation (iterate 1) and then simply use the change object to filter out repeats - you'll get all permuations, just without the one offending number - which, as Peter also brought up - won't come up very often.
Chance of it occuring at the sequence boundary is 1/39, and that chance is itself only 1/39 (sequence boundary).
... I'd just rip that one repeat out and keep soldiering on.
Basically there are two approaches: a series of systematic permutations or a randomized sequence of permutations.
With the latter, even once you manage to avoid pairs of permutations that have the same border element -- ie 39th element of P(n) == 1st element of P(n+1) -- you can still have situations where, for instance, the only difference between two consecutive permutation is that the 38th and 39th elements are transposed. Depending on the elements, this may be perceived as a simple repetition.
There are plenty of systematic transformations where each sequential permutation will be perceived as "different". And there's plenty of literature on this, both in mathematical permutation theory and in some of the serialist composition literature from the 1950s & '60s.
Given the size of your set, no one is going to live to hear all the permutations. Even if played back at sampling rates, the duration would be longer than the time since the Big Bang.
In any case, you need to decide exactly what approach you want to take and implement it. There is no factory object (nor 3rd Party Object) that will do exactly what you're after. So you'll need to do some programming, either with patch cords or with any of the procedural extensions to Max.
if you really took into account to store 20397882081197443358640281739902897356800000000 possible list in an array, i would suggest you buy google or AOL and then wait 130 years, because you laptop wont be able to store that database anyway.
p.s. i wonder what progam was used to calculate 39! ?
p.s. i wonder what progam was used to calculate 39! ?
A.o., scheme can do that. Or this: http://www.mathsisfun.com/calculator-precision.html
p
Hi all,
Thanks for all the excellent responses and lively discussion on my little monster!
I used an online calculator like Patrick gave a link to to generate the number. Part of my interest is practical here, the other part is certainly intellectual. The patch as it's running now generates random combinations very well, I haven't been able to notice repetitions (and probably won't considering the possibilities mentioned!). And I certainly realize it's not possible to hear all the combinations (in several thousands of millennia). What I am after in trying to pursue generating random true permutations was pushing the idea out in true form. I'm kind of cheating now just generating random combinations, they aren't "true" permutations. So on one hand, who cares b/c the patch works well now anyway. On the other, the anal retentive carpenter in me knows this isn't "right" and wants it to be theoretically and programmatically "correct".
I started playing with some suggestions mentioned here, see the patch.
Urn maxes out @ 4096 as the largest integer it can take by the way.
Random maxes out somewhere above 2 billion.
Anyway around it there will be problems dealing with such large numbers. But even if I accept being limited in the number of permutations being produced (still more than we could ever listen to), there are other problems.I run into things like Peter talked about. You get true permutations but many of the permutations only change number orders slightly or even flip just two numbers. This won't work well practically b/c it will sound very much like a broken record repeating.
So with all that said, I guess the ideal solution would be a system that could:
1) Handle astronomically large integers (or even if these were broken into smaller unique sets? Generate portions of the full set, work through them, then generate the next portion?)
2) Generate a randomized sequence of permutations that differ significantly enough from one another that they don't seem to repeat at all (this seems to me the hardest part)
3) Have non-repeating boundaries like others have mentioned. ex: as the 39th sample plays, the 1st sample of the new sequence isn't the same as the 39th sample played.
This seemed like a fairly straight forward exercise when I started. But once I really dig in and start to explore the system it is wonderfully complex! I'm not much of a math whiz and think this problem is going a bit beyond my pay grade. I'm going to try and consult with some PHD math majors and see what they think. I would love to hear continued discussion of solutions if anyone has ideas.
Cheers!
@Peter
If you have a link or two describing some of the math theory or serialist composition you mentioned I'd love to see them! I'm going to do some searches myself, but if you have anything good, please pass it along.
Thx
i totally understand you when you want to do it "right", i am often quite anal with my math stuff while knowing it is not really needed to get a certain result.
for the application you describe above i think i would put a [drunk] object into a [poly~ mydrunk 39], and
whenever i need the next list, i would send a bang to "target 0", and have a zl queue 39 behind the poly~
-110
@lostboy
I'd say that actually 2) is not that bad of a problem. Because these soundfile sequences are long, you have loads of time to compute and find a suitable solution from millions of acceptable solutions.
The key thing is coming up with a metric for what makes a set of values acceptable when compared with the previous sequence.
Also, everytime I have some idea like this I like to re-read Borge's "The Library of Babel". It helps to keep things in perspective regarding the quasi-infinite nature of permutations and the scope of human lives.
@lostboy: [random], as you noticed, provides 31 random bits. That's a charactaristic of 32bit signed integers limited to positive values. It's a bit like saying that water's wet.
BTW, I'm not convinced that [random] will produce all 2^31-1 possible bit combinations. It's a LC generator with non-prime parameters, so the low-order bits are not at all random. Even with the best parameters, a 31-bit Linear Congruence RNG is guaranteed to repeat, at the very latest, after 2^31 values.
The higher quality RNGs in the Litter Power Package (lp.titi, lp.tata, lp.mrmr, etc.) work with 32-bits, so will give you all values from -(2^31) to 2^31-1 and will produce all possible bit combinations. Because they use more than one 32-bit register internally, they will produce far more than 2^32 values before they repeat. Lp.tata, for instance, will produce approximately 2^88 values before cyling, titi goes for about 2^800 values, and mrmr goes on for something like 2-to-some-four-or-five-digit-exponent-that-I'll-have-to-look-up. The point being that you could concatenate 5 consecutive values generated by one of these guys to produce a random 47-digit number as an index into your (virtual) list of permutations.
Implementation left as an exercise to the reader. It's moderately straight forward.-)
About the references: Less concrete than I would like as I currently can't access my EndNote database of these for a number of reasons (mostly because it's on a machine 1200km from where I am).
Off the cuff: pretty much anything by Babbitt on serial technique is worth reading (actually, pretty much anything by Babbitt on *anything*-). Permutations tend to be a bit tangential.
I seem to recall that Křenek wrote concretely about systematic permutations of 12-tone rows as a variation technique, but I read that long before I started keeping a bibliography.-(
Boulez' articles "Eventuellement" (English translation available under the title "Possibly…") and "Musikdenken heute" (I believe there is a French translation but I don't know of one in English) go a bit into a serial approach to permutations.
Lewin was another good read. If you can find his 1966 paper in JMT "On Certain Techniques of Re-Ordering in Serial Music" helpful.
Coming from a different point of view, Douglas Hofstadter wrote a bit about randomised music in _Gödel, Escher, Bach_. "Different point of view" in that Doug doesn't seem at all convinced about chance in music (and he tends to miss the point about Cage). Still, a gifted thinker overall.
Sorry if this is a less concrete than you were hoping for.