Sp3000 pointed out that this is because e! does an implicit sort. That seems like an even bigger issue actually, because it means I can't reliably pick out a specific permutation if I need to (and my input is unsorted). I always assumed e! would be equivalent to (but possibly faster than) m!_&.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
e! uses a somewhat different algorithm. It generates the permutations in lexicographic order, and does not generate duplicates (to be removed at the end). It does need the elements to be comparable. An array of ten 0's and two 1's will have exactly 66 permutations rather than 479 million out of which 66 are distinct.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Right, but couldn't you just give the elements comparable identities? E.g. if the input is [1 2 "A" 2 'C "A" 'C [] []] then you'd turn that into [[0 1] [1 2] [2 "A"] [1 2] [3 'C] [2 "A"] [3 'C] [4 []] [4 []]. Now the first elements are comparable and you can run your algorithm based on those, and at the end you extract the second value of each pair.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Well, that would be possible, but it gets complicated. We'd need to get into the details of what it means to be comparable and which kinds of values are supposed to be equal, and then I'll need to do O(n^2) equality tests and define a semi-arbitrary order as you suggested. Anyway, I'll consider it.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I don't think the order is arbitrary at all. This behaviour would be consistent with how m! works for unsorted inputs. As for comparability, I'd just consider different types unequal, and then use the usual equality between elements of the same type (although it seems that = on two blocks always yields 0 - I'd consider blocks with equal string representation equal for this purpose, and NaNs as well). With these semantics you'd get all distinguishable permutations without discarding any indistinguishable ones.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Sp3000 pointed out that this is because
e!does an implicit sort. That seems like an even bigger issue actually, because it means I can't reliably pick out a specific permutation if I need to (and my input is unsorted). I always assumede!would be equivalent to (but possibly faster than)m!_&.e! uses a somewhat different algorithm. It generates the permutations in lexicographic order, and does not generate duplicates (to be removed at the end). It does need the elements to be comparable. An array of ten 0's and two 1's will have exactly 66 permutations rather than 479 million out of which 66 are distinct.
Right, but couldn't you just give the elements comparable identities? E.g. if the input is
[1 2 "A" 2 'C "A" 'C [] []]then you'd turn that into[[0 1] [1 2] [2 "A"] [1 2] [3 'C] [2 "A"] [3 'C] [4 []] [4 []]. Now the first elements are comparable and you can run your algorithm based on those, and at the end you extract the second value of each pair.Well, that would be possible, but it gets complicated. We'd need to get into the details of what it means to be comparable and which kinds of values are supposed to be equal, and then I'll need to do O(n^2) equality tests and define a semi-arbitrary order as you suggested. Anyway, I'll consider it.
I don't think the order is arbitrary at all. This behaviour would be consistent with how
m!works for unsorted inputs. As for comparability, I'd just consider different types unequal, and then use the usual equality between elements of the same type (although it seems that=on two blocks always yields0- I'd consider blocks with equal string representation equal for this purpose, andNaNs as well). With these semantics you'd get all distinguishable permutations without discarding any indistinguishable ones.Actually, the behaviour would be different from
m!. In your example, the first permutation withe!would be[1 2 2 "A" "A" 'C 'C [] []]