1

I have an array of 144 elements (integer numbers) and I want to find all possible permutations in Matlab. BUT the "problem" is that all these integer numbers can only have five different values: 11, 22, 33, 44 and 55 (the values do not really matter but anyway) and therefore changing, let's say, two 11's with each other does not make a new permutation. What I want is to find ONLY the unique permutations.

Matlab has the function perms which can find all possible permutations and put them in a table. But since it finds ALL possible permutations and not only the unique ones, it does not work in my case because the outcome-table would have 144! rows which is too much and makes my machine (i7 cpu, 8gb ram) run out of memory. If perms worked, I could then keep only the unique rows, which, if I am not wrong, should be 144!/n(11)!*n(22)!*n(33)!*n(44)!*n(55)!, where n(p) = times that number p appears and n(11)+n(22)+n(33)+n(44)+n(55)=144.

Is there any way to either make perms work with an array of 144 elements work or even better a way to find only the necessary permutations? Another solution would be to be able to get all the 144! permutations without storing them in a table (I will use them one-by-one as they are produced). But I don't know how to do any of the above.

======================================

P.S.: I have also tried uint8 in order to try and keep perms from consuming too much memory but it was not enough.

P.S.2: Since 144! is A LOT larger than 144!/n(11)!*n(22)!*n(33)!*n(44)!*n(55)!, a solution that finds only the necessary permutations would be better but please reply even if you have an idea on how to find all possible permutations and then I can keep the unique ones

P.S.3: I am not sure if I should call "permutations" or "combinations"what I am looking for because in a way it is both. Anyway, I decided to call them permutations in my question.

Ander Biguri
  • 35,140
  • 11
  • 74
  • 120
Kots
  • 11
  • 3
  • I am sorry but my question is totally different. The question you present as similar is about Cartesian product. Mine not only is a different question but I also ask about a trick that someone may know in order to avoid calculating all the permutations which makes my pc run out of memory. I searched a lot before I make my question and I could not find anything similar. Is it possible for the message "This question already has an answer" to be removed please so that someone that may help does not ignore my question? – Kots Jul 07 '15 at 11:18
  • instead of (pseudocode) `unique(perm(data))` why not `perm(unique(data))`. Do not compute all the possible permutation and get the unique values, just get the unique values first and then permute those! – Ander Biguri Jul 07 '15 at 11:33
  • In this case I will have a different thing than what I want. `unique(data)` will change my data set and it will only return the table [11, 22, 33, 44, 55]. But I need all the 11's, 22's etc that my data set initially has. Thank you anyway for your response. – Kots Jul 07 '15 at 11:41
  • `unique(data)` will not change the data, it will return a variable with the unique values without touching the data. – Ander Biguri Jul 07 '15 at 12:42
  • I know. What I meant is that I cannot use the outcome of unique(data) in order to do what I want because unique(perms(data)) is not the same as perms(unique(data)). The first one will give 144!/n(11)!*n(22)!*n(33)!*n(44)!*n(55)! permutations (which is what I want) and the second one will give 144*143*142*141*140 permutations. I think I need a smarter way to compute only the 144!/n(11)!*n(22)!*n(33)!*n(44)!*n(55)! permutations that I want without computing all the 144! permutations first and then keep the unique ones. But I don't know how to do that. – Kots Jul 07 '15 at 13:12
  • I agree your question is not _exactly_ a duplicate in the sense that you only want a subset of what the answer would give you. However, most way of tackling the question would take this route then reduce the dataset. If you cannot do that because of memory problem, then you'll have to devise your own recursive algorithm. You can look at the code of the function `perms` to start, and replicate that while eliminating duplicates as they are created to keep the numbers low. – Hoki Jul 07 '15 at 13:57
  • Now consider this: Granted `144!=5.5e+249 `, not many computers will let you define arrays of this size. But if I assume a flat distribution of your 5 unique elements (so [28x`11` 29x`22` 29x`33` 29x`44` 29x`55`]), then the number of **unique** permutations is still `144!/(28!*(29!).^4)=3e96` ... **3e96 perms** !! of an array of 144 elements. Even if you had a 3bits type (minimum capable of holding your 5 different values), you'd need `3e96*144*3/8/1024^3=1.5e89` GBytes to hold such an array !! That's still about 3e76 times the [worldwide HDD capacity](https://en.wikipedia.org/wiki/Zettabyte) – Hoki Jul 07 '15 at 14:11
  • I am pretty sure there is a logic flaw in those number indeed. 144! is just so ridiculously high that it **MUST** be wrong. – Ander Biguri Jul 07 '15 at 14:33
  • Perhaps you could give an example of what you want using a reduced data set; say, `[11, 22, 33, 11]`. – beaker Jul 07 '15 at 15:45
  • 1
    @AnderBiguri The number of permutations of `n` elements is `n!`. Big number. That's why Matlab documentation says don't even try it with anything bigger than `n=10`. – beaker Jul 07 '15 at 15:51
  • This might be more applicable: http://stackoverflow.com/questions/13109710/finding-unique-permutations-efficiently – beaker Jul 07 '15 at 15:59
  • I know that 144! is a ridiculously high number, this is why I am trying to find a way to either find only the permutations I need or find all 144! permutations but not store them in a matrix. I am now working on the second option and for that I (believe) I have just written the Steinhaus Johnson Trotter permutation algorithm in Matlab. That way, given a permutation, I can find the _next_ one and therefore dispose the previous one as the algorithm will never return to it. That way I can find all 144! permutations (although I do not need all of them) and use them one at a time. (1/2) – Kots Jul 07 '15 at 17:17
  • I am not sure at all if it is going to work but until something else comes up I will be working on this. Does anyone know if the calculation of all 144! takes "reasonable" time (given that I will not run out of memory since I will not store the permutations)? (2/2) – Kots Jul 07 '15 at 17:17
  • @beaker Your link seems very interesting at first. I will look into it – Kots Jul 07 '15 at 17:23
  • Why are you generating the permutations if you're not going to store them? – beaker Jul 07 '15 at 17:53
  • For every permutation I compute a Utility Score and I am looking for the permutation with the highest one. So when I find a permutation, I will also find its score and I will only store them (the score and the permutation) until another permutation with greatest score is found in which case I will overwrite the score and the best current permutation. That way I will only keep one permutation stored. I am trying to do that with the Steinhaus-Johnson-Trotter permutation algorithm. But I have no idea of the computational time it will need. Hopefully it is reasonable. – Kots Jul 07 '15 at 18:03
  • On my machine, `perms([1:10])` takes about `0.4` seconds if I suppress output. By my calculations, `144!` would require on the order of `10e242` seconds. – beaker Jul 07 '15 at 18:06
  • lol ... that's _only_ 3e229 million years :D (although i'm sure you'd be able to optimize that by a factor 10 or 100 ... ho well) – Hoki Jul 07 '15 at 18:28
  • I will not use perms but the function I made based on Steinhaus-Johnson-Trotter permutation algorithm. But again, I don't think that 144! permutations can run in reasonable time. If I manage to find a way that "only" produces 144!/n(11)!*n(22)!*n(33)!*n(44)!*n(55)! permutations (which with my numbers is equal to 1.5521e+25), is there any chance that the time is reasonable? – Kots Jul 07 '15 at 19:02
  • @Kots You're down to around 3 years. – beaker Jul 07 '15 at 19:09

0 Answers0