Created
September 20, 2018 10:32
-
-
Save kalmarek/238a807da33da7065eca3b3dfed35e07 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
doc""" | |
elements!(G::PermGroup) | |
> Return an unsafe iterator over all permutations in `G`. Only one permutation | |
> is allocated and then modified in-place using the non-recursive | |
> [Heaps algorithm](https://en.wikipedia.org/wiki/Heap's_algorithm). | |
> | |
> Note: you need to explicitely copy permutations intended to be stored or | |
> modified. | |
# Examples: | |
```jldoctest | |
julia> elts = Generic.elements!(PermGroup(5)); | |
julia> length(elts) | |
120 | |
julia> for p in Generic.elements!(PermGroup(3)) | |
println(p) | |
end | |
() | |
(1,2) | |
(1,3,2) | |
(2,3) | |
(1,2,3) | |
(1,3) | |
julia> A = collect(Generic.elements!(PermGroup(3))); A | |
6-element Array{AbstractAlgebra.Generic.perm{Int64},1}: | |
(1,3) | |
(1,3) | |
(1,3) | |
(1,3) | |
(1,3) | |
(1,3) | |
julia> unique(A) | |
1-element Array{AbstractAlgebra.Generic.perm{Int64},1}: | |
(1,3) | |
``` | |
""" |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Since `PermGroup` implements the iterator protocole You may iterate over all permutations via simple | |
``` | |
for p in PermutationGroup(n) | |
... | |
end | |
``` | |
Iteration over all permutations in reasonable time, (i.e. in terms of minutes) is possible when $n ≤ 13$. | |
You may also use the non-allocating `Generic.elements!` function for $n ≤ 14$ (or even $15$ if you are patient enough), which is an order of mangitude faster. | |
```@docs | |
Generic.elements!(::Generic.PermGroup) | |
``` | |
However, since all permutations yielded by `elements!` are aliased (modified "in-place"), `collect(Generic.elements!(PermGroup(n)))` returns a vector of identical permutations. | |
!!! note | |
If you intend to use or store elements yielded by `elements!` you need to **deepcopy** them explicitly. | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment