Skip to content

Instantly share code, notes, and snippets.

@kalmarek
Created September 20, 2018 10:32
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kalmarek/238a807da33da7065eca3b3dfed35e07 to your computer and use it in GitHub Desktop.
Save kalmarek/238a807da33da7065eca3b3dfed35e07 to your computer and use it in GitHub Desktop.
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)
```
"""
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