This problem has been playing on my mind for some time and I wanted to share it.
St Martins Church in Birmingham England has 16 change ringing bells. Each bell is tuned to a different note. The total possible permutations is a staggering 20,922,789,888,000. Twenty trillion, nine hundred twenty-two billion, seven hundred eighty-nine million, eight hundred eighty-eight thousand. A few orders of magnitude more stars than exist in the milky way.
If I put 123*4(…)*16 into Supercollider it returns ‘2004310016’. I suppose this is Supercollider’s highest number. Or at least in that region.
Although these numbers boggle my mind I am also keen to use them.
Supposing that I create an algorithm that allows me to access any of those twenty trillion permutations - or more - without the use of an array. I might want to access the ‘middle’ permutation, but I cannot put in 20,922,789,888,000 / 2.
First, I wanted first to check if this is the case? A friend showed me in Python they could do it. However I expect Python will also have its own highest number, so the same problem occurs at a different scale.
Second are there workarounds for this? I imagine some creative use of modulos might be one. I don’t want to reinvent the wheel. I realise dealing with trillions of permutations might seem meaningless, but I don’t want to close off that possibility of working in this way, or be scared off from the subject due to the intimidating scale of the numbers.
Haskell, Python, and other languages have arbitrary-precision integers, meaning they can work with integers of any size. Nowadays, there are very efficient implementations for those types.
In SCLang, you will need to use Float. This works but can cause precision loss for huge numbers. To use it, add ..0 like this:
20922789888000.0
There could theoretically be solutions, but the project’s leadership and most users don’t think it’s a “high-priority” issue. Since there are no language plugins, nobody can write a BigInt or similar arbitrary-precision library.
Another aspect of your situation is that, specifically for permutations, you don’t need to generate all possibilities to access a specific one. You can use factorial number systems or combinatorial algorithms to generate the nth permutation directly. This is called the “unranking” problem in combinatorics.
EDIT:
To link those two aspects:
even with implementing the nthPermutation in SCLang using Float, that’s not safe. You might see some rounding errors with huge numbers if you see something like this. This is unavoidable with floating-point arithmetics
a.nthPermutation(20922789888000.0)
If you use modulo arithmetic to wrap around large numbers, which helps handle larger values but will not give you access to every possible permutation when dealing with numbers beyond SClang Float limitations. I don’t know if there is a workaround for that. I think it would be just too messy if it were even possible.
This is very helpful to know. I wasn’t planning to generate all the possibilities, but without a math background I was not aware of the relevance of combinatorics.
It’s good to know about floats, but accuracy will be essential. I might take a look at Python for some of these tasks.
If you use modulo arithmetic to wrap around large numbers, which helps handle larger values but will not give you access to every possible permutation when dealing with numbers beyond SClang Float limitations. I don’t know if there is a workaround for that. I think it would be just too messy if it were even possible.
This was my concern. A lack of elegance, practicality, and readability. It’s a shame SC doesn’t yet have this capability but I am intensely grateful it exists and is sustained as the wonderful tool it is.
“abcdefghijklmnopq” would be each bell in order
“bacedefghijklmnopq” would have the second bell first then the first then the others in order etc…
This collection is still ordered since SC will evaluate "abcdefghijklmnopq" < "bacedefghijklmnopq" as true
These have the advantage over integers that they are readable directly…
for giant Integers you can write a class using strings (I had to do this once) so “12345678901234”.big - internally you use a pair of Ints [1234567, 8901234] and then define the ops appropriately
However, it does not guarantee that much smaller numbers used as input to some operations will never introduce errors.
Is it enough for the original example case?
EDIT: Well, one can ignore part of the combinations when they reach a “safe limit”; in some cases, one will not really need complete correctness and complete implementation.
This is one of the algorithms I mentioned before. It’s a classical topic/question/problem in combinatorics (it goes back to the 19th century, I think), but you can probably grasp it without deep diving. There is a lot of material online.
You should probably want to solve/implement this one, too (or the concept of ways to restrict combinations)
EDIT: I can try to write this (or the general idea behind this problem) in SCLang when I have time. @domaversano You can try it before me and see how it goes.
A possible version of the idea in Haskell
(this is a half-cooked version using brute force, sorry this code is O(n!); there are more clever ways, but would require less clear code)
module Main where
import Control.Monad (guard)
import Data.Array
import Data.List (permutations, subsequences)
isStrictlyOrdered :: (Ord a) => (a -> a -> Bool) -> [a] -> Bool
isStrictlyOrdered _ [] = True
isStrictlyOrdered _ [x] = True
isStrictlyOrdered cmp (x : y : xs) = x `cmp` y && isStrictlyOrdered cmp (y : xs)
validPermutations :: Int -> Int -> [[Int]]
validPermutations n k = filter isValidPerm $ permute [1..n]
where
isValidPerm perm = not (hasLongerAscDesc perm)
hasLongerAscDesc xs =
hasLongerSubsequence isStrictlyOrdered (>) (k + 1) xs
|| hasLongerSubsequence isStrictlyOrdered (<) 3 xs
hasLongerSubsequence orderCheck cmp m xs =
any (\subseq -> length subseq >= m && orderCheck cmp subseq) (subsequences xs)
permute [] = [[]]
permute xs = concatMap (\(y, ys) -> map (y:) (permute ys)) (selections xs)
selections [] = []
selections (x:xs) = (x, xs) : [(y, x:ys) | (y, ys) <- selections xs]
countValidPerms :: Int -> Int -> Int
countValidPerms n k = length (validPermutations n k) `mod` 1000000007
main :: IO ()
main = print $ countValidPerms 5 3